Anadi's blog

By Anadi, history, 2 months 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

»
2 months 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

»
2 months ago, # |
  Vote: I like it -19 Vote: I do not like it
  • »
    »
    2 months 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.

  • »
    »
    2 months 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...

»
2 months ago, # |
  Vote: I like it +13 Vote: I do not like it
  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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?

      • »
        »
        »
        »
        2 months 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)

        • »
          »
          »
          »
          »
          2 months 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?

»
2 months 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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

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

    • »
      »
      »
      2 months 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...

      • »
        »
        »
        »
        2 months 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.

»
2 months ago, # |
  Vote: I like it -63 Vote: I do not like it

Why not all 12 problems on geometry implementation?

»
2 months 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.

»
2 months ago, # |
  Vote: I like it +26 Vote: I do not like it

Our screencast (only my screen)

»
2 months 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?

»
2 months 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.

  • »
    »
    2 months 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?

    • »
      »
      »
      2 months 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.

  • »
    »
    2 months 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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 months 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?

      • »
        »
        »
        »
        2 months 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)

»
2 months 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 :)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here you have ;)

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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