No jinxing plsssss.

I thought nobody likes stories

stories are annoying during contest time but enjoyable during practice

Your prediction is true! They must upvote u!

Sorry for that.

lmao u r actually true

Regret for not trusting you, with tears after the contest

For people who don't like stories, you will find all the stories written in italic you can skip them safely.

This line was not for you if you like stories.

Pinky promise >>>>

The struggle with D and E was real fun! Looking forward to the editorial. Kudos to the entire team for a great contest. :)

Imagine thinking you are entitled to regulate how other people talk.

I agree

I hope so

F

yes! below 2100 rating can participate includes candidate master

strong pretests are even better

Thanks). Good luck to you too)

Till C in an average div 2 round.

Hope I return purple this round!

Last problem has 2 subtasks, if you solve just the easy one, you'll get max 1750 pts, if you solve both, easy and hard subtask, you get max 1750 + 1750 = 3500 pts. Also, avoid caps please :)

Way too long..

No. TLE has nothing to do with long queue.

gg wp

It has a 1000 points, usually it's only 750 points. I think its justified.

Read the announcement carefully, (For people who don't like stories, you will find all the stories written in italic you can skip them safely.)

+1 from future specialist

There might be a part of the array in the middle where we cannot move any element. If that part is not correctly sortet in input then ans=NO.

The main idea to solve this problem is that you will not able to swap the elements present in the array in the range from (n — x) to x, so, the elements that are present in this range must be sorted and must have values equal to the sorted array..

I think binary search on the edges was required. Since the gcd of two numbers is always smaller than or equal to the smaller of the two number ( $$$gcd(a,b) \lt = min(a,b) $$$) . This means that the maximum distance will be between two nodes that are intially having a edges.

Now we can find the maximum distance between any two edges in 1 query. After that we can binary search on the edges and find the edge with the distance equal to maximum distance.

I was not able to get AC and might be entirely wrong.

Yes, basically the idea is the following:
1. Set the goal = query of all nodes, we will eventually end up with this score between exactly two nodes.
2. Perform the following operations on the tree, till the tree has exactly two nodes (the answer):
2.1. Find the centroid of the tree and let's root the tree at the centroid.
2.2. For each child of the centroid add all the nodes of the subtree rooted at the child into a set.
3.3. From 2.2, we have k sets of nodes where k is the number of children of the centroid.
3.4. Merge all these k sets into exactly 2 sets, here we need to make these two sets have size as close as possible to each other. This can be done accurately enough by using knapsack as you described, but I used a greedy version for my implementation and it got accepted. Although, I am not entirely sure it is correct, so please someone prove its correctness or hack it :p.
3.5. After merging we ask a query on the first of these two sets. If the query == goal then we know that we have a valid answer in the set we asked, so we remove all the nodes & edges of the tree from the other set. Otherwise, if query != goal we know that our answer is contained in the second set, so we remove the nodes & edges of the first one.
3.6. If we end up with just two nodes, this is our answer, otherwise, we repeat the 2nd step.

Note that the 2nd step will be executed at most log(n) times because in each iteration we remove almost half of the tree's nodes. It can be proven that the size difference between these two sets will be small enough to keep it in log time, (if we merge all the k sets optimally) because of the properties of the centroid.

Here is my post-contest submission (130742844) of this implementation.
(Again, I did not use DP knapsack to merge the K sets into 2 as optimally as possible, so it might be hackable)

They probably had something like split into at most k trees and then changed it last-minute for that XD

I actually got C wrong answer at 10 because I handled the case when K = 1 instead of 2 because of that line. after the contest I edited it and got the late ACC :(

I thought that was to be able to easily write the constraints on n and k. It was something like 1 <= k <= n <=

This is what I did. Let XOR of all elements be Xo.

1) If Xo == 0, then there is always an answer ( As all elems >= 1 => it is possible when two partitions have equal XORs ) 2) If Xo != 0, then we need to divide the tree into 3 components. So, I ran a DFS across the graph which basically returns XOR of the subtree. a) If Xor of a subtree == Xo => this is a candidate for division. Return 0 ( So that we don't double count it, especially for cases where some contiguous group of ancestors have a xor 0. This leads to double counting of this subtree b) If Xor of a subtree != Xo, just return Xo

Finally, if we have > 1 nodes with Xo XOR and k > 2 => we can always have an answer.

Rerooting approach (couldn't implement it in time because I was stuck at problem B):

void dfs1(int u = 0, int p = -1) {
    dp[u] = a[u];
    for(auto v: g[u])
        if(v != p)
            dp[u] ^= dp[v]; 
}

void dfs2(int u = 0, int p = -1) {
    for(auto v: g[u]) {
        if(v != p) {
            edges.push_back({dp[v], dp[u] ^ dp[v]});
            dp[u] ^= dp[v];
            dp[v] ^= dp[u];
            dfs2(v, u);
            dp[v] ^= dp[u];
            dp[u] ^= dp[v];
        }
    }
}

Note: every edge is double-counted.

In the first DFS we calculate xor of all vertices in the subtree of u. In the second DFS we do it for every possible root. In the u's component XOR is dp[u] ^ dp[v] and in v's component XOR is dp[v].

+1

I guess you are doing a simple binary search on the edges. Imagine this, you want to ask about Edges $$$(1,2)$$$ and $$$(3,4)$$$. You will get $$$7$$$ as answer!

Test 17 is really depressing. In your case, it was for problem D and in mine, it was problem C. ;-;

You are welcome!

are you sure? I mean from 1270 to 1400+ is a big jump considering you have solved upto B. But if it does happen then kudos.