pritishn's blog

By pritishn, 3 years ago, In English

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://codeforces.com/gym/102780/problem/K
F. A word game : https://codeforces.com/gym/102780/problem/F

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

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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 :) ).

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

    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.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      Solution for K and F

      Credits to CrescentRose

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

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

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

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +30 Vote: I do not like it

          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).

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

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...)

»
3 years ago, # |
Rev. 2   Vote: I like it +33 Vote: I do not like it

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

»
3 years ago, # |
Rev. 2   Vote: I like it +35 Vote: I do not like it

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.

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

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