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

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

These problems were found in gym. I don't have access to other's solutions and there is no editorial for these problems. So can anyone please help ?

K. Parabolic sorting : https://mirror.codeforces.com/gym/102780/problem/K
F. A word game : https://mirror.codeforces.com/gym/102780/problem/F

  • Проголосовать: нравится
  • +19
  • Проголосовать: не нравится

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

I remember there is a coach mode in gym using which we can see all the solutions but there is some rating requirement for that which i don't know , so you can ask someone high rated to open the solutions and send them to you.(I know this answer is not of much help but if no one helps you in solving the problem you can use this option :) ).

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

    Yeah, coach mode is for 1900+. I actually have seen the solution for K on some chinese blog, but couldn't understand why it worked.

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      Solution for K and F

      Credits to CrescentRose

      These solutions seem clean to me, I haven't read the problems or anything though

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

        But, how does it work? Can you give some explanation please?

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

          Sorry, I just thought you needed some reference to go off of so I got the solutions from coach mode. I'm pretty busy now so I can't really help (or probably wouldn't be able to).

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

Just off the top of my head, F seems like some modified nim game (which i don't really have much knowledge on).

For K, it is easy to see that the smallest element will indicate some "turning" point (decreasing before, increasing after), so you just need to check the min number of moves needed to sort the left and right halves (which can be done using a segment / fenwick tree) for each position, and there are only N places the smallest element can go.

(Sorry for being a bit too short...)

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

I've just solved Problem F. I used Sprague-Grundy Theorem related to Simple Nim Game. I've created piles from number of each letters in the string. Then, I had restricted moves in this game: take 1, 2 or whole pile.

If I run Grundy on this problem it will pass, cause of small constraints, but if you will print out all values of Grundy function, you will see repeated sequence of 1, 2, 3, where only 0th element differs (Grundy(0) = 0).

Solution

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

K is same as this problem with order of the two parts swapped : Pyramid Array.

You can notice that in any valid ordering the maximum element will occur at either the leftmost index or the rightmost index. You should move it (by swaps) to whichever of those two indexes is closer to its original index (breaking ties arbitrarily). The order of remaining elements in the array remains unchanged so now we just have to solve the same problem but with one less element. Now, we just have to find out how many indexes less than a given index are present in the current array. This can be easily done with a fenwick/segment tree by storing 1 at each position and replacing it with 0 when the element occurring at that index is moved to the end.

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

    Oh, I should really complete solving CSES XD. Thanks a lot for your answer. :)