Hey All!
Topcoder SRM 785 is scheduled to start at 12:00 UTC -4, May 09, 2020. Registration is now open in the Web Arena or Applet and will close 5 minutes before the match begins.
Thanks to espr1t for writing the problem set and misof for testing and coordinating the round.
This is the third SRM of Stage 3 of TCO20 Algorithm Tournament.
Stage 3 TCO20 Points Leaderboard | Topcoder Java Applet | Upcoming SRMs and MMs
Some Important Links
| Match Results | (To access match results, rating changes, challenges, failure test cases) |
| Problem Archive | (Top access previous problems with their categories and success rates) |
| Problem Writing | (To access everything related to problem writing at Topcoder) |
| Algorithm Rankings | (To access Algorithm Rankings) |
| Editorials | (To access recent Editorials) |
Good luck to everyone!
Anyone else have problems with "Your login request timed out"? Web arena is working, but it is not really place where I want to write contest
Yes, I am having the same trouble.
Just wanted to ask the same thing,
restarting applet worked for me
Not for me, unfortunately
Hey Egor , KAN Can you try logging out of the web arena and then log in using the applet. I mean press logout in the web arena. It works for me.
I was never logged in web arena, but restarting the applet worked for me now.
I am getting
Your JRE does not support AES-128, login not allowed:(, Any help?Login Request timed out !
Same here! :( Seems like the applet isn't working
Same. Cant login.
First stackoverflow answer of clearing cache didn't help. Redownloaded applet on ubuntu didn't help.
Edit —
ping www.topcoder.comtakes forever on my wifi (JioFibre in India). Fortunately, I couldn't access topcoder 2 days ago as well and I knew switching to mobile data is the only way out. I never faced such problem in past with wifi. I'm sure there is no problem with wifi as I can access all other websites.I was getting various errors, I got both "Your login request timed out" and "Your JRE does not support AES-128, login not allowed", however something like my fifth login attempt was successful. I suggest you guys just have to be persistent.
Entering the web arena and logging out worked for me (maybe just by chance)
Just read your comment and thought to give another try and it worked !
What if you get logged out in the mid of competition?
I am having this exact problem. Already tried more than 5 times, still no luck :(
Hard
Ouch. I figured it is close to a very well-known problem and can be given before — but tried finding similar problems and couldn't. None of the testers knew it was given either, sorry about that. :(
For a fixed position, why is it never optimal to change more than one zero (say, three) to ones?
If you solve the problem from the most-significant bits to less significant ones (and all more-significant ones are already okay) changing a single zero to one would fix the current bit. Changing 3 can also fix it, but they will require strictly more operations. And, since you are changing a number, it will have all-zeroes in its less-significant bits — thus, you won't have all-one bits case in the less-significant bits.
Because when you change the digit from 0 to 1, the following ones become all 0, so they're all equivalent, so having three of those is not better than having one of those for the following digits. Therefore at least two of them can be kept all 0s. And then it's better to stop at 011111 instead of 100000 for those two.
(Simpler explanation?)
Assume that all numbers are in $$$[0,2^{b+1})$$$ and remain in that range at the end. First, sort them in increasing order. We can choose to increase the $$$x$$$ greatest elements less than $$$2^b$$$ such that all of them equal $$$2^b$$$, where the parity of $$$x$$$ is such that the $$$b$$$-th bit of the XOR is 1. Then take all numbers modulo $$$2^{b}$$$ and recurse for $$$b-1$$$. Note that
This easily gives a $$$O(N\log^3 (10^9))$$$ solution. Code
Well, OK. How is it possible that my Hard failed, while Danylo99 passed? It is exactly the same code (that's because of problem mentioned above was from team contest, where we participated together).
undefined behavior in your code?
this looks fishy:
It is not the case as our codes are exactly the same (they differs only by LINF constant, but as answer never exceed 10^18, it doesn't matter).
UPD. Sorry, I misunderstood. I will investigate it.
UPD2. My constant INF was too small:)
Why do you write "variant of Nim" instead of "Nim"? We end up searching for differences from standard Nim even though there aren't any.
Nim was originally played in its misere variant — thus I wanted to specifically point out it is the normal play nim.
Interesting.. in most US textbooks the "normal" version (not misere) is taught first.
At least that's what Wikipedia says: https://en.wikipedia.org/wiki/Nim I've also learnt it in the normal-play variant.
That's ... surprising to say at least :P.
It is really depressing when there are 25 people above you with one less correctly solved task.
I started with TC rounds after many years of competing, and now they are most interesting rounds to me — probably because they require more standard programming skills than "IMO 1995 shortlist tricks". As well I understand people who likes opposite.
can someone explain the DP solution of DIV2 NIM
Anyone else have issues with the 500? I was repeatedly testing my solution on the max case; sometimes it would run in less than 3s and other times it would TLE ...
yes. And I also did it super optimized in my opinion.
How do these leaderboard points exactly work? It's rather clean that Gennady won't advance for the second time, but is it expected that these $$$5$$$ points awards are awarded to him?
Yes, people who already advanced still get the points (but can't advance again), both for direct trips and for qualifying to Round 4. https://clist.by/standings/tco20-algorithm-stage-3-17680999/ shows who would advance with the current points (but it isn't updated with the today's round yet).
Sorry if this is a stupid question, but in DIV1 500, the statement says something like "calculate the expected value", and is the same for the editorial: "Calculate the chance (expected value)..."
This confused me a bit, aren't we supposed to calculate the probability of the ratings be the same, instead of the expected value? Not saying that I couldn't solve the problem because of this, but I want to know if I'm missing something
When I read expected chance I thought of a meme like: a normal guy sitting down doing nothing: “probaility”. A super god with some lights going out of his head “expected chance”
Apparently topcoder allows numpy so I am trying to see if a python solution can pass the div1 500.
Although it takes less than 2 seconds on my machine, it can't even pass the n=42 example test case when running on topcoder's test servers. Anyone see any other optimizations? https://pastebin.com/QzVvNXCT
This problem will be extremely hard to pass in Python I think. It is both very memory inefficient (although I believe the floats, in contrast to integers, are IEEE, thus may be okay) and very slow, and in this problem performance was crucial.
Numpy is vectorized which is sometimes enough to make up for the slowness of the python glue code.
My solution (linked above) runs the n=52 case in 1.5 seconds locally so it would've probably been fine if topcoder had slightly more modern CPUs!
Virgin CF: error 13131313 when importing default libraries in runtime
Chad TC: import numpy