Errichto's blog

TCO 19 live stream
By Errichto, 5 years ago, In English

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

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

»
5 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

TCO 1000 Solution

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

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.

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

    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.

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

Day 2 statements: https://docs.google.com/document/d/1sRfdKdo2F_hUKK3qWKWCij9_pgs04btOMocjfEWDzt4/edit?usp=sharing

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

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.

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

    I'm getting TC Newsletter, it has a section that lists upcoming SRMs.

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

Statements for finals: https://docs.google.com/document/d/1g-H0eyN4H6SG2OLtmJYRW3fPUk8td2kaNVaqp15baoA/edit?usp=sharing

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

Results?

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

Congratulations to tourist!

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

    ksun48 is congratulating tourist.

    Thanks!

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

      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 :)

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

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

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

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

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

    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!

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

      Just git gud

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

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

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

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

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

          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.

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

            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.

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

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!

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

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

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

      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.

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

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

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

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$$$?

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

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

https://youtu.be/_W7Yy0CNDws

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

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

→ Reply