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

A week with H2
Автор Petr, история, 9 лет назад, По-английски

http://petr-mitrichev.blogspot.com/2015/06/a-week-with-h2.html

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

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

Wow, I struggled so long to make it to Petr's blog, but when it finally happened then there are two appearances in a row :D (of course that is also thanks to mnbvmar and Errichto :P). However this time indirectly as a member of a team, but still :P. So proud of that and of having solved that H2 :D.

Btw, I am curious about other's approaches to problem I. Did you use an idea of finding shortest paths for some values of p which allowed to say something about a graph of function f(p)=optimal length? Or maybe some dirty tricks like model solution?

And I want to say that this devices problem is very nice! I am very surprised that such silly algorithms like simulating queue given two stacks may turn out to be crucial idea sometimes :)! I will remember that!

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

    I haven't read the problem, but meret (who solved I) said that he didn't use DAG property and runtime of his program depended on the output size. So, I'm guessing he had something similar to yours.

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

    Egor has solved problem I for us, hopefully he'll comment here soon. But I'm pretty sure he was not sure his solution would work in time before actually running it on the large dataset.

    → Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

    For I2 I used binary search and dynamics (instead of Dijkstra to speed up, I hacked up generator to avoid permuting order of vertices), my solution works in O(|answer| * N * log(ε - 1))

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

I thought that last year R+T+J absolutely crushed everyone. We were very lucky to get the 2nd place, even though I felt like we had a pretty good performance. I can't talk for other teams, but we wouldn't caught up with them even if we had one more extra hour. Maybe if we had two, but that's a big maybe :)

This year, we were actually quite close to finishing the whole problemset. I needed around 15 more minutes to finish J2 (my whole performance this year was a string of failures, for example I wasted nearly one hour on getting pygame to work on windows). Around 10 minutes before the deadline meret finished writing solution to L (L1+L2), but he had a small bug, so we ended up without even having L1. Marek struggled with H2 and tried to solve it with LP. It's a good example of "if all you have a hammer, everything looks like a nail". He figured out that it won't work, but since the contest ended very soon, he decided to go with it to the end.

I'm guessing that if we had 15-30 more minutes there was a big chance that we would solve all problems. Probably not and we would screw up something on the way, but I like to stay optimist with that thought ;)

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

    Thanks for sharing! I would guess R+T+J were also not that far from solving all problems, but I agree that the competition was much closer this time. We've tried to solve all 5 remaining problems, too, and had varying degrees of progress, so more time would've helped us as well.

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

Hah, in comparison to us it is funny that you nearly completed problemsets and that additional time will give you much help. We lacked J2, K, L2, M2 and we were very far from solving anything else. I would not solve J and K even given solutions and infinite amount of time :P. Me and Errichto are really just 'classical' competitors and are not able to do some weird stuff like J and K :P. I probably know more about poetry than about assembler and processing of sound :D

→ Ответить