simonlindholm's blog

By simonlindholm, history, 9 months ago, In English,

Hot on the heels of Finland's contest, the Swedish olympiad finals also took place this weekend, and for those who want to try out the problems, we have put up a site where you can participate during any 5 hour period during this week: https://pofinal19-open.kattis.com/.

If you don't have 5 hours to spare you can also look at the problems directly at https://pofinal19.kattis.com/. The last problem is IMO quite neat.

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

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this full feedback? Are there hidden system tests?

»
9 months ago, # |
  Vote: I like it +18 Vote: I do not like it

The last one appears to be the same as this problem.

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

    Oh, you're right. That's further back in ICPC history than I've looked. :) I guess it's not too surprising that it has appeared before given the simple graph reformulation, though it does at least require a bit of thinking to reduce it to that.

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

    Well in that problem you could get away with a O(n^4) solution, here you need to tweak it to be O(n^3)... :/

    Mine turned out quite horrible. Time to read the spoilers to see if there's a more beautiful way. ^^

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

      I had an O(n^3 log n) solution for that problem. I find it not obvious how to improve the solution for the sparse case where |E| is smaller than n^2. I agree that it is a tough problem, it took me several hours to get AC at the Live archive.

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Going to publish the scoreboard? (been waiting since morning :D)

»
9 months ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

damn, it's the biggest word I've ever seen :D