It is sad that I opened the complete problemset too early, and saw that n=2000 in B(in hacks) , and try hard to optimize my solution from 36 queries to 33, and there weren't clarifications. After a while I noticed that n=1000 in statement, and after I refresh the statement they all become n=1000. It wastes me about ~20min time.

ok thanks

I dont know how TAT

Is D too difficult for a D? The upper bound analysis of this problem makes me think it has the difficulty level of F.

G and https://mirror.codeforces.com/problemset/problem/1887/D are the same problem, except that G is forced online. Change the binary indexed tree of 1887D to a persistent segment tree, then you can get accepted in G.

O(k^2logk) solution for G.

For convenience, we will only consider the round of jumping to the right here. The turn that jumps to the left is symmetrical. If the current jump distance is k0, then for each modulo result of k0, we only need to record the smallest position. Because smaller positions can always jump to larger positions. Next, consider turning at each position. These positions, such as d, d+k0, and d+2k0, must form a cyclic interval in the form of k0-1. What we need to do is to take the maximum value of the cyclic interval for the arithmetic sequence. It can be achieved using a suitable data structure.

Because all remaining cities contribute x twice, this permutation does not affect x's contribution. Put all cities on the number line according to y, and the problem is like you need to walk from a fixed starting point to a fixed ending point on the number line, and then there are several points on the number line that need to be passed through. And y's contribution to the answer is the total distance you have traveled on the number line. This way, it is easy to see that this movement method obtains the shortest distance.

I tried to fix the tags but after I deleted the abnormal tags, they quickly returned.

Problem 1887C is awesome. I really like the idea of 1887C.

EFG are all excellent problems. Failed to solve F because I mistakenly thought that 1<=n<=1e5.

So do I. Should I stop using cin/cout from now on?

I got the idea of F after about 25 minutes, but I tried solving it with dp on tree, ignoring that it can be calculated with bruteforce. I felt into a thinking trap that it must be difficult to implement because it is F.

G2 is almost the same as 2022 ICPC Asia Hangzhou Regional Programming Contest problem I. The only difference is the constraints and input/output format. https://mirror.codeforces.com/gym/104090/problem/I

The interactor of problem D(div2)/B(div1) can be made TLE. Select a case that n>800,add O(n) random x between n/2 and 3n/2, and query n random pairs of nodes.As there are O(n^2) edges in the graph, it takes O(n^3) time for the interactor to answer all the query.

Submission:https://mirror.codeforces.com/contest/1815/submission/201700734

I can't understand why. We take part in contests because we persue the joy of solving problems. Cheating can only be a waste of these awesome problems. ICPC is what we enjoy, not something we must do. If a person doesn't enjoy it, simply, he can refuse to participate and do whatever he likes.

It is really sad to see my verdict of D changed from Accepted to Wrong Answer. Althougt my solution is actually wrong.

Solution A-E

A:read the picture:security

B:note that it is "was it rated". you can find that codeforces round 1 is rated and round 15 is unrated. In the first 25 test,only round 15,20,21 are unrated.

C:t<=32 and sum of n<=155,around t*5, so you can guess that it is n is a random number between 0 to 9. As 2*1*4=8,7=7,1*2*3*5=30, you can guess that n is 31415926... and the answer is the product. the sum of the first 32 digits of pi is also actually equal to 155.

D:there is no limit of n>0.

-7 -> -20 -> -10 ->-5 -> -14 -> -7

E:the difference is 10^6 not 10^-6. if you set a=0,the condition will be always satisfied.

Maybe 2600-2700

This case can hack it.

1

100000

1 49999 1 1 1 1 ...... 49999 1

1809G is similar to 1437F, although the constraint of 1809G is tighter.

If there is a subtree with size sqrt(n)-1 and the depth of its root is divisible by sqrt(n),for one node of a query in the subtree,we will jump at most sqrt(n)-1 times to the root of the subtree,but as the size of subtree is not greater than sqrt(n),this will not be a important node.We have to jump sqrt(n) more times to find another node whose depth is divisible by sqrt(n).The subtree of this node must have at least sqrt(n) nodes.So there must be an important node after 2*sqrt(n)-1 jumps.For the other node,it is the same.So there must be a pair of important nodes after at most 2*sqrt(n)-1 jumps.

It is a custom in programming contests that the hardest problem in a contest should be unsolvable for most contestants,which is used to distinguish top contestants.

Solution of E with block algorithm: Mark every node whose depth is divisible by sqrt(n) and subtree has at least sqrt(n) nodes as important nodes.There are at most sqrt(n) important nodes.for every pair of important nodes whose depth are the same,calculate the answer and store it.As there are at most n pairs of important nodes and for every pair of important nodes,there must be another pair of important nodes after sqrt(n) jumps,the time complexity is O(n*sqrt(n)).For every query,there must be a pair of important nodes after at most 2*sqrt(n)-1 jumps.So the time complexity is O(q*sqrt(n)).

overall time complexity:O((n+q)*sqrt(n)),overall memory complexity:O(n).

code:https://mirror.codeforces.com/contest/1806/submission/197990830

Actually it is common to have a problem harder than 2800 in a div2 contest.

Binary search solution for E.

https://mirror.codeforces.com/contest/1796/submission/195570895

Actually it is not a good idea to use binary search because checking an answer is more difficult than solving it directly with greedy.

Pretest 1 is the sample.Having wrong answer on pretest 1 indicates that your program failed to pass the sample.

It is absolutely unfair,especially for those who solved E but failed to solve F.

1788E and 1667B are similar

There is an easier solution for F.For each element x between 0 and 300000,the contribution of the element is only related to the latest position that x is included in the set,no matter how many times x have appeared in previous sets.It can be proved that if the last set which includes x is the ith set,the contribution of x will be pow(3,i-2)*pow(2,n-i+1),except the 1th set which is pow(3,i-1)*pow(2,n-i) (or pow(2,n-1))

So we can simply use a segment tree to implement interval assignment and solve the problem in O(M+nlogM) time.

Solution -> 176975490

Proof:If there exist m ways of the previous k operations that x is inclueded in the current set,if x is included in the next set,there will be pow(3,k) ways that the next operation is and,creating m sets which include x,there will be pow(3,k) ways that the next operation is or,creating pow(3,k) sets which include x,there will also be pow(3,k) ways that the next operation is xor,creating pow(3,k)-m sets which include x,so the total number of sets which include x will be 2*pow(3,k).It is not related to m.

Otherwise,if x is not included in the next set,if the next operation is and,no set will include x,if the next operation is or,m sets will include x,if the next operation is xor,m sets will include x,so the total number of sets which include x will be m*2.

In conclusion,the total contribution of x is only related to the last position x appeared in the set.

In the testcases where x is negative and odd,x%2 will be -1 but not 1