Блог пользователя TheScrasse

Автор TheScrasse, история, 4 года назад, По-английски

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
  • Проголосовать: не нравится

»
4 года назад, # |
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.

»
4 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится
Hint for F
»
4 года назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 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

»
4 года назад, # |
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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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