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?