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

Автор Errichto, 5 лет назад, По-английски

I and Lewin will do some commentary of TCO semifinal 1, starting in a few minutes. Watch it on TCO Twitch website.

Stream: https://www.twitch.tv/topcoder_official

Statements: https://docs.google.com/document/d/1OjmXL8DMDiWf92XhLch_xjjPVA21-dvIhcnYEh_0CbM/edit?usp=sharing

  • Проголосовать: нравится
  • +60
  • Проголосовать: не нравится

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

TCO 1000 Solution

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

Semifinal 1 has finished.

Thank you for easy and medium — I liked them a lot. In easy the most intuitive solution is wrong, and you need to prove the solution to get it right. I like such kind of problems. With a good observation the implementation of medium can be very simple like tourist's solution. (By the way, how to write the checker for this? Is the answer actually unique?)

Personally, I didn't like hard because in my solution I needed to compute an inverse of a power series and this way the problem was quite technical and the TL was quite tight. Probably n <= 10^7 was a better constraint. Also, it was unfortunate that the problem was bashable (e.g. P-recursive). Though, the intended solution is very nice.

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

    misof authored easy and medium. Yes, the answer is medium is unique. Let's say there is bit $$$1$$$ at position $$$i$$$ if card $$$i$$$ is exactly there. This gives us a big binary number. This number must decrease with each operation, so it's optimal to decrease it by $$$1$$$ and there is just one way to do it.

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

Is there a way to get emails about upcoming Topcoder events? The contests seem to often be announced only a few days before they begin and I don't want to keep having to check the website.

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

Results?

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

Congratulations to tourist!

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

    ksun48 is congratulating tourist.

    Thanks!

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

      My last year’s victory at Topcoder Marathon was, to me, a great achievement because it is a format very different from traditional contests: 12 hours, one complex task, no ideal solution. I’m still not sure if I didn’t simply get lucky there: perhaps I’ll have to win another time just to prove that it wasn’t all luck.

      Congrats :)

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

So did lyrically get challenged or not ? (During the challenge phase she got challenged, but at the evaluation it didn’t show challenged, then it did, but the points didn’t get removed? Very confusing)

Edit: Guess there was a precision problem on hard going by Petr's tweet: https://twitter.com/PetrMitrichev/status/1195824770291585024

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

    Both challenged :( and passed :)

    For those who don't know the task: Final 1000 is a special-judge task where the contestant should return an array of doubles and the checker calculates certain values, which can have relative or absolute errors of at most 10^-7 to get accepted.

    Here goes what I heard from the admin, misof. Against the challenge case made by Petr, my solution had errors around 10^-5 and hence it was a successful challenge. But at the same time writer's and tester's solution also causes errors around 10^-5. misof says the solutions are precise enough when run locally, so it might be an issue with handling doubles in the topcoder system.

    The decision was announced before the closing ceremony. In short: the challenge scores are kept as is, while they rejudge the submitted solutions, tolerating much errors (seemingly 10^-4). Finally my 1000 passed.

    Anyway, precision errors are really really hard to tackle with...

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

    On the other hand, I feel I was cheated by the organizers (congrats on the correct solution to the problem, of course!).

    From what I understand, you needed to return vector<double> in your solution. However, doubles turn out to be too inaccurate and these tiny rounding errors made the relative errors of the areas produced as large as 1e-5. Therefore, it was probably impossible to solve the problem within these limitations.

    From my point of view, if statement says one need to fit within 1e-7, and no solution can fit within 1e-7, then, well, sh#t happens — no solution can solve the problem. Changing the allowable relative error to 1e-4 (?) feels:

    • random (what if it's possible to cause even larger errors?)
    • inappropriate (wtf, changing the statement of the problem after the end of competition? I understand you can't simply make the finals unrated here, but, well...)

    It's so upsetting to me. Also, if the organizers chose 1e-7, they probably had some reason (isn't 1e-9 the default allowed error?). If they were afraid of these errors, they should have done everything to prove that their solutions will fit within 1e-7. They have not. Damn it, this is probably the most important round on this platform in the year, and you do this! You had more than 85 minutes to prepare this problem.

    Disclaimer: I acknowledge that if the problem had been prepared correctly, the standings would have looked the same way they look right now. In some way, I "didn't deserve" to be higher, and I'm okay with this. Obviously, hos.lyric deserved her place, congrats! The organizers were crap. Thank you.

    It's been so many times I've been deeply disappointed with a TC round. Maybe it's a good idea to take some longer break from it.


    I'm sorry for such a long rant. I feel quite emotional about this and I just needed to show my point of view. Thanks.

    Also, thanks to all other organizers, you did a great job and the everything else was amazing!

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

      Just git gud

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

      doubles turn out to be too inaccurate

      If "the solutions are precise enough when run locally", then doubles aren't too inaccurate, the TC system is faulty. You know their SRM infrastructure is crap. If you were a problemsetter on TC, you know preparing a problem in that system (MPSQAS) rather than locally or on Polygon is torture, so it would make sense that a failure in the testing system doesn't get caught because you can't stresstest in that system, only locally. Simulating correct behaviour by decreasing the required precision rather than sticking with the incorrect behaviour seems like the right choice.

      I don't know the problem, can you show that standard double rounding errors really add up to over 1e-5? It's something I have trouble believing until I see and test it (like here).

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

        @Xellos, In that TC problem, printing values with error $$$e$$$ might give you solution error much bigger than $$$e$$$, this is why returning doubles was very bad.

        I completely understand mnbvmar's frustration and I'm sorry for the situation. We didn't prepare and test problems carefully enough. Two biggest reasons were MPSQAS and how late we started the problem selection/preparation process. I hope that next year there will be a new tool and the process will start at least a month before TCO.

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

          You don't have to tag when replying, there's a reply notification anyway.

          Yes, I'm aware the solution error as defined can be much larger than the error in the output values (particularly angles since trigonometry has higher precision loss than simple arithmetic). I was just basing everything off of "precise enough locally", which I expected to be about the solution error calculated by the checker.

          I'm also interested in how that happens and if it really differs between systems (80-bit double registers come to mind). The relative error in triangle areas should be roughly the same as the relative errors in returned angles or trigonometry calculations (whichever is larger) if we assume that these are the dominant errors.

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

            I'm not sure about calculations but:

            Let $$$M$$$ be a limit for coordinates. A relative error $$$e$$$ in returned coordinates of the middle points means an absolute error $$$e \cdot M$$$ in returned coordinates, which means an absolute error $$$e \cdot M \cdot X$$$ in computed areas, where $$$X$$$ is the diameter of the polygon. Does it make sense?

            misof can know more.

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

Also wanted to mention how enjoyable the format was with Lewin and Errichto explaining the problems to Scott and the back and forth to reach the solutions, didn’t expect it to be this enjoyable to watch. Congrats on that!

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

    I agree, Topcoder has the best coverage, far ahead any other programming competition stream, ICPC organizers have a lot to learn.

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

      TCO has like at most 8 contestants and the format is very blitzy clocking in at only 85 min. It's much easier to cast this type of event than a 5 hour contest with >100 teams.

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

tourist didn't participate in design challenge otherwise he would have won that as well. All designers should thank him..

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

Can someone explain the solution for Semifinal 1 — 1000? Looks like it can be solved using Kirchhoff's Theorem, but how can the eigenvalues of the Laplacian Matrix be computed efficiently since $$$m$$$ can be up to $$$10^6$$$?

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

I made a video about FourDistinctDigits (div1-hard from semi2) because it's a cool problem :)

https://youtu.be/_W7Yy0CNDws

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

Hi Errichto..How to access your DP playlist of 15-20 videos that was earlier posted on youtube