As promised, here are some (nested) hints for Codeforces Round #682 (Div. 2).
1438A - Specific Tastes of Andre
Hint 1
1438B - Valerii Against Everyone
Hint 1
Hint 1
Hint 1
I wasn't able to solve E and F. If you did, you may want to add your hints in the comments.
Also, please send a feedback if the hints are unclear or if they spoil the solution too much.
In E, you can notice that the sum {a[l + 1] ... a[r — 1]} is increasing and if we assume that a[l] < a[r] (the opposite case will be considered when reverse the array), then a[l] ^ a[r] <= 2 * a[r]. This means that the count of good subarrays is not too big. Therefore, we can count all good subarrays.
Consider repeatedly querying three random nodes, keeping track of the frequencies of the responses to the queries. Which nodes would you expect to appear most frequently? How can you use this information to determine the root?
I like the way you expressed nested hints, thanks for it :)
https://codeforces.net/blog/entry/84500?#comment-720707
The way you expressed hints is quite good. But at problem C, my code gives correct ans for your hint's input but it fails at system test (pretest actually). May be hints of C can be improve. Here is my solution: 98304939
In problem D, "The xor of all the array remains constant". I can feel this but can't prove. :( . Can you give me the proof plz? Actually, I can feel and simulate, but can't prove in satisfied way.
When you xor three values, then for a given position, if there are an odd number of 1 bits, then they will be replaced with three 1 bits, and if there are an even number of 1 bits, they will be replaced with zero 1 bits. Since xor is solely based on parity, the xor remains constant.
Got the point. Thanks.
A great initiative. It will be great if we can see more of such posts for further contests. Helps in upsolving.
why rating not changed for codeforces round #682(div2)
They announced that it is unrated mid contest.