TheScrasse's blog

Unofficial hints for Codeforces Round #682 (Div. 2) (A — D)
By TheScrasse, history, 4 years ago, In English

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.

  • Vote: I like it
  • +34
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it
Hint for F
→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

I like the way you expressed nested hints, thanks for it :)

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/blog/entry/84500?#comment-720707

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A great initiative. It will be great if we can see more of such posts for further contests. Helps in upsolving.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why rating not changed for codeforces round #682(div2)

→ Reply