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
did anybody get 'check failed' on C?(div2)
i wrote that https://pastebin.com/kdEXLgvV
wasnt able to submit my solution
G was taken from atcoder
All problems were taken from competitions organized in Wrocław (G was proposed in 2018). We didn't notice that it appeared on AtCoder.
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...
I was https://en.wikipedia.org/wiki/Suurballe%27s_algorithm
Not really. They say something about solving for all sinks, but do not provide an algorithm.
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?
Use Fibonacci heap + parallel bfs to find subtrees (to traverse all subtrees besides the largest)
Isn't that still $$$O(E \log V)$$$ because you check each edge up to $$$O(\log V)$$$ times?
Anyone has a good test case for K? I keep getting PE on test 3. My Code for reference
I believe acos(min(1.0,*)) would work.
Thank you so much! Problem solved. Never thought that two normalized vectors could have a dot greater than one...
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.
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.
I wrote a separate blog entry for this topic: https://codeforces.me/blog/entry/75431
Our screencast (only my screen)
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?
It took ~2.5 months to get a reply after I mailed them.
:(
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.
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?
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.
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
I got those results from model solution: $$$10.392304845$$$, $$$9.486832981$$$.
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?
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)
Can anyone share a solution code for problem J?
i'm getting WA and don't know why :)
Here you have ;)
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.....111111
For 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.
Yes i had this bug and fixed it but still getting WA