The first Algorithm Competition Online Round of the 2020 Topcoder Open has arrived! Round 1A will be held on Saturday April 18, 2020 at 12:00 UTC -4.
Did you win an _Automatic Berth a.k.a Bye_ for Round 1?
Check out the members who won an automatic berth to Round 2 here. CORRECTED and UPDATED
How many will qualify?
The 750 highest scorers from each Round 1 will win a spot in Round 2 of the Algorithm Competition.
How to Compete?
Please note that you must register for this round in the Arena or Applet. Registration is open for the round and closes at 11:55 UTC -4. Be sure you register early to guarantee your spot in the round as registration is limited to the first 2,500 competitors. Please take a look at our How to Compete guide to understanding Topcoder Algorithm contests better.
Don't forget! There will be one more Round 1 — Round 1B on Tuesday, April 28, 2020 at 07:00 UTC -4.
New to Topcoder and the TCO20? The Algorithm Competition is one of the most fierce and popular tournaments. Battle up against some of the biggest names in coding.
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) |
Best of luck to you in the Arena!
Is it rated?
My bad — I thought I had replied — yes it is rated!
The linked list of byes is from 2019.
Hi All, We did some miscalculation with the byes list and it is now fixed — here's the updated list https://tco20.topcoder.com/competition-overview/algorithm/algorithm-byes
Sorry for the confusion :(. We are sending out individual emails to those who are now on the list and also to those who were earlier but have been removed now because of the miscalculation.
Hi, my TC handle is gs14004. I'm on the list of byes but didn't receive an email. Could you please check this?
Hey ko_osaga, you had unsubscribed from Topcoder Emails "Unsubscribed via Topcoder — Data Science Newsletter — 04/14/17". Thus didn't get the email.
Let me know if you want me to subscribe you back.
I see, that’s fine. Thanks!
Did anyone receive such email? I (topcoder handle is thuustalu) was on the list before but got removed. I got "TCO20 Round 1A — 24 Hour Reminder" and "Topcoder Community Newsletter March 2020" so I don't think it's the same problem as ko_osaga had.
Hey -is-this-fft- We did not send that email because almost all the members (who were removed) registered for Round 1A for the same. There were a few members to whom I had specifically informed about getting a bye. I made sure they know they are now removed. Incase you feel you cannot compete in Round 2 — it was totally our mistake and we can award you a bye to Round 2. Feel free to reach out to me at [email protected] :)
So... for participating TCO20 Rounds, we need to be at least 18 years old. However parallel rounds are for all (including people under 17). Is my recognition correct?
There is no hard stop on age on the platform to check the same at the moment because we don't capture that data unless a member is being paid.
Thus all those who got a bye and qualified to Round 4 from the Online Stages 1 and 2 can compete in the Parallel Round. All those who are not can compete in Round 1A
However, the age will be verified when the call to the Finalists goes out from Round 4 results or when the members are paid out.
So, what is the "Competition" in Terms and Conditions in TopCoder?
I thought that "Competition" means any rounds of TCO, and it was applied for TCO18 and TCO19. Were the rule changed?
The rules are the same — however age and birth date are never captured on the platform when you register or compete. You can update the age and birth date information if you want, but that is not a required field.
It is expected from the member to follow these rules. A hard check is done by Topcoder when members are being selected for Finals or when members are being paid on Topcoder.
Topcoder arena server is not responding. I want to register for the contest but the site is unable to load. There is no issue with the network connection. Kindly check once.
Hey, Are you using the web arena or Java Applet? If Web Arena — I recommend you to use the Java Applet it is more stable — topcodr.co/SRMGuide
Sure, I will try Java applet.
On that note, are there any plans to ever finish (read: make usable) the Web Arena? This is maybe the single most serious issue on TopCoder Algorithm. It is incredibly hard to explain to younger competitors why TopCoder is good if they need to use something 15+ years old which doesn't support high-resolution displays and needs explicit Java security exception to run...
There's work going to build a completely new arena. It's taking longer than expected because we are also trying to move out the old data into new databases.
the old practice rooms have been removed? there are only practice rooms from 780-783
I am not experienced with Topcoder UI.
How to solve problems from "problem archive"?
Take a look at this guide to set yourself up — https://www.topcoder.com/community/competitive-programming/how-to-compete
Thanks! I went through that, but I want to practice problems category-wise (by selecting the category in problem archive for example. Am I supposed to go to that particular SRM in the arena practice room or is there an easier way.
The applet or web arena don't have that feature, so you will have to select from the problem archive and then go to that problem in the applet/arena
hmehta Does arena works fine on linux ? Or should i use windows .
Works on both. However, should be easy to set up on windows though in quick time.
From last 5 minutes web arena is not loading . Please fix this as only few minutes left :/
Hey Boron — what's your Topcoder Handle — let me register you and then you can setup the Java Applet — topcodr.co/SRMGuide
I think the time has come to quit participating in Topcoder Rounds. Your website doesnt work during contest.
omg KARAN is back esposing cheaters
KARAN I missed you
I was using web arena and submitted code for a problem in c++ . When i compiled it , it said it has compiled successfully but has generated few warnings. When i went to submit it , it said : your code should compile first . Is it some sort of system error or a rule ? Warning it generated was : variable 'j' has not been initialised . It was not possible to initialise it since i was using it in a while loop and it value it has was based on code above the loop. hmehta please look into it , i have send the code to you.
Imagine participating in the parallel round where everyone is yellow+, and you face this problemset.
It was really nice of Topcoder to set a problem in the memory of John Conway. RIP.
How will finalists for regional onsite rounds be decided?
https://youtu.be/LAWlaoLoLQI — Screencast of me getting the last place :D
Could someone explain the solution to the 1000 problem in a little detail?
Here a small derivation using $$$\text{numSets} = 2$$$. For the other cases the logic is exactly the same.
We perform DP. We can describe a state by counting which items we have how many times. Clearly it doesn't matter if we have the first item twice and the second item once, or exactly swapped. This means we can describe a state using a tuple $$$(a, b, c)$$$ (number of items we have at least two times, number of items we have exactly once, and number of items that we don't yet have). Clearly $$$a + b + c = \text{numItems}$$$.
Let's denote $$$\mathbb{E}(a, b, c)$$$ as the expected number of steps until we reach the position $$$(\text{numItems}, 0, 0)$$$ (when we have enough of every item) from position $$$(a, b, c)$$$. Our end-goal is to compute $$$\mathbb{E}(0, 0, \text{numItems})$$$.
Let's find a recursion for $$$\mathbb{E}(a, b, c)$$$. So let's simulate a move and open a box. If we receive one of the $$$a$$$ items that we already have enough from, we don't get closer to our our goal, and we still need expected $$$\mathbb{E}(a, b, c)$$$ steps to get to the goal. This happens with probability $$$\frac{a}{\text{numItems}}$$$. If we receive one of the $$$b$$$ items, then we get closer. Now we only need an expected $$$\mathbb{E}(a+1, b-1, c)$$$ steps until we get to the goal. This happens with probability $$$\frac{b}{\text{numItems}}$$$. Otherwise if we receive one of the $$$c$$$ items, then we also get closer. Now we only need an expected $$$\mathbb{E}(a, b+1, c-1)$$$ steps until we get to the goal. This happens with probability $$$\frac{c}{\text{numItems}}$$$.
So to summarize:
Notice that $$$\mathbb{E}(a, b, c)$$$ appears on both sides of the equation, so you need to rearrange the equation:
And there you have a recursion. The base cases should be pretty easy to figure out by yourself.
Thanks, this is not easy, and your help is much appreciated. I had a couple of follow-up questions:
1) Why would the end goal be to have numItems of all items? Isn't the problem asking to compute having a numSets amount of any 1 item (instead of a numSets amount for all numItems items)? So that would imply reaching (1, 0, 0) instead of (numItems, 0, 0) in your example where numItems = 2.
2) In the summary formula, E(a, b, c) references itself without any modification (resulting in a potential infinite loop). Did it mean to reference E(a-1, b, c) instead? Perhaps that's what it translates to when you go to implementation, but I wasn't sure.
ad 1) You need to read more carefully. I said that we want to reach the position $$$(\text{numItems}, 0, 0)$$$ from the position $$$(0, 0, \text{numItems})$$$. $$$(\text{numItems}, 0, 0)$$$ means, that we have $$$\text{numItems}$$$ item at least two times, 0 items only once, and 0 items not at all, so in short that we have every item at least twice. And $$$(0, 0, \text{numItems})$$$ means that we have no items at all. Check out the definition of $$$(a, b, c)$$$!!!
ad 2) No. This is not a mistake. That's quite common that you can express a probability or expectation value as a recursion that uses itself. No problem though, that's why we do the rearranging of the equation in the next line.
1) Oops, I had clearly misread the problem statement. Yes, the problem asks to find numSets for each item (and not for any one item).
2) Ok, figures, just clarifying
Thanks a bunch!
Thanks for the wonderful explanation of the state. It's amazing how the main thing of these DP problems is identifying the precise state representation, and how hard it is to come up with that. Even with your detailed explanation I had to read it several times and think hard before my mind was able to transpose the "easy" state which first comes to mind (and doesn't work), to this true one.
I have one more question. Your state has up to 5 variables, but because the sum of those equals numItems, the actual number of possible states is not 50^5. So I used a map to store the memo and upsolved using your explanation, because that is sparse compared to double E[50][50][50][50][50].
But many have written solutions with double E[50][50][50][50] which is small enough to store. I don't quite understand how they are eliminating that fifth dimension. Could someone explain further? Thanks!
Yes. We know that the sum of all 5 variables is always equal to
numItems. So if you only store the last 4 variables, you can easily compute the first one. E.g. in my example, we could store the position(10, 3, 7)(which means thatnumItems = 20) inE[3, 7].After the contest, I can't log in to the arena from the web site. It just freezes with the message "Completing login... One moment please..." then after some time it redirects me to some other login page and says that my password is incorrect. Although, I'm able to login with applet and the same username and password :/
But in java applet I couldn't paste my code from my editor into topcoder applet editor :( (on MacOS) And sometimes it crushes..
You cannot paste it because the Control key is hard-coded. Try using Ctrl + V (instead of Cmd + V) — it works for me.
Yep, thanks:) already found out)