thiago's blog

By thiago, history, 7 years ago, In English

Funny that I was trying to solve the Timus 1955 last week. And then it wildly appears at the World Finals.

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

»
7 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Even funnier than that is that I_love_Tanya_Romanova apparently has solved this problem on Timus. I was really cheering for his team and I wonder why didn't they solve A on WF.

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

    It was probably a good call not to. It was horrible to implement correctly, a lot of teams wasted several hours just trying to debug it.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +116 Vote: I do not like it

    Thanks for cheering us :) We had a lot of fun on this one :)

    First funny thing: all 3 of us solved this problem on Timus; however, if you'll simply take AC solution from Timus and submit it at Kattis, none of three will pass :) Timus problem has lower constraints on coordinates. Solution of one of my teammates is OK because it works in integers as much as possible — you only need to change int to long long there to get AC. Two other solutions work in doubles and that's where things seem to go wrong.

    I took my AC solution from Timus, modified it in a way that should make it work for larger coordinates (changing INF etc.), tried a few different values for eps and so on, yet I'm not able to make it work: WA31.

    WA31 is what I'm getting here :)

    Second funny thing, time for some irony: I started reading problemset from the problem A, so I said to my teammates that we have a problem from Timus here — around 2nd minute of the contest. And that made us really excited because of guess what?.. You know, we were prepared so well that we had most of the solution for this problem in team reference, in section called like that problem from Timus — on the screenshot below you can see it, in Russian: notebook

    Basically we had codes for both N4 and N3 * log(N) solutions that will pass at Timus :)

    As a result we weren't really looking into possible precision issues till the end of the contest.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +69 Vote: I do not like it

      I must be the only one getting AC on Kattis and WA on Timus...

»
7 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Can you share your AC code? The problem on Timus has smaller coordinates so it maybe easier to solve (no precision issue).

I tried to solve this problem yesterday. I think my algorithm is almost correct but maybe I have some issue in implementation..

UPD: Nvm, my teammate has ACed on both sites.

»
7 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Why are people talking about this as if it's a normal thing? I mean this is ICPC WF aren't problems supposed to be original?

also there exists a very similar problem in CF educational round here in addition to Timus problem.

any explanation of appearance of repeated problem in WF?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +85 Vote: I do not like it

    When some duplicate problem appears on Codeforces:

    • i cant google, but some people can google to solve problem, so unfair
    • make pls mike this round unrated
    • fire kan, we want glebs back
    • fire glebs, we want zlobber back
    • fire zlobber, we want gerald back
    • fire gerald and close this shit

    When some duplicate problem appears on WF:

    • i_love_tanya solve problem on timus but not on wf, lulz
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      After so many instances of this issue happening, I guess people started to realize that it is not cool, but it happens. There's no way around it. And it's going to happen even more frequently as time goes by and more problems are written by many different authors on many different platforms.

      So I guess there is no point in ranting too much about it =p

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

      CF is not ACM ICPC WF, also your submission history isn't very impressive.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +26 Vote: I do not like it

      And nobody even remembers that before gerald there was rad.