### ko_osaga's blog

By ko_osaga, history, 23 months ago,

Hello!

XXII Open Cup. Grand Prix of Seoul will be held in 2022/07/17 Sunday, 17:00 KST (UTC+9).

The contest was used as a Day 2 Contest for ByteDance Summer Camp 2022.

Problems were authored by jh05013, molamola., jihoon, ainta, pichulia, chaeyihwan, evenharder, TLEwpdus, applist, Cauchy_Function.

Special thanks to myself for translating the statements and editorials.

Enjoy!

• +136

 » 23 months ago, # |   +10 Ready to get destroyed by data structures and cacti.
 » 23 months ago, # |   0 Could you please provide the link to the contest?
•  » » 23 months ago, # ^ |   +20 link (it says unofficial, but it is actually official)
•  » » » 23 months ago, # ^ |   0 Thanks!
 » 23 months ago, # |   +6 Thanks for the exciting contest! How to solve M and F?
•  » » 23 months ago, # ^ |   0 M: notice that if we replace min by max, then this is L_{\inf} distance, and it's equivalent to the Manhattan distance after rotating everything by 45 degrees. And for Manhattan distance, the sum separates into two sums that can be computed straightforwardly.And then we notice that min+max=sum, so we can subtract the above from the sum of sums (which is again finding the sum of Manhattan distances, but without rotating by 45).
•  » » » 23 months ago, # ^ |   0 Wow, thank you for such an amazing explanation with observations Petr !
•  » » 23 months ago, # ^ | ← Rev. 2 →   0 F: notice that in a group of consecutive stones of the same color, we can get at most one weight, and we can get no weights from the first and last groups. It turns out that we can always get any ceil(k/2) maximum weights from k non-first-and-non-last groups (because we can always find a group that we want adjacent to a group that we don't want, and remove both).
•  » » » 23 months ago, # ^ |   0 I got it. I haven't seen that observation. Thank you again Petr !
 » 23 months ago, # |   +16 Seems the contest has been finished.It's my favorite set in the ByteDance Camp 2022. Really enjoyed problem B, G, I and L. Thanks to the author!
 » 23 months ago, # |   +8 Could someone share a solution code for L? I tried to upsolve it in the ByteCamp but failed. My solution has the same complexity as the model one but it keeps getting TLE.
•  » » 23 months ago, # ^ |   +8 Here's my code, 2.8/3s :) (I've removed includes and modint from ACL to make it smaller) Code#define sz(v) ((int)(v).size()) #define all(v) (v).begin(),(v).end() using namespace std; typedef int64_t int64; typedef pair ii; int MAX_JUMP = 18; using mint = atcoder::modint1000000007; const mint base = 31373137; const int INF = (int) 1e9; struct Jump { int dest; mint hash; }; class LMakeDifferent { public: void solveOne() { int n, q; cin >> n >> q; vector t(n); for (auto& x : t) cin >> x; vector tr = t; reverse(all(tr)); vector basePow(MAX_JUMP); basePow[0] = base; for (int i = 1; i < MAX_JUMP; ++i) basePow[i] = basePow[i - 1] * basePow[i - 1]; auto computeSingle = [&](vector t) -> vector { vector backwards(n, 0); for (int i = 0; i < n; ++i) if (t[i] == 2 && backwards[i] == 0) { int j = i; int steps = 0; while (steps < n + 1 && t[j] == 2 && backwards[j] == 0) { j = (j + n - 2) % n; ++steps; } if (steps == n + 1) { j = i; for (int u = 0; u < steps; ++u) { backwards[j] = INF; j = (j + n - 2) % n; } } else { for (int u = 0; u < steps; ++u) { int nj = (j + 2) % n; backwards[nj] = 1 + backwards[j]; j = nj; } } assert(backwards[i] > 0); } vector res(n); for (int i = 0; i < n; ++i) { if (t[i] == 1) { res[i].dest = (i + 1) % n; int j = (i + n - 1) % n; res[i].hash = backwards[j] + 1; } else { res[i].dest = (i + 2) % n; res[i].hash = 0; } } return res; }; auto duplicate = [&](int stage, const vector& ju) -> vector { vector res(n); for (int i = 0; i < n; ++i) { Jump j1 = ju[i]; Jump j2 = ju[j1.dest]; res[i].dest = j2.dest; res[i].hash = j1.hash + basePow[stage] * j2.hash; } return res; }; vector> direct; vector> reverse; direct.push_back(computeSingle(t)); reverse.push_back(computeSingle(tr)); for (int i = 1; i < MAX_JUMP; ++i) { direct.push_back(duplicate(i - 1, direct.back())); reverse.push_back(duplicate(i - 1, reverse.back())); } auto findNextDiff = [&](const vector>& direct, int p1, int p2) -> tuple { if (direct.back()[p1].hash == direct.back()[p2].hash) return {INF, -1, -1, -1, -1}; int when = 0; for (int j = MAX_JUMP - 1; j >= 0; --j) { if (direct[j][p1].hash == direct[j][p2].hash) { when += 1 << j; p1 = direct[j][p1].dest; p2 = direct[j][p2].dest; } } return {when, p1, p2, direct[0][p1].hash.val(), direct[0][p2].hash.val()}; }; auto handleDirection = [&](const vector>& direct, int p1, int p2) -> int { int res = INF; int offset = 0; for (int step = 0; step < MAX_JUMP; ++step) { auto[when, np1, np2, w1, w2] = findNextDiff(direct, p1, p2); if (when >= INF) return res; if (w1 == 0 || w2 == 0) { res = min(res, offset + when); } else { res = min(res, offset + when + min(w1, w2)); } offset += when + 1; p1 = direct[0][np1].dest; p2 = direct[0][np2].dest; } return res; }; for (int qi = 0; qi < q; ++qi) { int p1, p2; cin >> p1 >> p2; --p1; --p2; int res = min(handleDirection(direct, p1, p2), handleDirection(reverse, n - 1 - p1, n - 1 - p2)); if (res >= INF) res = -1; cout << res << "\n"; } } void solve() { int nt = 1; for (int it = 0; it < nt; ++it) { // cout << "Case #" << (it + 1) << ": "; solveOne(); } } }; // #define st_mtimespec st_mtim int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); LMakeDifferent solver; solver.solve(); return 0; } 
•  » » » 23 months ago, # ^ |   0 Thanks!
•  » » » » 23 months ago, # ^ |   0 Just sped it up to 0.3s with the following diff: - for (int step = 0; step < MAX_JUMP; ++step) { + while (offset < res) { 
•  » » » » » 23 months ago, # ^ |   +28 Note that you can also shave off a log factor entirely.Instead of using jump pointers with binary search, we can build a suffix array and query LCP in linear time. I'm not sure of it's possible to build a suffix array on a tree in linear time (I think DC3/SAIS might still work?), but instead we can also observe that this functional graph consists of only a single large cycle with paths of the form $22\ldots22$ or $22\ldots21$ hanging off of it. Thus, we can handle those paths in a special case, and build a suffix array on just the cycle (doubled). Together with linear-time RMQ to query LCP efficiently, this gives an $O(N + Q \log N)$ solution.
•  » » 23 months ago, # ^ |   0 Hi, I uploaded the tester's solutions to the Gym. They should have no TL issues in Yandex, I think.
•  » » 23 months ago, # ^ |   +66 I believe L also could be solved in $O((n + q) \log n)$ for any graph, not a specific one given in this task.It is somewhat similar to DFA minimization algorithm. Let's first split all vertices into two groups by color. Then do at most $n$ iterations of splitting groups into smaller ones. We can maintain the property that after $k$ iterations two vertices are in the same group iff they cannot be distinguished by $k$ moves.Naively on each iteration, we can split vertices into new groups by key (current group id, [current group id of the $i$-th children of current vertex] for all $i$).But it can be done in a lazy way. We could recalculate the group for a vertex only if one of its child groups changed in the previous step. Also, we can apply optimization — if, on some step we want to move more than half of the vertices of some group to the same new group, we can leave them in the current group, and move others. This way every time a vertex is moved to another group, group size is reduced at least by a factor of two, so each vertex is moved at most $O(\log n)$ times. Here is my implementation: 164708181, it is $O(n \log^2 n)$ because it uses sets to maintain groups, but it can be easily optimized to $O(n \log n)$.
 » 23 months ago, # |   0 Hyeong ko_osaga, can you share the test cases?
 » 23 months ago, # |   0 What was the approach for problem M?
 » 23 months ago, # |   0 Is there any editorial? Or plz someone give me solution of I.
 » 23 months ago, # | ← Rev. 2 →   +3 Indeed, thanks for the amazing round!How to solve B and K?
•  » » 23 months ago, # ^ | ← Rev. 2 →   +18 K: For a board, if $n,m\ge 2$ you delete the last column and the last row, and delete empty columns and rows at the same time, it will be the same as the original board. That's because if one player move the piece to the last column or the last row, the opposite can do $\ge 1$ operations.If every board has $n=1$ or $m=1$, the answer can be get easily.
 » 23 months ago, # | ← Rev. 2 →   +11 I enjoyed this contest very much, thanks for round!Solving some problems were helped by AtCoder's past problems
 » 23 months ago, # |   +62 Thank you for the participation!EditorialGym
 » 23 months ago, # | ← Rev. 3 →   0 Btw anyone knows how to import Ghosts from Yandex Standings? Wow, now I know how
 » 23 months ago, # |   +10 The solution to the problem K in the editorial is very cool in its simplicity and integrity. I did not want to think in such manner and applied some theory I know. Interestingly enough, what I obtained is a seemingly other solution. The editorial solution should imply that mine can be simplified further, but here is what I implemented. My solution of problem KCall the player who moves horizontally Left and the other guy Right. Each cell of each board corresponds to the game with one chip initially standing on this cell, and this game is a surreal number. One may refer to the (classical) book of J. H. Conway "On Numbers and Games".More specifically, let $x$ be the game corresponding to the cell just to the right of us, and $y$ be the game corresponding to the cell just below our cell. Then the game in our cell is denoted by $\lbrace x\mid y \rbrace$ and means that Left can only go to the game (or state) $x$, and Right can only go to $y$. Note that this should explain the choice of names Left and Right: Left can only proceed to the states to the left of the bar, and Right can only go to the states to the right. If one of these neighbor cells does not exist, then this state is denoted by something like $\lbrace\mid y\rbrace$. If $x$ and $y$ are numbers, then $\lbrace x\mid y\rbrace$ is the simplest number $z$ for which the inequalities $x < z < y$ hold.It turns out that all these games correspond to integer surreal numbers, and therefore simplest means "closest to 0". In other word, we can calculate the state in a cell using this pseudocode: x = dp[i][j + 1] or -infinity y = dp[i + 1][j] or +infinity if (0 <= x) dp[i][j] = x + 1 elif (y <= 0) dp[i][j] = y - 1 else dp[i][j] = 0 An informal meaning of a game being equal to number $n$ is that Left has a handicap of $n$ moves in this game: if $n = 0$, then nobody has an advantage over the other player, and whoever goes first runs out of moves before the other player. If $n > 0$, then Left can make $n$ moves before the game begins, and then whoever goes first loses. If $n < 0$, then actually Right can make $-n$ moves to make the game losing for the first player.It follows from the intuition that in several games the winner is determined by the sum of the numbers corresponding to these games. In general, games may be non-integer surreal numbers, irrational, infinitesimal or even not a surreal number (for example, a game where the first player always wins). In particular, there is a game with value $1/2$, and this means that Left has a handicap of half of a move. If we take two copies of this game and one game with value $-1$, then the sum of these three games is losing for anyone who goes first. Also, the definition of simplest number is not always "closest to 0"; for example, $1/2$ is considered to be the simplest number between $0$ and $1$. Again, refer to ONAG if you want proofs, it is indeed some interesting stuff.In this problem, however, it can be seen that all cells of each board correspond to integers, and we can calculate them in $O(sz)$ where $sz$ is the size of the board. This is too slow.To speed this up, we may notice that the value in each row can be divided into several arithmetic progressions, and each row can be recalculated from the one below it in $O(n + m)$. I will not dig into the details here, though it took time to figure this out during the contest.
•  » » 23 months ago, # ^ |   +18 I also did all of that (on paper), but I didn't believe I would be able to implement that, so I found a simplification:I was going through (anti-)diagonals instead of rows, there we also have several arithmetic progressions with step 2. There will be one arithmetic progression (I called them segments) which is closest to 0, it will become wider with time, while other segments will shrink (at least on the side closer to the "main" segment). In terms of the initial picture the main segment covered some upper-left part of the plane, while segments below it covered some segments of rows (below that upper-left part) and segments above covered some segments of columns (to the right of that upper-left part). But since we are only interested in the value in the top-left corner, all the areas except for the main upper-left part are not interesting to us! Thus we can ignore all the segments except the main one. Moreover, new segments can only appear when some cell doesn't have the neighbour to the right or below AND the value we would assign there normally is not correct, but in this case we will assign 0 to this cell, which means that this cell will become the corner of the new main zone. In the end the solution is very simple: traverse both borders, maintain the current corner of the main zone, if encounter a cell with only one neighbour which would have incorrect value, make it the new corner of the main zone.
•  » » » 23 months ago, # ^ |   0 I think I implemented a similar but different solution. I traversed by rows from bottom to top and keep only the leftmost surreal number in each row.When we go up, if the left border stays the same we simply minus 1 (the cells on the right won't affect the value), otherwise in the top-left adjacent cell we plus one and max with zero (no cell under it) and for the cells on the left we plus 1 in each step. This is not exactly correct since the existence of right border (rightmost value is at most 0) so we need to cap it with the length of that row.If this sounds impossible to comprehend here's the code: int w=1,o=m; for(int i=n;i>=1;--i) { // suppose the i-th row is from L~R --w; // walk up if(o!=L) { w=max(w+1,0); // walk one more step left w+=o-L-1; // then the remaining lefts o=L; } w=min(w,R-L); // cap with the right border } 
 » 23 months ago, # |   0 Why ML in problem I is 32mb?
•  » » 23 months ago, # ^ |   +3 This is to guarantee that simplex would MLE.No reference solutions are close to 32MB ML, my tester solution came in under 4MB and I think only one tester had a solution above 8MB.
•  » » » 23 months ago, # ^ |   0 Hm, interesting. Do you have a solution using simplex? If so, could you please explain, why simplex will return an integer solution and why it would fit into the time limit?
•  » » » » 23 months ago, # ^ |   +8 There are MLE simplex solutions that were prepared, this is not a theoretical exercise. Since the intended solution wasn't simplex, and the intended solution comfortably fits in the claimed ML, there should be no issues, right?
•  » » » » » 23 months ago, # ^ |   0 Of course, it is not theoretical problem. I'm just interested in the fact that the is a solution with simplex which moreover returns the integer solution, wow)