just find the largest decreasing subarray of input and avoid it, then we get the maximum rating

oh, thank you for explaining it to me, i've been confused about this for hours..

1630-D is really an impressive problem!!

when I want to find a way to go from the left-top to right-bottom, I notice these 8 cells are special, because we cannot go to the right-bottom without passing one of them, after that, I found all friends can go to the right-bottom just using one of these cells.

another 5 minutes...

every time we want to subtract, we need to subtract k or 0 counts of bitwise pos, so if we want to subtract all elements to zero, the bitwise count in every pos must be divided by k

My solution 133023219 fails at Time limit exceeded on pretest 17, can't find a way to decrease time complexity

how to solve Div.2 D?

in the second split we will split the arr into (6,7,6,5) and (5,8,5,1), then ask whether the left part has the maximum.

here's my code

        while (l + 1 < r) {
            int m = (l + r) / 2;
            get arr from euler arr[l,m](l and m inclusive)
            int t = ask(arr);
            if (t == target) {
                r = m;
            } else {
                l = m;
            }
        }

there is no way to break an edge since we only do binary search on nodes, in one search we decide to search the node's left or node's right (here left/right means left/right in euler tour array)

Let's define Dist(u,v) as the greatest common divisor of the weights of all edges on the path from node u to node v.

means the maximum dist in this tree is simply a maximum weight edge from u to v, because a >= gcd(a,b) for all positive integers

check this URL to understand what is euler tour https://www.geeksforgeeks.org/euler-tour-tree, and we generate an euler tour array from the input tree, then use binary search to find the edge with maximum dist

totally argee

The gap between div2-C and div2-D is too large so if u submit some wrong answers in the first three questions u get a bad rank...

you'll be able to submit the code after the system test for this contest is over