By Anadi, history, 2 months ago, ,

XX Open Cup Grand Prix of Wrocław takes place on Sunday, March 29, 2020 at 10:00 CEST.

Link to the contest (you need an Open Cup login to participate).

The round is based on local competitions organized in 2018 and 2019 in Wrocław. Tasks were invented, prepared and translated by gawry, bardek, Arti1990, Rafiki53, Skedar, koratel, Kreyyy, Łukasz Zatorski, Arblash, yarek, MicGor, Maciektoja, w0nsh, kobor, Fly_37 and me.

Good luck!

UPD: There was a wrong time written at the beginning! I got confused because of the time change in Poland and I am deeply sorry about that.

UPD: Editorial

• +168

 » 2 months ago, # | ← Rev. 2 →   +7 did anybody get 'check failed' on C?(div2) i wrote that https://pastebin.com/kdEXLgvV wasnt able to submit my solution
 » 2 months ago, # |   -19
•  » » 2 months ago, # ^ |   +43 All problems were taken from competitions organized in Wrocław (G was proposed in 2018). We didn't notice that it appeared on AtCoder.
•  » » 2 months ago, # ^ |   +63 Well, "was taken from xyz" is actually much stronger statement that "appeared before in xyz", so I would like to stress that it originally appeared before that AtCoder was held. Some Polish contestants during that AtCoder already knew that problem from contest in Wrocław. Unfortunately it seems that this set of people didn't contain any guys from Wrocław...
 » 2 months ago, # |   +13
•  » » 2 months ago, # ^ |   +59 Not really. They say something about solving for all sinks, but do not provide an algorithm.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 I'm actually curious what the Wikipedia article means; they claim you can solve it for all sinks using time proportional to a single instance of Dijkstra, but the only solutions I've seen require $O(E \log V)$ time intead of $O(E + V \log V)$. Does anyone know of a $O(E + V \log V)$ algorithm?
•  » » » » 2 months ago, # ^ |   0 Use Fibonacci heap + parallel bfs to find subtrees (to traverse all subtrees besides the largest)
•  » » » » » 2 months ago, # ^ |   0 Isn't that still $O(E \log V)$ because you check each edge up to $O(\log V)$ times?
 » 2 months ago, # |   +15 Anyone has a good test case for K? I keep getting PE on test 3. My Code for reference
•  » » 2 months ago, # ^ |   +13 I believe acos(min(1.0,*)) would work.
•  » » » 2 months ago, # ^ |   +5 Thank you so much! Problem solved. Never thought that two normalized vectors could have a dot greater than one...
•  » » » » 2 months ago, # ^ |   +41 That is your very typical geometrical trap. Never make yourself vulnerable to epsilon errors. Basically always think that all numbers are calculated within epsilon uncertainty. So if mathematics says that dot product of two normalized vectors can be in [-1,1] interval, assume your program provided you number from [-1-eps, 1+eps] interval. Which, as you saw, can be detrimental to correctness if you do not account for that uncertainty.
 » 2 months ago, # |   -63 Why not all 12 problems on geometry implementation?
 » 2 months ago, # |   +76 G is an instance of edge coloring in bipartite graphs. By using the algorithm here (problem F), we can obtain a $O(n^3)$ algorithm, compared to the standard $O(n^{3.5})$ solution using matching. My implementation of $O(n^3)$ runs 3.5x faster, and the code is also slightly shorter.Of course, the same argument goes to AGC task. You can compare my code of flow solution and coloring solution.Actually, edge coloring in bipartite graph can be solved in $O(M \log M)$, so the whole problem can be solved in $O(n^2 \log n)$ time. But the algorithm is rather theoretical, so I'm not sure if there is any subcubic implementation that actually runs faster than $O(n^3)$ for this problem.
•  » » 2 months ago, # ^ |   +21 I wrote a separate blog entry for this topic: https://codeforces.com/blog/entry/75431
 » 2 months ago, # |   +26 Our screencast (only my screen)
 » 2 months ago, # |   -7 Opening an account on Open cup is the biggest challenge! Any idea how to get it done.? I have sent message to snarknews few weeks ago, but he hasn't come online yet. Is there any other way?
•  » » 2 months ago, # ^ |   +5 It took ~2.5 months to get a reply after I mailed them.
•  » » » 2 months ago, # ^ |   0 :(
 » 2 months ago, # |   0 In K, for the last sample, I am getting major axis length: 10.392304845413612, and minor axis length: 9.1855865354369186 (2a and 2b). Thus my answer is: 74.973649581425, which is pretty near the expected answer. I can't find the bug. Can anyone please share some debug info? I checked some facts in geogebra (like intersections etc) they matches. The only place I did not verify in geogebra is the conic part, which can be tedious, but may be I will try that later.
•  » » 2 months ago, # ^ |   0 From my experience, a very small mistake often comes from unnecessary rounding somewhere. Maybe you cast double to int for a moment in the middle of computation?
•  » » » 2 months ago, # ^ |   0 Good point, but I used double all over the place (except say IsZero, IsCollinear function's return type). So hopefully rounding is not the issue.
•  » » 2 months ago, # ^ | ← Rev. 2 →   +28 We have experienced the same problem and in our case the problem was in false assumption: we thought, that the minor axis is an image of a diameter of the circle, but in fact it is not
•  » » 2 months ago, # ^ |   0 I got those results from model solution: $10.392304845$, $9.486832981$.
•  » » » 2 months ago, # ^ |   0 Thanks.SendThemToHell I don't assume so explicitly but maybe my computation eventually does so? After finding the major axis, I rotate the major axis vector by 90 degree with respect to the plane normal, which gives me direction towards minor axis. Next I find the angle between the minor axis vector and the sun-death star center line (btw which seems to be 90 degree). This gives us a 2d right angle triangle picture (half portion of the subsection of the cone). Am I doing something wrong?
•  » » » » 2 months ago, # ^ | ← Rev. 3 →   +10 I think I got my mistake. I think the sun-death star center does not go through the ellipse center.Upd: AC. But I am not happy with how I compute the minor axis (I have center of ellipse and the minor axis direction. Then I am doing a BS to find the tangent line going through minor axis)
 » 2 months ago, # |   0 Can anyone share a solution code for problem J?i'm getting WA and don't know why :)
•  » » 2 months ago, # ^ |   0 Here you have ;)
•  » » 2 months ago, # ^ |   0 For a long time, I couldn't find a bug in my code.For me, the problem was in an integer overflow.Small chance, but maybe you have the same bug.For the test case 000000.....111111For the first 0 and last 1. I need to make around 10**12 swaps and the total value can get 10**24 if you calculate it like a sum.
•  » » » 2 months ago, # ^ |   0 Yes i had this bug and fixed it but still getting WA