Qingyu's blog

The 1st Universal Cup. Stage 6: Taiwan
By Qingyu, 20 months ago, In English

Hello Codeforces! The 6th Stage of the 1st Universal Cup is coming. It will be held from Mar 4th to 5th.

The contest is based on an official ICPC Asia Pacific regional contest. It has been used in the 2022 ICPC Asia Taoyuan Regional Programming Contest, which was held on November 19, 2022 — November 21, 2022. Thanks to the judges and authors for preparing this great contest and sharing with us as a Universal Cup Stage.

As usual, we have three time windows for participating. You can participate in the contest in the following three time windows:

  • Mar 4th 13:00 — 18:00 (UTC +8)
  • Mar 4th 19:00 — 24:00 (UTC +8)
  • Mar 5th 02:00 — 07:00 (UTC +8)

Please note that you can see two scoreboards in DOMjudge. The 'Local Scoreboard' shows the standings ONLY IN THE CURRENT TIME WINDOW. And the 'Combined Scoreboard' shows all participants, including the onsite participants, and the cup participants in the previous time windows.

Contest link: https://domjudge.qoj.ac/

Universal Cup Scoreboard: https://qoj.ac/ucup/scoreboard

About Universal Cup:

Universal Cup is a non-profit organization dedicated to providing trainings for competitive programming teams. Up to now, there are more than 500 teams from all over the world registering for Universal Cup.

A more detailed introduction: https://codeforces.me/blog/entry/111672

Register a new team: https://ucup.ac/register (the registration request will be processed before each stage)

Results of the past stages: https://ucup.ac/results

Terms: https://ucup.ac/terms

Ratings: https://ucup.ac/rating

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

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

Can someone give some idea for problem H? How to find the optimal cut while calculating a particular DP[K][N] in O(1) as the editorial says?

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

    This is how we did it.

    Let's look at $$$O(N*N*K)$$$ dp solution.
    $$$dp[k][i] = min(dp[k][i], dp[k-1][j-1]+cost(j,N))$$$ for all $$$i<j<=N$$$

    Create a helper array where $$$changes[i]$$$ contains all $$$i<j$$$ such that $$$cost(i,j-1) \neq cost(i,j)$$$. The updated dp states are -
    $$$dp[k][i] = min(dp[k][i], dp[k-1][j-1]+cost(j,N))$$$ for all $$$j$$$ present in $$$changes[i]$$$.

    Editorial claims that sizes of these $$$changes[i]$$$ array is $$$O(1)$$$ because of random inputs. I do not have any rigorous proof for this claim.

    → Reply