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!
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
4 | atcoder_official | 161 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
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!
Name |
---|
Registration has started
Auto comment: topic has been updated by chrome (previous revision, new revision, compare).
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.
Challenge phase will be nullified
Which means I potentially lost 250 points in the challenge phase?
Based on the reasoning from TCO15 2A, it should be unrated.
TCO15 2A was rated i think at least for me :P
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.
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.
Ok will somebody please explain how to solve Div.1 easy ?
Here is my Python code:
Exponentiation modulo (A+B)
Could anyone please explain why this solution works?
if A >= B then A — B = 2 * A mod (A + B)
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.
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).
Oh crap, challenge phase nullified :(. Had one successful challenge.
what does "nullified" mean ?
(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.
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.
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?
My java recursive solution passed.
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.
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
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.
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
Editorial is on TC website. I invite you to discuss about problems on my blog
What a great great job publishing the editorial that fast. Thank you so much.
For the love of god, don't make the round unrated...
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