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
Excuse me, how is there 30% of unused code?
<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.
Maybe they just always display that message because nobody cares anyway :D
Oh wait, I hope they don't apply the
__attribute__((unused))to all the code below...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!
Same! I also checked if it's 1000 for sure.
I checked multiple times before the first submission on 1000 in the non-parallel round came, so, thank you :D
+1. Topcoder should find somebody to test their rounds at least for TCO, the place of this problem is just ridiculous.
Don't check how easy it was and facepalm. Check how easy it was, then how many people failed it, and then facepalm!
Oops did anyone else do B in $$$\Theta(\max(D)^6J^5)$$$ ...
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!
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.
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)
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.
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.
Ok, I see. I think I remembered someone talking about some inconsistent performance at latest tco finals but I guess I misremembered something.
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.
After computing it for $$$N=100,101,102$$$ you can use polynomial interpolation to get the answer for any greater $$$N$$$.
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$$$.
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:
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.
I see, I kind of forgot that $$$ans(x, y)$$$ is actually constant here.
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.
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