hmehta's blog

TCO20 Round 1A
By hmehta, history, 4 years ago, In English

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.

Learn more here.

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!

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

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

Is it rated?

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

    My bad — I thought I had replied — yes it is rated!

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

The linked list of byes is from 2019.

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

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.

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

    Hi, my TC handle is gs14004. I'm on the list of byes but didn't receive an email. Could you please check this?

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

      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.

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

    also to those who were earlier but have been removed now because of the miscalculation.

    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.

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

      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] :)

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

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?

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

    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.

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

      So, what is the "Competition" in Terms and Conditions in TopCoder?

      Our Website is not intended for use by children under the age of 13. You must have your parents” permission to use this Website if you have not reached the age of majority in your jurisdiction of primary residence and citizenship. You must be at least 18 years old and have reached the age of majority in your jurisdiction of primary residence and citizenship to participate in any Competitions.

      I thought that "Competition" means any rounds of TCO, and it was applied for TCO18 and TCO19. Were the rule changed?
      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        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.

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

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.

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

    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

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

      Sure, I will try Java applet.

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

      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...

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

        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.

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

          the old practice rooms have been removed? there are only practice rooms from 780-783

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

I am not experienced with Topcoder UI.

How to solve problems from "problem archive"?

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

hmehta Does arena works fine on linux ? Or should i use windows .

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

    Works on both. However, should be easy to set up on windows though in quick time.

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

      From last 5 minutes web arena is not loading . Please fix this as only few minutes left :/

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

        Hey Boron — what's your Topcoder Handle — let me register you and then you can setup the Java Applet — topcodr.co/SRMGuide

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

I think the time has come to quit participating in Topcoder Rounds. Your website doesnt work during contest.

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

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.

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

Imagine participating in the parallel round where everyone is yellow+, and you face this problemset.

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

It was really nice of Topcoder to set a problem in the memory of John Conway. RIP.

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

How will finalists for regional onsite rounds be decided?

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

https://youtu.be/LAWlaoLoLQI — Screencast of me getting the last place :D

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

Could someone explain the solution to the 1000 problem in a little detail?

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

    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:

    $$$\mathbb{E}(a, b, c) = 1 + \left(\frac{a}{\text{numItems}} \mathbb{E}(a, b, c) + \frac{b}{\text{numItems}} \mathbb{E}(a+1, b-1, c) + \frac{c}{\text{numItems}} \mathbb{E}(a, b+1, c-1)\right)$$$

    Notice that $$$\mathbb{E}(a, b, c)$$$ appears on both sides of the equation, so you need to rearrange the equation:

    $$$\mathbb{E}(a, b, c) = \frac{1}{\text{numItems}-a} \cdot \left(\text{numItems} + b \cdot \mathbb{E}(a+1, b-1, c) + c \cdot \mathbb{E}(a, b+1, c-1)\right)$$$

    And there you have a recursion. The base cases should be pretty easy to figure out by yourself.

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

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 3   Vote: I like it +1 Vote: I do not like it

        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.

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

          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!

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

      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!

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

        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 that numItems = 20) in E[3, 7].

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

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 :/

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

    But in java applet I couldn't paste my code from my editor into topcoder applet editor :( (on MacOS) And sometimes it crushes..

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

      You cannot paste it because the Control key is hard-coded. Try using Ctrl + V (instead of Cmd + V) — it works for me.

      → Reply