Блог пользователя Anadi

Автор Anadi, история, 4 года назад, По-английски

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
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -19 Проголосовать: не нравится
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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...

»
4 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +59 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
      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?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +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.

»
4 года назад, # |
  Проголосовать: нравится +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.

»
4 года назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

Our screencast (only my screen)

»
4 года назад, # |
  Проголосовать: нравится -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?

»
4 года назад, # |
  Проголосовать: нравится 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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 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?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 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.

  • »
    »
    4 года назад, # ^ |
    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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 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?

      • »
        »
        »
        »
        4 года назад, # ^ |
        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)

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone share a solution code for problem J?

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Here you have ;)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 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.....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.