hmehta's blog

TCO20 Round 4 and Parallel Round
By hmehta, history, 4 years ago, In English

The Parallel Round of fourth Algorithm Competition Online Round of the 2020 Topcoder Open has arrived! Parallel Round 4 will be held on Saturday, Sept 5 at 12:00 UTC -4.

The match will be **rated**

Please note that you must register for this round in the Arena. Registration is now open for the round in the Arena or Applet and will close at 11:55 UTC-4. The coding phase will start at 12:05 UTC-4, so make sure that you are all ready to go. See what time Round 4 starts in your area.

Don’t know how to compete in Topcoder Algorithm Competitions?

Check out this guide to successfully compete in an algorithm match.

You can compete using:

  • 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.)
  • Topcoder Web Arena(Beta) - Please watch this video for step by step guide

Best of luck to you in the Arena!

- The Topcoder Community team

  • Vote: I like it
  • -20
  • Vote: I do not like it

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

I cannot login to the arena.

The message is either "Your login request timed out" or "Your JRE does not support AES-128, login not allowed". I tried clearing the cache and restarting the computer but it didn't work.

I could login half a day ago. What happened? Please help me.

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

    Now I am logged in.

    I had tried both oldly downloaded one (ContestAppletProd.jnlp) and the newly downloaded one (ContestAppletProd7.2.jnlp). The solution was to try again and again...

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

      Every single version of the arena is broken as shit. Possible errors include never getting the Enter button enabled when a contest starts, being unable to challenge, unable to log in and others.

      The only solution is trying different versions of the applet and hoping one of them works.

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

Why does the parallel coding phase start before that of the main round? :/

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

That's a serious questions: does the page with the leaderboard in webarena work today? I don't have ready applet on my machine and I don't know if I should install it or if the website will work today.

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

    If you can setup applet before stsrt then please do it. Dont rely on web arena in an important contest.

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

    Nothing works properly, reason: TC sticking with the same old/broken shit as always.

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

      Are you still facing the issue? Apologies, we did restart the arena and cleaned things up a few hours back to make sure there are no issues. Request you to please email — [email protected] or me at [email protected] whenever you need any urgent help.

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

        I'm talking in general, I or other people seem to encounter never before seen problems from time to time.

        Trying to support something as outdated as this system is clearly a failed approach. There should've been a proper, non-broken web arena a long time ago.

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

I have an URGENT question about Round 4 bye!

I did have it, but now I can't register to the round 4 in the arena.

It is not funny! Please fix the problem!

darnley

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

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

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

    The first screenshot was made on April 17, the second was made right now.

    It was April 17, not April 1, so I don't consider this situation a nice joke from TopCoder!

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

      Hey! You should be registered now. We had an issue on the leaderboard and fixed that in a few hours after it was published in April. Sorry for the confusion. We have you registered. All the best.

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

        I confirm that I'm registered now, thank you! Not very happy about the overall situation, but grateful for fixing it in time.

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

Hard: 325E - The Red Button

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

1)Hard is almost duplicate of 325E - The Red Button, some people just copied code to this problem and got close to full score on it

2)I am a bit upset that problems in this round were so easy. Sure many problems were challenged but before the challenge phase there were >30 full scores. I don't think that selection to the final round should work this way...

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

    ...

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

    Transparency is important, so I'll try to give some comments from our side:

    First, the round was certainly easier than it ideally should have been. No arguments there.

    Apologies for not knowing about the similar problems, both me and the round's testers (Lewin and Shef) had no idea about them. Luckily, it looks like the impact is quite small.

    That being said, I don't think that the difficulty was that low, and I don't think that "before the challenge phase" is a useful metric. From testing we had quite a good idea how tricky the easy can be if people rush it, and many did do that and failed. That's not solving the problem, and should not count as such. If I'm counting correctly, we had 16 people actually solving all three problems which isn't that far from what we were aiming for (which was 10 such people in an ideal world). It's quite hard to accurately set a round that ~10 people will solve fully, especially with our contest time and #problems constraints, there is quite a lot of variance involved. To give you a different perspective, from what I've seen during the round I think we would have hit the desired number if the round was about 5 minutes shorter. Happens.

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

      Sadly, it looks like the impact was quite large...

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

Any hints for 600 level problem!

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

Editorial: https://www.topcoder.com/2020-topcoder-algorithm-round-4-editorials/

Thanks for participating :)

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

Isn’t med the same as a problem from Gennady’s acm contest which took place during winter 2017 Petrozavodsk camp(with smaller limits)?

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

    I was wondering why tourist solved this immediately LOL

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

      VArtem wrote an additional solution before that contest, and even though it was really painful back then, today he submitted it even faster than I did! :)

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

Hard was interesting. The appliance of randomized algorithm is great.

We can use the fact that, for random permutation $$$p$$$, when we consider graph of $$$i \rightarrow p_i$$$ for $$$i = 1, 2, 3, \dots, N$$$, the probability of this graph to be cycle is exactly $$$1/N$$$.

We can easily see that the number of patterns of which directions from all vertices are different is $$$2^{N/2}$$$, because we can pair vertex $$$k$$$ and $$$k + N/2$$$, which has the same candidates of directions. We randomly assign directions in this idea, and then we can think that the assignment will hit correct in $$$1/N$$$ probability.

The expected time complexity is $$$O(N^2)$$$.

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

    And why we can treat those permutations as completely random? This does not even prove that answer always exists.

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

      I'm sorry that I forgot to tell that it is still a conjecture. During the contest I proved in a way that computes the answer for $$$N = 2, 4, 6, 8, \dots, 3000$$$. I also checked the number of tries, and everything fit in $$$\leq kN$$$ tries for some small constant $$$k$$$.

      I still do not have a complete proof, but I reached some fact that seems nice. Let $$$C(N)$$$ the number of Hamiltonian cycle, and let $$$\delta(N) = 2^{N/2} / (N \cdot C(N))$$$, the expected number of tries divided by $$$N$$$.

      Then, for any positive even number $$$N$$$, I conjecture that $$$\delta(N) = \delta(2N)$$$ will hold. I verified to be exactly true for $$$N = 2, 4, 6, \dots, 32$$$. I expect that this proof is not very difficult (still not come up with it yet).

      If the conjecture is true, we can say that, for any positive integer $$$k$$$, $$$\delta(2^k) = 1$$$, $$$\delta(3 \cdot 2^k) = 4/3$$$, $$$\delta(5 \cdot 2^k) = 16/15$$$, $$$\delta(7 \cdot 2^k) = 64/49$$$, and so on, will hold.

      According to random analysis of 10,000 tries, $$$\delta(N)$$$ has a larger value when $$$N$$$ has many distinct prime factors. For example, $$$\delta(210) \simeq 2.19$$$, $$$\delta(630) \simeq 2.40$$$, $$$\delta(2310) \simeq 2.20$$$.

      It is likely that $$$\delta(N) = O(\log N)$$$. Since the time complexity is $$$O(N^2 \cdot \delta(N))$$$, the overall computing time of $$$O(N^2 \log N)$$$ is possible, but I guess it would not be larger.

      EDIT: I think that the exact value of $$$\delta(N)$$$ can be computed in $$$O(N^4)$$$ time by BEST Theorem.

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

From the editorial, about the 600-pointer: Challenge yourself: can you now solve this problem (modulo 10^9 + 7) with the constraint that N can have up to 100,000 digits?

I set this problem with $$$N \le 10^{250\,000}$$$ for Gennady Korotkevich Contest 2, but exact answers were required, without any modulo. It was funny to see rng_58's clarification request: "Did you forget the modulo?" (but it's a reasonable question of course). See this comment for a brief solution description.

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

Also, hard is very similar to that: https://codingcompetitions.withgoogle.com/codejam/round/0000000000201902/0000000000201877. I have to say, that I’m very disappointed with the problem set. Two constructions, two notorious coincidences and two typical typical tc problems in 3-problem contest :/

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

Wow that was bad. When you think topcoder can't get any worse...

→ Reply