Topcoder SRM 738 is scheduled to start at 12:00 UTC -4, Sept 30, 2018.
UPD: Editorials — https://www.topcoder.com/blog/single-round-match-738-editorials/
Featured Problem Writer: wild_hamster
You will be able to register for the SRM in the Arena or Applet 4 hours prior to the start of the match. Registration closes 5 minutes before the match begins, so make sure that you are all ready to go.
TCO19 Points Leaderboard: https://tco19.topcoder.com/home/algorithm/algorithm-leaderboard
Don’t know how to compete in Topcoder SRMs?
Topcoder Java Applet — You can refer to this guide here to set up the applet. (Note that those who have Java 8 installed on their machine will see a security issue — You will have to add Topcoder in security exceptions in Java Control Panel. Please refer to the details in the guide)
Hope to see most of you competing! All the best!
Next SRM 739: October 10, 11:00 UTC-4
hmehta every-time when I try advice to my friends to write SRM -- I will get negative answers. Answers are like this "What? I will write program in Java Application?", "Bad Interface", "I didn't get how write SRM and go out from site". It's not user-friendly. Topcoder lost it's popularity. Generally I am bad at CP but I can get top 100 easily in div2.
Also I see web arena -- but didn't heard something good about web arena too and in blog you not advising use web arena.
But I and CP community like topcoder. It's has nice problems and good editorials. I want that this project become popular again and user-friendly.
When we can see topcoder in user-friendly way?
Sorry for my bad english
TC asked the community to fix it themselves: https://codeforces.net/blog/entry/61107
We are working on one right now. Within a few days, you will see a form in which we will ask you to put in the problem details, we will manually add it to the system and do most of the work for you. Later we will make that form a web app with all the features.
I can help you if you want to write add the solutions to the system. Just send me an email and I will take care of it. :)
We are taking it step by step — Like we had this page for How to compete for making it easier for the new members to understand around the specific way of writing solutions to topcoder problems and ofcourse using the arena. https://www.topcoder.com/community/competitive-programming/how-to-compete
Also working on the main home page https://www.topcoder.com/community/competitive-programming/ to have everything related competitive programming, be it match list, editorials, tutorials, forums, blogs, results, stats etc.
Problem difficulty is not as high as it used to be. We are bringing back more number of SRMs.
Hope to bring things back in place very soon :)
topcoder arena is not loading
Self-promotion
I will stream on Youtube just after SRM ends. It isn't an official stream but I hope to solve some problems and talk about solutions. And later I will go through some div1-hards from TCO qualification rounds. Link: https://www.youtube.com/channel/UCBr_Fu6q9iHYQCh13jmpbrg.
Still can't enter the room:( So when will srm738 start?
There was an announcement in the arena, 20-minute delay.
Does it allow you to enter the arena?
No, I can't even login to the arena now. Maybe they are restarting it.
I can't login now,what should I do?
More than 20 minutes has passed...
I still can't login to the arena (after they kicked me out ~5mins ago, presumably for restarting the arena). Is anyone else experiencing the same problem?
yup, same
Yes. I am using the web arena, and encountered a brand new login screen that I never saw before.
Link of web arena please ?
https://arena.topcoder.com/#/u/dashboard
yes.
Should I start a streaming of me playing Chip's Challenge while we wait? :')
https://www.youtube.com/user/jonathanirvings/live :)
What is the meaning of "Your JRE does not support AES-128. Login not allowed ?"
It means arena isn't configured yet, it should be ready in 5 minutes based on their prediction
Had the same problem: first attempt — timeout, second attemp — AES-128 error. Restart java applet — timeout again.
Has there been another announcement after the "20 minutes" one?
Please postpone
Someone please drop a comment if they manage to login successfully.
I've managed to log in, although there is no active contest yet.
Same here.
I cannot login neither in the applet, nor in the web arena...
Please wait, I will notify here when it is back up!
Sorry for the issues. All in the process to make it better.
I cannot log in into the web arena.
UPD: It's ok now.
It works now. But there seems to be no contests.
It is possible to login to the arena now
but there is no active contest on there.
Things are back up! We will be starting at 13:00 UTC -4.
Which is about 10mins from now!
Hope you guys enjoy the problems!
yes, I got it finally.
Thanks.
Unable to write in code arena
Medium was very old when I started doing CP.
To be honest it was quite non-trivial for me, I even wrote brute force to get some experimental results.
I was pretty pleased with myself when I solved harder version of this task. This was more than 5 years ago :)
I'm glad I was able to challenge you a little :)
I like this trick. It's quite obvious once you see what's going on, but at the first glance the rules do a very good job to disguise that the bulbs are in fact independent games. I haven't seen this particular trick used at a contest, but I'm sure that some generalizations / similar problems must have appeared before, the setting is quite natural.
How to solve easy and medium?
Easy: Prove or guess that all sides must be integers. Generate all vectors of integer length up to 500 and try all pairs of them.
Medium: The only trick is to realize that this is still a sum of independent games, even though it tries to pretend it isn't.
Imagine that instead of lightbulbs we play the game with pebbles. "Turn a lamp off" is "remove a pebble", "turn a lamp off and another on" is "move a pebble", and "turn two lamps X and Y off" is also "move a pebble from X to Y". In the last case you will get two pebbles at Y (instead of zero lightbulbs), but those two pebbles can be ignored because of symmetry. A longer version of this argument will be in the editorial.
Pretest for MED seems weak. I made a silly mistake :(
The samples (at least at TopCoder) are there to help you understand the statement, not to verify the correctness of your solution. Correctness is your responsibility.
If applicable, we try to have the samples cover potential issues such as overflows and error messages -- in addition to their primary purpose, the examples do also try to make sure that you won't fail because of something unrelated to the problem.
In this particular case, the fact that examples are small and simple is intentional, as I did not want people to guess the solution and "verify" their guess by testing on a big sample.
Thanks for the round!
My screencast with commentary: https://youtu.be/a_AglzG7ieo
(so far seems to only be available in 360p, 1080p is still processing and should be available soon)
Is it just me or has the editorial been mangled so badly that the solution to the Div1 900 is completely unreadable?
Why the editorials of topcoder SRM was posted in codeforces? That's not good.
Can anybody please help me prove, why in Div1 Easy all the sides of the triangle must be integers?
because out of square root(or any root) of integer number comes integer or irrational. (You can prove this fact by contradiction i.e suppose m1/n1 = sqrt(2) and m1, n1 lowest among all values, then you eventually find m2,n2 even more lower)
What you wrote is not a sufficient proof yet.
More precisely, it is a sufficient proof that the square root of a positive integer is either integer or irrational. But that's not enough here.
In Div1 Easy what we need is to prove that for positive integers a, b, c the fact that sqrt(a)+sqrt(b)+sqrt(c) is integer means that all three values sqrt(a), sqrt(b), sqrt(c) must be integers.
The above is not a trivial statement. For example, note that if we change one + into a -, it stops being true: sqrt(2)+sqrt(2)-sqrt(8) is integer even though the three terms aren't.
If you only want to be sure that your solution is correct, you can in fact afford to examine all triples (a,b,c) that are small enough.
The general proof is conceptually simple: Do a proof by contradiction, so start by assuming that sqrt(a) + sqrt(b) + sqrt(c) = p/q for some relatively prime integers p and q. Then, get rid of most sqrts by squaring the equation twice, and find the contradiction by getting an expression where one side is rational and the other is irrational because it's the last remaining sqrt.
Details follow. (Written off the top of my head, quite ugly, may be buggy.)
Start from the above assumption.
Note that we can write sqrt(a) + sqrt(b) — sqrt(c) as (p/q — 2*sqrt(c)).
We can now go back to the previous equation and multiply both of its sides by sqrt(a) + sqrt(b) — sqrt(c) to get:
(sqrt(a) + sqrt(b))^2 — sqrt(c)^2 = p*(p/q — 2*sqrt(c)) / q
a + b + 2sqrt(ab) — c = p^2/q^2 — (2p/q)*sqrt(c)
Let's rearrange terms to get a single term with sqrt(ab) on the left hand side:
2q^2*sqrt(ab) = p^2 + (c-a-b)*q^2 — 2pq*sqrt(c)
Square it again:
something_rational = something_rational — 4pq(p^2 + (c-a-b)*q^2)*sqrt(c)
something_rational = 4pq(p^2 + (c-a-b)*q^2)*sqrt(c)
We can now divide both sides by the nonzero rational 4pq^3, getting:
something_rational = ( (p/q)^2 + (c-a-b) ) * sqrt(c).
Finally, (p/q)^2 is rational and obviously (p/q)^2 > a+b+c, hence the large parenthesis on the right hand side is rational and positive. Thus, we can divide by it and get that sqrt(c) must be positive, a contradiction.
Can someone please explain the solution of Div 2 Medium ? Could not understand it from the editorial.
Let's store all possible divisions in set(let's store them in sorted array order). At first we have division with given number {N}. We launch recursive function, where we remember current division and try to go to all possible divisions from this state(if this state was not used earlier) and launch recursive function from them. For example for {3, 5} all possible next divisions is {1, 1, 1, 5} and {1, 1, 1, 1, 1, 3}. For example how should it work with N = 6:
launch go({6}): {6} was not used yet, so we increment amount, add 6 to answer, launch go({1, 1, 1, 1, 1, 1}), go({2, 2, 2}), go({3,3})
go({3, 3}): {3, 3} was not used yet, so we increment amount, add 3*3 to answer, launch go({1, 1, 1, 3}) and go({1, 1, 1, 3})
go({1, 1, 1, 3}): {1, 1, 1, 3} was not used yet, so we increment amount, add 1*1*1*3 to answer, launch go({1, 1, 1, 1, 1, 1}). When we will launch go({1, 1, 1, 3}) next time, we will just exit as it was already used.
We will stop when we will visit all possible states. As number of possible states is at most 105, we can do it fast. We can also precomputate answers for all N ≤ 90. There are also some possible optimizations in the editorial, you can see them there.
Is it clear enough?
Thank you very very much. This explanation helped me understand and solve the problem. Would be great if you include this with the editorial as well. I found the initial reading of the editorial of the problem very abstract as nothing had been mentioned about how to store the divisions. I used set< vector< pair<int, int> > > to do so as per the idea that you mentioned. BTW, how can we say that the no. of possible states is at most 105 ?
We can just find all the answers for N ≤ 90 and can see, that there will be not more than 105 states. Also it is mentioned in the sample test case N = 90.
OK. Thanks once again. :)