MedoN11's blog

TopCoder SRM 697
By MedoN11, history, 8 years ago, In English

Topcoder SRM 697 starts in around 16 hours, and no blog made yet. So I thought I'd make one.

Timing here

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

»
8 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Cool! No one solved the easy problem :D

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

There are some technical issues with Easy, should be resolved in a moment.

You can enjoy the detailed editorial at the topcoder website.

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

    ConnectedStates can also be solved with exponential generating functions(the answer is (n - 2)! times the coefficent of xn - 2 in the power series of , where p and s are the product and the sum of all ai.

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

    Were you the writer ? If so first of all thanks alot ! Btw where was Limak, on a vacation ?:P

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

      "no Limak" => "I'm not a writer" ;)

      I was a tester (and editorialist this time). A writer was Arterm.

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

How to solve Div2 Hard (XorOrderDiv2) ?!

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

May be out of the topic But where are the editorials for the SRMs(I mean 696 and others) which are missing on this page here

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

    Yeah i too can't find them , some one please explain

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

    All editorials are at the website you linked. They are usually created after the round, sometimes with much later.

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

      Thanks for guiding... (It means I should check the page regularly after the contest if I do not find just after the contest... ) :)

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

    For 696 in particular I started a post that currently only has div1 easy, but today I got AC on div2 hard and div1 medium, I will write the explanation later today :)

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

Hi, I was writer this time, Errichto was a tester.
I apologize for the issue with div1-easy, I occasionally commited wrong solution during the contest to see if it works. We still don't know if it affected anybody during challenge phase, if it affected the contest probably will be unrated.
Hope you found some interesting task during the contest anyway.
UPD: We believe that most likely it didn't affected any challege. So there is a strong chance it will be rated.

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

    Is it common for things to be tested during the competition? IMO, it's far better to let incorrect solution pass than to run the risk of this happening during systest.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 4   Vote: I like it +26 Vote: I do not like it

      Arterm thought that he has made a mistake in one of his generators, went to the problem-preparing system, compiled his own solution with something added, and run it on all tests. Btw. everything was ok with tests so it was all unnecessary. Unfortunately, that solution was saved for some reason.

      I don't imagine being unable to test something during the contest. Organizers often want to check something. In particular, sometimes we are worried about the correctness of our solutions of the validity of the test data. It means that we use the system sometimes. In this particular case it wasn't a must, but who would think that checking something will lead to issues with the systesting? The risk seemed to be to small to consider it (but yeah, sth went wrong).

      I must also add that it was me who advised him to just "compile and run" in the system. I thought that not submitting won't save a solution. So my advice was very very bad.

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

        In this particular case it wasn't a must, but who would think that checking something will lead to issues with the systesting?

        I'm pretty sure exactly the same thing happened in a recent SRM (I don't remember exactly which, maybe someone with a better memory can tell us), so the chance must be bigger than you imagine :)

        It's computing, whatever can go wrong usually does, which is why you should only mess with things as a last resort (e.g. test data doesn't follow constraints, or there is a high probability the solution is wrong). I'm pretty sure solutions that don't sort the array would be very easily challenged anyway.

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

          Yeah, you are right I think.

          I remember an interesting situation from one CF round. It's advised that a checker should print some info in case of WA, e.g. "the printed numbers must be distinct". It's displayed only during the upsolving (and organizers see it during the contest). During the round we saw that in one case a checker prints 0 instead of some other number in the middle of some message. I made a change (requiring some new variable) in the checker (why not, right?), run tests on all our ~10 solutions, and committed. A moment later I found a mistake and managed to find a wrong solution for which my new checker gives AC. Ok, I must quickly go back to the first version. And then I REMOVED the checker by mistake. Polygon is smarter than me though, and it didn't allow me to update a problem in the CF round. Yeah, that was fun. And note that the first change wasn't even important — that info wasn't displayed to any participant during the contest. During the contest you would see only e.g. "WA on test 4" anyway.

          small note: I simplified the story a bit. In particular, not only Polygon but also a coordinator tries to not allow you to destroy a contest.

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

          I'm pretty sure exactly the same thing happened in a recent SRM

          Are you thinking of SRM 652? This was a while ago (over a year), but in that case, some last minute changes were made to the checker but there was a mistake. Details located here and here.

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

          And the other way around, software should be designed to be as foolproof as possible — if a user could do something wrong, it should be expected that he will do it for sure.

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

      I believed it is completely safe. Like, we discussed and agreed not to changing testset. I was just curious if wrong solution will pass. But, unfortunately, it went to production and messed up.
      If you interestring, issue was the following: in around 30%-40% of testcases all b-s were sorted. So, if you want to check they distinct checking each adjacent pair, you may fail if you do not sort.

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

No electricity supply for 14 hours. That's why no blog. I didn't even got the chance to participate in SRM.

Thanks to MedoWith11Es for the post.

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

please anyone can explain the div2 hard(1000)..

I have read the editorial but couldn't understand how trie tree work. I need some help how trie work for this problem. Thanks in advance.

→ Reply