Hi,

I have a doubt regd the Scalar Product Tree problem. As mentioned in the third paragraph in the editorial section: (https://discuss.codechef.com/problems/SCALSUM)

“In each block choose the layer with the least number of vertices. Select every possible pair from this layer to pre-process. Let’s observe that if the block has K vertices then in selected layer there could be at most K/sqrt(N) vertices”.

If I consider a binary tree with N = 31 vertices (please find the image link below), then

block size = sqrt(N) = sqrt(31) = 5.56 ~ 5

maximum number of vertices in a selected layer in a block = K/sqrt(N) = 31/5.56 = 5.568 ~ 5

This means that, all the levels come into a single block which has all 5 layers.

Maximum number of vertices in any selected layer in a block should not exceed 5.

But maximum number of vertices as per the diagram is 16 (in the last level)

Can someone please help me where am I going wrong?