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.net/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, Konijntje, 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!
Who all can participate? How can i request for Login authorization?
You will solve 0 anyway, it is for 2000+
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!
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.
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. :)
I got TLE in J using bipartite matching (O(√N*M)). Is there any faster solution or was my implementation too slow?
My Kuhn works in 444ms, lol.
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.
The intended solution also uses $$$O(E\sqrt V)$$$ bipartite matching. My solution runs in 420ms out of 3s.
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.
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.
https://codeforces.net/blog/entry/17023
The 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.
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.
It looks close to dinic so I'm not sure but I think It could be $$$O(\sqrt{V} E)$$$.
Thanks for the participation!
Problemsetter:
Solution for Div1
Solution for Div2
We also know that solutions are poorly written, sorry :( Thanks to xuanquang1999 for pointing out critical typos in Div2B solution.
Btw, I think this beautiful Voronoi Diagrams by Konijntje deserves some attention, so I'll leave it here. This is used in Div2 problem set.
Would the problem set be available in Codeforces gym later?
Well, I'll try that in this week.
Oh, thanks :)
Div1 is here https://codeforces.net/gym/102201
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.
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.
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.
Thank you very much for your explanation!
P.S. I somehow missed the post with the editorial, now I see :)
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 :)
I think it's same, just the difference of removing or inserting?
True, it uses path shortening instead of augmenting it.
Auto comment: topic has been updated by ko_osaga (previous revision, new revision, compare).
Auto comment: topic has been updated by ko_osaga (previous revision, new revision, compare).
"Some problems between Div1 and Div2 are shared."
So who have seen the Div1 problemset should not participate in the Div2 contest?
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!
30 minutes left~
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.
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.
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?
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.
Strongest generator.
Thank you for enjoying problem B! At first, the test data was very weak. But Konijntje and other setters found out some heuristics and I was able to make counterexample for those solutions.
From Problem A editorial:
Why is this true?
Roughly speaking, we are only interested in the ratio A/B.