### ko_osaga's blog

By ko_osaga, history, 23 months ago, 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! Announcement of 2020-2021 Summer Petrozavodsk Camp, Day 6: Korean Contest Comments (15)
| Write comment?
 » seems that it is not available now :(
•  » » Oops, I forgot to make it public. Thanks for the heads up.
 » 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.
 » Many thanks for sharing it!
 » How to solve E?
•  » » 23 months ago, # ^ | ← Rev. 3 →   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 winThe 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
•  » » » Thank you!
 » How to solve F?
•  » » 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
•  » » » The code link needs authority.Could you post code in public platform?QAQ
•  » » » » I tried to put it in spoiler tags, but the spoiler didn't work for some reason. But now it does. Oh well. code#include using namespace std; using ll = long long; const ll INF = 1e18; const int N = 2000; ll as[N+2]; ll cs[N+1]; ll add[N+2][N+2]; ll dp[N+2][N+2]; void solve(int a, int b, int k, int ia, int ib) { if (a > b) return; int m = (a + b) >> 1; pair best = {-INF, -1}; for (int x = ia; x < min(m-1, ib + 1); ++x) { pair off = {dp[x][k-1] + add[x][m], x}; best = max(best, off); } dp[m][k] = best.first; solve(a, m-1, k, ia, best.second); solve(m+1, b, k, best.second, ib); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, k; ll p; cin >> n >> k >> p; for (int i = 1; i <= n; ++i) cin >> as[i]; for (int i = 1; i <= n; ++i) cin >> cs[i]; for (int a = 0; a+1 <= n; ++a) { add[a][a+1] = 0; for (int b = a+2; b <= n+1; ++b) { add[a][b] = add[a][b-1] + as[b-1] * cs[b-a-1]; if (b == a+2) add[a][b] += p; } } for (int i = 1; i <= n+1; ++i) dp[i] = -INF; for (int t = 1; t <= n+1; ++t) { solve(t+1, n+1, t, t-1, n); for (int i = t; i <= n+1; ++i) dp[i][t] = max(dp[i][t], dp[i-1][t-1]); } ll res = -INF; for (int h = 0; h <= k; ++h) res = max(res, dp[n+1][n-h+1]); cout << res << '\n'; } 
•  » » » Thanks a lot!
 » How to slove D?
•  » » 22 months ago, # ^ | ← Rev. 3 →   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
 » How to solve C?