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

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

UPD: 2018 ICPC Asia Jakarta Regional Contest problemset is now available on CODEFORCES Gym

UPD2: The original checker for problem C turns out to have non-deterministic behaviour due to insufficient array size. Fortunately, the false checking caused by the bug occurs rarely enough that the live contest (including the mirror in Codeforces) was not impacted (at least we did not receive complaints on the live contest). The checker was fixed on 23 June 2020 and all submissions have been rejudged. See this comment for more detail.

We would like to invite you to the mirror post-contest of 2018 ICPC Asia Jakarta Regional Contest. The contest will start on Sunday, 25 November 2018, 10.00AM Western Indonesian Time (UTC+7) (exactly 2 weeks after the real contest started).

The contest consists of 12 problems and you can solve them in 5 hours.

If you participated the contest, or have read the problems before, you are encouraged to not participate on the mirror post-contest :'( The problems should be available for upsolving after the 5 hours timer is up, though.

See you on top of the leaderboard (to those who plan to participate).

==== This post was heavily edited on November 20. The old post was kept below for archiving purposes. The title of the post was "2018 ICPC Asia Jakarta Regional Contest problemset on Gym" back then. ====

Sorry, I can't resist. (make sure to also read the "On a serious note" below the image)

On a serious note, following the comments on this thread, I am currently working on putting the problemset on (Codeforces) Gym, hopefully it can be done within a week or so. For those teams who are willing to participate in this contest virtually, my advice is not to read the problemset until then :) Stay tuned!

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

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

gym problem on gym machine :D

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

By the way, do you know how hard it is to spread a competition problemset on a Gym treadmill and take a photo of it, without causing people around to think that you're crazy?

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

Auto comment: topic has been updated by jonathanirvings (previous revision, new revision, compare).

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

BUMPing this as a reminder that this contest starts in less than 12 hours :)

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

Why don't you add official participants here as ghosts?

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

The mirror post-contest is over. Thanks for participating, and congratulation to ainta for winning it.

You can discuss the problems here if you want :) The scoreboard for the actual contest is available here (at least for now). The problem repository (including the problem analysis) is available here.

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

I got WA5 on problem C, but after inspecting my output it turns out to be correct. The same code resubmitted got accepted.

The analisys mentions the checker uses rolling hashes so I assume there were collisions.

jonathanirvings I propose to change the checker. One option is to recheck the output some number of times, like ~20, before judging WA. A deterministic option is to check if $$$max(lcp_i) < n$$$ after computing the suffix array.

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

    I don't know which checker is actually used but I found this one on github. This checker has a bug, the power array has size $$$N$$$ instead of $$$H$$$ (line 24).

    But for the second sample, my solution printed $$$3323134352$$$ which should be right and the above checker confirms it. But it got WA on codeforces. 84675626

    This should definitely be fixed jonathanirvings. The moduli in the checker above should be big enough to ensure that no collisions occur.

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

      [Old comment is obsoleted, I did not see the comment properly]

      The custom output validator used in the original contest and in Codeforces is the code found by MZuenni.

      As MZuenni hinted, seems like the error was caused by non-deterministic behaviour due to insufficient array size. Fortunately, the false checking caused by the bug occurs rarely enough that the live contest (including the mirror in Codeforces) was not impacted (at least we did not receive complaints on the live contest).

      I apologize for this error and will fix it at my earliest convenience.

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

      Update: The bug is now fixed, and all submissions have been rejudged. Thanks for reporting and apologize once again for the inconvenience.