When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

ko_osaga's blog

By ko_osaga, history, 3 years ago, In English

Hello!

I uploaded 2020 Petrozavodsk Summer Camp, Korean Contest to the CF Gym. It is a collection of Korean problems per the request of snarknews.

Problems are collected from:

  • UCPC 2020 (Local ICPC Contest. 2019 version was used in XX Open Cup. GP of Korea)
  • Semi-Game Cup (Contest authored by Seoul Science High School students. YeongTree is selected to IOI 2021 Korea team)
  • IOI 2020 Korean TST (Problem B)
  • Random educational problem from rkm0959

Problems are authored by:

And unfortunately there are no editorials.

List of relevant previous contests:

Enjoy!

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

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

seems that it is not available now :(

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

    Oops, I forgot to make it public. Thanks for the heads up.

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

It should be noted that test cases for K is a bit weak... Sorry about that.

While there are no editorials, I have an explanation for K in Korean. See here.

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

Many thanks for sharing it!

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

How to solve E?

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

    Let S denote the set of squares with no guards installed among the squares of k*k that are completely contained within the plate.

    If there is an intersection of the squares belonging to S, the game is over by placing a guard in that place, so you should not hand over such a situation.

    Imagine that there is no current intersection of S. At this point, we can unconditionally choose two squares that do not overlap each other.

    All you have to do is drop the guard in the remaining space of the two squares which are not overlap each other than your opponent will never win unless I win

    The number of such cells on the board is nm-2*k*k, so if nm is odd, Yuto can always execute the above strategy, and if the number is even, same for Platina.

    Separately, you have to consider the fact that the first player finishes the first turn.

    I'm sorry for my English skills, and thank you for interest in my problem

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

How to solve F?

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

    Divide and conquer DP optimisation.

    For convenience, add a dummy element to the start and end of the array that we must both miss. Denote by $$$DP[b][k]$$$ the maximum score we can get from the first $$$b$$$ notes, such that we miss $$$k$$$ of them. Denote by $$$Add[a][b]$$$ the amount of score we get if we miss notes $$$a$$$ and $$$b$$$, and hit all notes in between. Then, \begin{equation*} DP[b][k] = \max_{a < b} DP[a][k-1] + Add[a][b]. \end{equation*} Define \begin{equation*} A[b][k] = arg\,max_{a < b — 1} DP[a][k-1] + Add[a][b]. \end{equation*} Then \begin{equation*} DP[b][k] = \max(DP[b-1][k-1], DP[A[b][k]][k-1] + Add[A[b][k]][b] \end{equation*} Thus, we can use divide & conquer optimisation, since $$$A[b][k] \leq A[b+1][k]$$$.

    Code: 110039963

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

      The code link needs authority.

      Could you post code in public platform?QAQ

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

        I tried to put it in spoiler tags, but the spoiler didn't work for some reason. But now it does. Oh well.

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

      Thanks a lot!

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

How to slove D?

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

    F (I, j) means the number of non decreasing subarrays of [i, j].

    Observation 1: Platina naturally calls L or R.

    Observation 2: Also on this, Yuto will call X where max(f(L, X), f(X, R)) is the minimum.

    Observation 3: For L,R, f(L,X) will be smaller up to a specific position, and f(X,R) will be smaller from a specific position.

    Observation 4: The number called by Yuto by Observation 2 and Observation 3, the smaller one calls one of the two boundaries.

    So our goal is to find that boundary.

    Therefore, it is possible to find the boundary using binary search. To find this boundary once, we have to do it in O(logN), so we have to find F(i,j) in O(1).

    NDSA means non-decreaing subarray. If K consecutively non-decreasing, the number of NDSAs in the zone is k(k+1)/2. Therefore, it can be grouped by these zones as a pretreatment.

    Using the prefix sum, you can get the NDSA in a few areas in the middle, and you only need to add x(x+1)/2 only for parts that do not completely include the area.

    Therefore, it can be solved in O(1), and the whole process can be processed in O(QlgN). I don't know the solution, but there are some people who have solved O(N+Q).

    I'm sorry because I'm late, and thank you for interest in my problem

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?