You can use $-brackets instead of `-brackets to show your formulae better owo

I know there is an additional log complexity because of map, but you can use unordered_map instead of it.

it's me

Me too, didn't get this proof. I hope someone elaborate.

You can see it this way:

• If you take any number $$$n$$$ and you add an odd number $$$z$$$, then $$$n + z$$$ is going to have its last bit flipped. That's because any odd number has its last bit set to $$$1$$$. If $$$z \in B$$$, $$$n$$$ will have an edge to $$$n + z$$$ in the generated graph. But since that always flips the last bit you can split all numbers in a set with last bit equal to $$$1$$$ and a set with last bit equal to $$$0$$$.
• Now if you multiply $$$z$$$ by $$$2^k$$$, you know that this number will have its last $$$k$$$ bits set to zero. So $$$q = 2^k \cdot z$$$ will look like this: $$$\cdot\cdot\cdot10\cdot\cdot\cdot0$$$. So if you take some number $$$n$$$ and you add $$$q$$$ to it, the last $$$k$$$ bits won't change and the $$$k-th$$$ will always change. Given that in this case you started assuming that all number in $$$B$$$ were odd then if you multiply any of them by $$$2^k$$$ the resulting number will have exaclty $$$k$$$ zeros to its right.
• Finally, if you generate the graph for this new set you can show that any pair of nodes $$$(a,b)$$$ that have an edge between, $$$a$$$ and $$$b$$$ have their $$$k-th$$$ bit flipped with respect to each other. So you can put all numbers with their $$$k-th$$$ bit set to $$$0$$$ in one set, and the rest in the other.

Let's denote the first three numbers in the array as a, b, c. Then the multiplication table has the following form: row1: 0 ab ac ... row2: ab 0 bc ... row 3: ac bc 0 ... So we do have the values of ab, ac, and bc given in the input. Then we can simply solve a system of equations with three unknowns and find the value of a. Then if we know a we can find all the other ones by simply going through the first row of the table and dividing all the entries by a. Hope it makes sense.

HERE

See Ashishgup's solution for the problem (60806580)

Em cũng éo hiểu : )

wait...why the observation 2 is correct? by the way, I think the T you build by the sample is : 1(0,5) 2(0,3) 3(0,4) 4(0,0) 5(2,6) 6(0,7) 7(0,0) but not all cartesian tree of $$$b_{k+1}...b_{k+n}$$$ is a connected compoent of it

I must mistake your solution can you help me ? thanks a lot. :D

• If I know the value of any one element I can get the values of all the remaining elements.

        Example:
        M = 0 4 8
            4 0 8
            8 8 0

• If I get the value of the first element, in this case, it is 2
• I can get remaining elements from the first row: 2, 4 by dividing the first element with all the elements in the first row.

• We can easily get the value of the first element

• Let elements be a, b, c

         M = 0 ab ac
             ab 0 bc  
             ac bc 0  

         M[0][1] = ab, M[0][2] = ac, M[1][2] = bc 
         (ab * ac) / (bc) => a^2

• Hence first element is sqrt(M[0][1] * M[0][2] / M[1][2])

• My solution LINK

The graph may have some subtrees. If you enter a subtree, you cannot leave it.Therefore, the best solution would be to start by choosing two subtrees. One for you to start the tour and one for you to complete. Vertices that are not part of a subtree can be visited without any problem. therefore you will be able to visit all. Now you need to choose two paths. These paths belong to the subtrees. These paths should have the highest possible value. For each subtree, you can calculate the highest cost of each path using dynamic programming.