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?
binary tree would look like this : https://www.google.com/imgres?imgurl=https%3A%2F%2Fmedia.geeksforgeeks.org%2Fwp-content%2Fuploads%2Fbinary_tree-1.png&imgrefurl=https%3A%2F%2Fwww.geeksforgeeks.org%2Fperfect-binary-tree-specific-level-order-traversal%2F&tbnid=BT7Qs6cJDlR90M&vet=12ahUKEwjfvsSv7ojtAhWzk0sFHbeRCSQQMygAegUIARCiAQ..i&docid=xXDjpbYuLRe87M&w=774&h=322&q=binary%20tree%20with%2032%20vertices&ved=2ahUKEwjfvsSv7ojtAhWzk0sFHbeRCSQQMygAegUIARCiAQ