### ko_osaga's blog

By ko_osaga, history, 3 years ago,

Update 2019/06/12: Me and MikeMirzayanov managed to upload the Div.2 contest into Gym. Huge thanks him for the great system, and also a kind help!

However, I decided not to just open it, but to give a training contest. The contest is scheduled in June 14 Friday, 09:00 UTC. Even considering some obvious bias from the setter, I'm personally very proud of the Div.2 contest :D I hope you participate and share the same joy with us! (and of course, please don't cheat!)

.

.

.

.

.

.

.

.

Update 2019/06/05: I managed to upload the Div.1 contest into Gym. Have fun! https://codeforces.com/gym/102201

Open Cup GP of Daejeon is scheduled at 2019/05/05 Sunday, 11:00 MSK. Daejeon is a city where KAIST is.

Division 1 problem set is identical with MIPT PreFinals Camp 2019 Day 6. It was held on March 15.

Division 2 problem set is identical with KAIST RUN Spring Contest 2019. It was held on May 1 locally. Like last year, it was an IOI-style contest, but as we are doing in OpenCup, subtask will be disabled. Some problems between Div1 and Div2 are shared.

Problems were created by ainta, _menhera, ko_osaga, kriii, kdh9949. Some problems in Div1 were borrowed by Diuven, imeimi.

Problems were tested by arknave, dotorya, Namnamseo, tzuyu_chou, .o..

List of relevant previous contests:

Enjoy!

• +88

 » 3 years ago, # |   0 Who all can participate? How can i request for Login authorization?
•  » » 3 years ago, # ^ |   -24 You will solve 0 anyway, it is for 2000+
•  » » » 3 years ago, # ^ |   -63 I request CF community to think before replying such harsh comments! It hurts and some of us are here just to learn and not think about ratings! I am sure CF community will show their support by downvoting the deserving comment! Peace!
•  » » » » 3 years ago, # ^ |   +87 You don't have to think about rating to have one. He just said that this contest is too hard for you, and this is absolutely true.
•  » » » » » 3 years ago, # ^ |   +2 I agree with him and you as well but his comment was not required in the first place. Hope you agree on this atleast. And there is always a human way of saying the truth without hurting someone. :)
 » 3 years ago, # | ← Rev. 2 →   0 I got TLE in J using bipartite matching (O(√N*M)). Is there any faster solution or was my implementation too slow?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +10 My Kuhn works in 444ms, lol.
•  » » » 3 years ago, # ^ |   0 Thank you. I copied your implementation of bipartite matching and got OK...I tried also this but it was too slow too. I'm interested in library codes of people who got AC in J in the contest.
•  » » 3 years ago, # ^ |   +10 The intended solution also uses $O(E\sqrt V)$ bipartite matching. My solution runs in 420ms out of 3s.
•  » » 3 years ago, # ^ |   0 Did you solve whole problem with flow or search for matching of size n-1, and than full solution without flow? Solving second part with flow too shouldn't work.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 I used just bipartite matching and construct answer based on it like as the intended solution. This is my TLE source code. My maxflow library is not optimized for matching and the graph has 2N+M edges. Besides, the graph is held in linked list. I guess these are one of causes of TLE.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +10 https://codeforces.com/blog/entry/17023The article is in Russian, but you can try Google Translate and also it contains the key part of the source code.I googled it using the words "codeforces, burunduk, Kuhn" because I remembered that a fast implementation by Burunduk1 exists that everybody use when I struggle with Dinic.
•  » » » 3 years ago, # ^ |   +8 Thank you. I didn't know that article. It was easy to understand for also non-Russian speaker :)I tried to use BFS instead of DFS in Kuhn and it became faster. Then I changed it to multi-source BFS, it became faster more. codestruct BipartiteMatching { vector pre, root; vector> to; vector p, q; int n, m; BipartiteMatching(int n, int m):pre(n,-1),root(n,-1),to(n),p(n,-1),q(m,-1),n(n),m(m){} void add(int a, int b) { to[a].push_back(b);} int solve() { int res = 0; bool upd = true; while (upd) { upd = false; queue s; for (int i = 0; i < n; ++i) { if (!~p[i]) { root[i] = i; s.push(i); } } while (!s.empty()) { int v = s.front(); s.pop(); if (~p[root[v]]) continue; for (int i = 0; i < (int)to[v].size(); ++i) { int u = to[v][i]; if (!~q[u]) { while (~u) { q[u] = v; swap(p[v],u); v = pre[v]; } upd = true; ++res; break; } u = q[u]; if (~pre[u]) continue; pre[u] = v; root[u] = root[v]; s.push(u); } } if (upd) fill(pre.begin(),pre.end(),-1), fill(root.begin(),root.end(),-1); } return res; } }; It looks close to dinic so I'm not sure but I think It could be $O(\sqrt{V} E)$.
 » 3 years ago, # | ← Rev. 2 →   +34 Thanks for the participation!Problemsetter: ko_osaga (Div1 BCDI, Div2 A) ainta (Div1 AGJ, Div2 B) _menhera (Div2 C) kriii (Div1 E) kdh9949 (Div2 E) imeimi (Div1 H) Diuven (Div1 F) Solution for Div2We also know that solutions are poorly written, sorry :( Thanks to xuanquang1999 for pointing out critical typos in Div2B solution.
•  » » 3 years ago, # ^ |   +37 Btw, I think this beautiful Voronoi Diagrams by _menhera deserves some attention, so I'll leave it here. This is used in Div2 problem set.
 » 3 years ago, # |   +1 Would the problem set be available in Codeforces gym later?
•  » » 3 years ago, # ^ |   +30 Well, I'll try that in this week.
•  » » » 3 years ago, # ^ |   0 Oh, thanks :)
•  » » » » 3 years ago, # ^ |   +8 Div1 is here https://codeforces.com/gym/102201
 » 3 years ago, # |   +11 Where do these contests take place?Is there an email address that I can contact for creating a sector?I tried messaging snarknews but his last visit was 2 weeks ago.
 » 3 years ago, # |   +8 How to solve C and I? I assumed C is some dp over components of two-connectivity and parity of cycles, but did not come to the final solution.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +8 C: The solution in pdf is written by Endagorion, so it might differ with my intended solution.For a permutation $p$ to contribute to the determinant, $(i, p_i) \in E(G)$ for all $i$. This means $p$ should cover all vertices with the collection of edges and cycles. If it's a cycle, it should correspond to some biconnected component in cactus. So you can run DP on each BCC, where you can decide whether you cover a cycle, or not.There is a catch, because every permutation actually contributes to the answer by $inv(p)$ mod 2. However, it is equal to the number of even cycle in the permutation $p$ mod 2. So if you add matchings or even cycles, negate it.
•  » » » 3 years ago, # ^ |   0 Thank you very much for your explanation! P.S. I somehow missed the post with the editorial, now I see :)
 » 3 years ago, # | ← Rev. 4 →   0 We solved E (7 minutes after the end) using a bit different (maybe equivalent?) approach rather than the mentioned one in the editorial.First, find the partition for N lunches and N dinners (sort by lunch-dinner difference). Second, solve problems in decreasing order of sizes (from N-1 to 1) using the solution for the previous one.At each step there are three possibilities: Remove two heaviest dinners and move the lunch with smallest difference to dinners Remove two heaviest lunches and move the dinner with smallest difference to lunches Remove the heaviest lunch and the heaviest dinner We used the same 4 mentioned sets from the editorial to do it in $O(N \log N)$.P.S. it looks that the solutions are dual, but I can't prove it :)
•  » » 3 years ago, # ^ |   +8 I think it's same, just the difference of removing or inserting?
•  » » » 3 years ago, # ^ |   0 True, it uses path shortening instead of augmenting it.
 » 3 years ago, # |   0 Auto comment: topic has been updated by ko_osaga (previous revision, new revision, compare).
 » 3 years ago, # |   0 Auto comment: topic has been updated by ko_osaga (previous revision, new revision, compare).
 » 3 years ago, # |   0 "Some problems between Div1 and Div2 are shared."So who have seen the Div1 problemset should not participate in the Div2 contest?
•  » » 3 years ago, # ^ |   0 As you pointed out, some problems from Div1 will appear. Just like virtual participation, please do not participate if you know the hints or solution of the problem!
 » 3 years ago, # |   0 30 minutes left~
 » 3 years ago, # | ← Rev. 2 →   0 For B, I think the answer is always $1$ or $2$. The former case is trivial to detect. For the later case, I thought about choosing random $100$ vertices and then check each of them in $O(n^2 / 64)$ using bitset. But seeing how many submission get TLE, I don't think this solution is correct.UPD: I have just read the solution for B, but I think there are some typo in the proof.
•  » » 3 years ago, # ^ |   0 There were some "heuristics" which sampled 100 vertices with the highest outdegree and passed. :) We tested all kind of $O(n^3/64)$ and didn't manage to make it work, AFAIR.By the way, I really liked problem B. It's my favorite along with problem I. Hope you liked it too.
•  » » » 3 years ago, # ^ |   0 I liked problem B, even though I spent about 2 hours on it and still cannot come up with the intended solution.Btw, how did you generate testcases against brute-force solution that iterate through student in random order?
•  » » » » 3 years ago, # ^ |   0 Yeah, we thought it was the second easiest problem, but it was one of the game-changers in the onsite round... It's always hard to estimate difficulties of ad-hoc type problems.
•  » » » » 3 years ago, # ^ |   0 Thank you for enjoying problem B! At first, the test data was very weak. But _menhera and other setters found out some heuristics and I was able to make counterexample for those solutions.
 » 3 years ago, # |   0 From Problem A editorial: Observe that, A+=A is equivalent to B/= 2, and vice versa... Why is this true?
•  » » 3 years ago, # ^ |   0 Roughly speaking, we are only interested in the ratio A/B.