chrome's blog

Single Round Match 664
By chrome, history, 9 years ago, translation, In English

Hi there! I am back from SIS(LKSh)!

Tomorrow Today at 19:00 MSK will be held Topcoder SRM 664.

GL && HF

Let's discuss problems here!

Also, congrats for all IOI winners!

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

Comments Comments (29)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Registration has started

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

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

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

I usually don't try in the challenge phase much (I read the codes, but just briefly and usually don't try to challenge), but is challenging always this laggy? I tried challenging 5 times, always something that wasn't marked as challenged, and after a minute+ of waiting, I got the result: this problem was successfully challenged by someone else. 5 times in a row (okay, to be precise, I didn't get any feedback twice and this message 3 times).

Meanwhile, there was no indication of the problem being challenged, the red info below the code and "Challenge Succeeded" in the summary only appeared around the same time as that message.

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

    Challenge phase will be nullified

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

      Which means I potentially lost 250 points in the challenge phase?

      Based on the reasoning from TCO15 2A, it should be unrated.

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

        TCO15 2A was rated i think at least for me :P

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

          You didn't read the thread I linked at all, did you?

          The round was supposed to be unrated due to something similar. But since people need to advance from it and there was a local event, it needs to be acknowledged as a valid round. And if it's a valid round, it's rated.

          If there wasn't a need to consider it a valid round, then it could've (that was the initial intent AFAIK) been unrated.

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

    Same story.

    I tried to challenge all wrong solutions for 250 in first 1-2 minutes, and then I was getting messages about problem being already challenged during whole challenge phase in some random moments of time (I got last one 6 minutes before the end — it was 7-8 minutes after my last challenge attempt). Inbetween I was simply looking at standings, seeing yet unchallenged problem which I already tried to break, and waiting for some good news.

    Anyway, it seems that people at TopCoder were scared by having more than 1200 people registered for a round, and they had to make something to prevent such a huge scary numbers in future.

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

Ok will somebody please explain how to solve Div.1 easy ?

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

    Here is my Python code:

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

    Exponentiation modulo (A+B)

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

      Could anyone please explain why this solution works?

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

        if A >= B then A — B = 2 * A mod (A + B)

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

        One of the numbers in the pair is always , because the transitions are (a, n — a) -> (2a, n — 2a) and (a, b) -> (2a — n, 2n — 2a), where n = a + b.

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

        The number of marbles in A + number of marbles in B is always equal to A+B; actually always A and -A (mod A+B). So when you double one pile, marbles will always be 2A and -2A (mod A+B).

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

Oh crap, challenge phase nullified :(. Had one successful challenge.

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

(Java-related rant follows)

Yet another contest with my impression of it totally ruined because authors love tight constraints. In 550, if you want participants to come up with a linear solution, why do you make the tree so huge? 200000 nodes would be more than enough to kill all wrong approaches. And with 1000000 — Java solutions with recursion get TLE (for some mysterious reason — apparently there's smth wrong with Java on topcoder servers, it was working less than 1 second locally). What's worse, getting rid of recursion is non-trivial coding task, if you don't read actual tree generation code.

It is really disappointing, since the tasks were nice in my opinion.

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

    I'm very sorry for that. 1e6 didn't look tight at all. We had two solutions in java passing tests easily but they didn't use recursion. I didn't think about testing it with recursion because it was nonsense for me that linear solution wouldn't pass. My bad, my apologies.

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

    Well, reading the actual tree generation code wasn't that hard :)

    Moreover, do you see how the tree-generating code could NOT look as "connect i with its parent in [0..i-1]" and still always generate a tree?

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

    My java recursive solution passed.

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

    In TC we have experienced solutions doing more than 1e9 operations in 1s, so if Java can't handle n<=1e6 then it is a serious reason to change your coding language to C++ :P.

    To be clear, that suggestion was not serious, but I have to admit, that I wasn't expecting such things, Java here kinda sucks hard.

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

      you're comparing 1e9 operations with C++ with 1e6 with Java , but you forget that 1e9 operations in C++ takes less than 1s only if they are iterative and have operations that the processor can do quickly (unlike multiplication and modular)

      while in the 1e6 in Java it is recursive operations and contain a lot of multiplication and modular operations

      so you can't simply say 1e9 in C++ is less than 1s while 1e6 in Java is more than 2s

      BTW, my solution in C++ already was taking more than one second

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

        But man, 1e9/1e6=1e3, you won't simply go away with argument "modulo is slower than addition". And not modulos here are subject of matter, as I understood depth of recursion is the bottleneck.

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

          not only modulo but also recursion , and as I told you my solution in C++ took more than 1 second so the majority of 1e3 times slowness comes from type of operations and recursion not from Java

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

Editorial is on TC website. I invite you to discuss about problems on my blog

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

    What a great great job publishing the editorial that fast. Thank you so much.

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

For the love of god, don't make the round unrated...

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

I'm quite shocked that my 550 Div2 code passed :3

I think that who ever tried to challenge my solutions is really pissed off now :P

→ Reply