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

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) <= 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.

If we delete $$$k-1$$$ edges, there will be $$$k$$$ pieces of the original tree. So if $$$k=2$$$ for example, there will be $$$2$$$ trees left after removing $$$k-1=1$$$ edge.

Meaning that we cut the tree into k components, so the # of cut edges is k — 1.

K components is more natural

I think it is so that there are maximum k disconnected components as the result of the edges deletion, pretty reasonable.

One dfs should be enough. For each subtree, calculate XOR for it. If a subtree has XOR equal to $$$x$$$ (XOR of all the elements), we set it equal to $$$0$$$ and increase the counter. If the counter reaches $$$2$$$, then we can split the tree in $$$3$$$ components with equal xor.

Your observations are correct. Using x as the value of all XOR, I did a dfs from any point. At root, if A[root] == x, return 0 and increment numComponents, else return A[root]

At non-roots, you take A[node] XOR with dfs of all children (so excluding parent). Again if value == x, return 0 and increment numComponents, else return XOR value.

Basically what this does is everytime you get a subtree where its XOR equals x, you immediately break it away as a single component.

Then check if numComponents <= k or (numComponents — k) % 2 == 0 --> This means if you can achieve k components by combining 3 components into 1.

If the xor of all $$$a_{i}$$$ is $$$0$$$, you need to make an even number of components i.e just one cut is enough.

If the xor of all $$$a_{i}$$$ is greater than $$$0$$$, let's call it $$$x$$$, you need $$$3$$$ components(two cuts) with subtree xor's equal to $$$x$$$. You can easily calculate that with a dfs and cutting edges off subtrees when you meet one with a xor of $$$x$$$.

let x = xor of all nodes z = equal xor value for each component if x is zero deleting any 1 edge will do the job other wise the number of components must be odd which implies even number of edge cuts and the xor value of each connected components must be x i.e z must be = x. Thus the number of components must be 3 , 5 , 7 ... (bound depending on value of k) but We don't need more than 3 components , suppose we 5 components , we can merge 3 of them into 1 maintaining the xor value since z xor z xor z is = z

When I suspect that something like this is happening, I delete everything, read the problem statement and start writing the code again.

You can use binary search over a traversal of the graph to do this without too much implementation pain. (You have to mark a node each time you visit it, so there are 2*#edges nodes in the traversal.) https://codeforces.com/contest/1592/submission/130700097

Can you share your code for this

You probably forgot that you have to use almost $$$k-1$$$ cuts.

I could not pass the pretest 10 as well ;(

If Xor = 0, One cut is enough

If Xor != 0, If there is a solution it always can be done with 2 cuts

Proof: Let X represent XOR of all nodes

If X = 0, it can be done in 1 cut, because, say y represents xor of one component and z represent the other component. Then:

y ^ z = 0

therefore, z = 0 ^ y = y, so the two componnents will have equal xor value

If X!=0, it can be done in 2 cuts. Let x, y, z represent xor of each component after two cuts

x^y^z = X

since all components are supposed to be equal, x = y = z, therefore:

x^x^x = X

x^x^x = (x^x)^x = 0^x = x

x = X

So we should make 3 components with xor value = X

Thank you!

Thanks!

Thanks!

Well, I guess your test case is wrong, as it does not meet the constraints specified for the weight of the node, which was greater than 1 and thus cannot be 0.