### TheScrasse's blog

By TheScrasse, history, 3 years ago,

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

1438C - Engineer Artem

Hint 1

1438D - Powerful Ksenia

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.

• +34

| Write comment?
 » 3 years ago, # | ← Rev. 2 →   +5 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.
 » 3 years ago, # |   +18 Hint for FConsider 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?
 » 3 years ago, # | ← Rev. 2 →   +8 I like the way you expressed nested hints, thanks for it :)
 » 3 years ago, # |   0
 » 3 years ago, # |   0 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
 » 3 years ago, # | ← Rev. 2 →   0 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.
•  » » 3 years ago, # ^ |   0 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.
 » 3 years ago, # |   0 A great initiative. It will be great if we can see more of such posts for further contests. Helps in upsolving.
 » 3 years ago, # |   0 why rating not changed for codeforces round #682(div2)
•  » » 3 years ago, # ^ |   0 They announced that it is unrated mid contest.