Anadi's blog

XX Open Cup: GP of Wrocław
By Anadi, history, 5 years ago, In English

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

  • Vote: I like it
  • +168
  • Vote: I do not like it

Comments Comments (30)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

did anybody get 'check failed' on C?(div2)
i wrote that https://pastebin.com/kdEXLgvV
wasnt able to submit my solution

→ Reply
»
5 years ago, # |
  Vote: I like it -19 Vote: I do not like it

G was taken from atcoder

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +43 Vote: I do not like it

    All problems were taken from competitions organized in Wrocław (G was proposed in 2018). We didn't notice that it appeared on AtCoder.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +63 Vote: I do not like it

    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...

    → Reply
»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

I was https://en.wikipedia.org/wiki/Suurballe%27s_algorithm

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +59 Vote: I do not like it

    Not really. They say something about solving for all sinks, but do not provide an algorithm.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Use Fibonacci heap + parallel bfs to find subtrees (to traverse all subtrees besides the largest)

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Isn't that still $$$O(E \log V)$$$ because you check each edge up to $$$O(\log V)$$$ times?

          → Reply
»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Anyone has a good test case for K? I keep getting PE on test 3. My Code for reference

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I believe acos(min(1.0,*)) would work.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Thank you so much! Problem solved. Never thought that two normalized vectors could have a dot greater than one...

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +41 Vote: I do not like it

        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.

        → Reply
»
5 years ago, # |
  Vote: I like it +76 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Our screencast (only my screen)

→ Reply
»
5 years ago, # |
  Vote: I like it -7 Vote: I do not like it

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?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +28 Vote: I do not like it

    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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got those results from model solution: $$$10.392304845$$$, $$$9.486832981$$$.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 3   Vote: I like it +10 Vote: I do not like it

        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)

        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone share a solution code for problem J?

i'm getting WA and don't know why :)

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here you have ;)

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes i had this bug and fixed it but still getting WA

      → Reply