hmehta's blog

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

The TCO20 Algorithm Round 3B and Parallel Round of TCO20 Algorithm Round 3B is scheduled to be held on Tuesday, August 18 at 07:00 UTC -4.

The match will be **rated**.

Please note that you must register for this round in the Arena. Registration is open for the round and closes at** 06:55 UTC -4. **The coding phase will open at 07:05 UTC-4.

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 5 minutes before the match begins, so make sure that you are all ready to go. Click here to what time it starts in your area.

Members eligible to compete in the Parallel Round include:
- Members who did not qualify for Round 3
- Members who advanced to Round 4 from Round 3A
- Qualified for Round 4 or TCO20 Algorithm Finals from Online Stages 1,2 and 3

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
  • +19
  • Vote: I do not like it

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

Excuse me, how is there 30% of unused code?

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

    <bits/stdc++.h> contains thousands of unused functions!

    Joking aside, as the auto-detection is pretty inaccurate like this, and as there seems to be few (no?) deduction for the Unused Code Rule these days, having this message could be very unfair. I hope the rule to become properly applied or to be removed.

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

    Maybe they just always display that message because nobody cares anyway :D

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

    Oh wait, I hope they don't apply the __attribute__((unused)) to all the code below...

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

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

I thought I mistakenly opened 300 when I opened 1000 first :) (As long as I remember old days topcoder rounds contained this kind of problem as Easy).

Anyway I liked the problems, thanks!

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

    Same! I also checked if it's 1000 for sure.

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

      I checked multiple times before the first submission on 1000 in the non-parallel round came, so, thank you :D

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

    +1. Topcoder should find somebody to test their rounds at least for TCO, the place of this problem is just ridiculous.

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

    Don't check how easy it was and facepalm. Check how easy it was, then how many people failed it, and then facepalm!

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

Oops did anyone else do B in $$$\Theta(\max(D)^6J^5)$$$ ...

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

    That's what I was trying to code at the end of the round, but it was hopelessly slow for me :) Great job making it pass!

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

How to solve Medium 500, I was able to make precomputations for N <= 100 but was unable to relate it with bigger dimensions. Borders, in my case.

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

    My solution was as follows:

    Since J = 10 and max(D) = 10, you can move maximum 100 in any direction. That means that anything that is at distance 100 or more in both dimensions can just move freely.

    So: If N <= 201, you just do DP[i][j][k], in how many places can you get from i,j in k steps.

    Otherwise do the DP for N = 201. If you notice cell (101,101) can't be blocked by the walls because it's too far away. And cells i, 101, with i <= 100, can't be blocked by the j coordinate, only the i one.

    And if you do a drawing of how many cells like our (101,101) are there (Specifically cells that cannot get blocked by the wall) ? You'll find that there are (N-200) * (N-200).

    So add (N-200) * (N-200) * best[101][101][J] to the answer.

    Now if you look at the cells that are of type (i,j), with i < 100 and 100 < j < N-100 (So you can get blocked by a wall in the i coordinate, but not in the j). There are N-200 for each i. Multiply that by 4 (since you can be blocked by i to the left, i to the right, j up, j down).

    So add 4 * (N-200) * best[i][101][J] to the answer (i <= 100)

    Now you only need to add the square in the corner 4 times, with i < 100 and j < 100.

    So add 4 * best[i][j][J] to the answer (i,j <= 100)

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

      Uhh, what do you mean "just do dp"? Isn't it $$$200^2 \cdot 10 \cdot 500$$$? The dp is obvious but I was always under impression topcoder servers are pretty slow.

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

        The judging machines are just fine, you'd know if you had to face a tighter DP problem there before. Treat it like submitting on CF as far as the TL goes.

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

          Ok, I see. I think I remembered someone talking about some inconsistent performance at latest tco finals but I guess I misremembered something.

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

            They're fine as far as "this DP has too many state transitions, it'll get TLE unlike on a modern judging system", which is what you were asking about.

            The inconsistent performance is a separate problem. First, I suspect it's caused by wrong measuring rather than old hardware (but we'll most likely never know). Second, it's not something you can rely on — it appears inconsistently and even if you're affected by it, it's never your mistake (unlike sending a code that properly TLEs) and you can talk to TC about fixing your result. You should worry about it as much as about your computer running out of power and shutting off in the middle of a contest.

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

    After computing it for $$$N=100,101,102$$$ you can use polynomial interpolation to get the answer for any greater $$$N$$$.

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

      Do you imply, that polynomial is of degree at most $$$3$$$? Also, I'm not sure why it is $$$N = 100$$$ and not $$$N = 201$$$.

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

        I can explain why the polynomial has a degree no more than $$$2$$$, but, indeed, for $$$N > 200$$$. Let $$$cnt(x, y)$$$ be the number of cells for which the distance to the vertical boundary (either left or right, doesn't matter) is $$$x$$$, and the distance to the horizontal boundary is $$$y$$$. For the cell $$$(0, 0)$$$ these numbers are $$$0$$$ and $$$0$$$. Also if any of $$$x$$$ and $$$y$$$ is at least $$$100$$$, we replace them by $$$\infty$$$. So the points are now of these types:

        • $$$x$$$ and $$$y$$$ are finite. For $$$N > 200$$$ all these $$$cnt(x, y)$$$ are $$$4$$$.
        • either $$$x$$$ or $$$y$$$ is $$$\infty$$$. For all $$$x$$$ we have $$$cnt(x, \infty) = 2(n-200)$$$ or something, the same for $$$y$$$. Long story short, $$$\sum_{i=0}^{99}(cnt(i, \infty) + cnt(\infty, i))$$$ is linear of $$$n$$$.
        • $$$cnt(\infty, \infty) = (n - 200)^2$$$.

        Also since these $$$x$$$ and $$$y$$$ define the number of paths starting from the point with such $$$x$$$ and $$$y$$$, the answer for $$$n$$$ is $$$\sum_x\sum_y cnt(x, y)\cdot ans(x, y)$$$, which is quadratic, as seen above.

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

          I see, I kind of forgot that $$$ans(x, y)$$$ is actually constant here.

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

        Suppose that you start at $$$(0,0)$$$ and make $$$J$$$ jumps (ignoring the constraints that you must stay on the grid). Let $$$dif_x$$$ be the difference between the maximum $$$x$$$ and minimum $$$x$$$ you visit and define $$$dif_y$$$ similarly. Then this sequence of jumps contributes $$$\max(N-dif_x,0)\cdot \max(N-dif_y,0)$$$ to the answer (the number of ways to translate the sequence vertically and horizontally such that you always remain within the grid). Whenever $$$N\ge J\cdot 10$$$ we can replace this with $$$(N-dif_x)\cdot (N-dif_y)$$$, which is quadratic in $$$N$$$.

        You can see that I've used this in the last part of my slow code.

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

In 300, I submitted a simple dfs implementation without knowing it could lead to TLE, and got AC. The search order is NSEW. Is it correct or just lucky because of weak test cases?

Here is my submission: https://community.topcoder.com/stat?c=problem_solution&rm=334600&rd=18145&pm=16349&cr=23027339

→ Reply