TCO19 Algorithm Round 2B and Parallel Rated Round is scheduled to start at 11:00 UTC -4 on June 4, 2019. Registration is open for the Round in the Arena or Applet and it closes 5 minutes before the match begins, so make sure that you are all ready to go.
Click here to see what time it starts in your area.
Algorithm Round 2 Qualified Competitors (https://tco19.topcoder.com/algorithm/byes/, https://tco19.topcoder.com/algorithm/round-1a and https://tco19.topcoder.com/algorithm/round-1b) are eligible to compete in Round 2B. Those who have already qualified for Round 4 (https://tco19.topcoder.com/algorithm/round-4) from online stages are not eligible to compete.
All the best!
i have not qualified for the round 2 is there still a way to qualify for the regionals?
TCO19 Algorithm Rounds are not related to regional qualification! Round 1a, Round 1b and Members who got a bye are eligible for this!
Regionals have their separate qualification — This year performance in the period of Feb-April was used for qualifying members for the regionals :)
what is the exact criteria for the qualifications to the regionals?
Here are the details: https://tco19.topcoder.com/regional-events/
so now there is no chance to qualify for tco ri8?
Yes, however if there are seats left we will open it for members on first come first serve basis!
what do you mean by that? so anyone would be able to attend the regionals?
Which regional are you looking to join?
So initially we will roll out invitation to the members on the leaderboard: -https://tco19.topcoder.com/regional-events/south-america/leaderboards
-https://tco19.topcoder.com/regional-events/japan/leaderboards
-https://tco19.topcoder.com/regional-events/china/leaderboards
Later some members backout or are not able to attend then we open the leftover tickets on first come first serve basis.
i am looking for india regionals. could you pls give me a ticket if someone backs out?
It was two days ago....
Upvote if you didn't like first problem
It take me several minutes to correct condition number_less_than_goal $$$ \lt (n + 1) / 2$$$, number_greater_than_goal $$$\le n / 2$$$ :)
I found the second problem to be much easier than the first one
Can you please explain your approach?
OEIS
Can Someone explain approach for 2nd Problem?? Thanks in advance.
Just try all divisors of $$$n$$$. For each divisor $$$d$$$, call the same algorithm recursively on $$$n/d-1$$$. During steps other than the first, don't consider $$$d=1$$$.
In fact, this problem is OEIS A167439.
Is there any analysis for the complexity of the algorithm?
Yeah, I saw that pretty quickly but then I spent over 30 minutes staring at the problem and trying to figure out what additional shortcuts needed to be done and couldn't come up with any.
I felt pretty certain that doing that would require calling the getAllDivisors() function on too many unique values to be able to run in time because of the subtractions by 1.
Let test N and N-1 separately, so we can assume that there's no 1 in sequence.
Take a look at $$$a_0$$$, each consequent number is divisible by $$$a_0$$$, so N is also divisible by $$$a_0$$$.
Now if we divide everything by $$$a_0$$$ we'll receive another sequence with sum of $$$\frac{N}{a_0}$$$ and first element 1. Let's drop that 1 and solve the problem for $$$\frac{N}{a_0} - 1$$$. Just build dp on top of that.
Is there a link for schedule of future TCO online rounds? The TCO algorithm page is absolutely unnavigatable.
clist.by :>
I managed to find it on TCO website :) https://tco19.topcoder.com/algorithm/algorithm-rules
Hard looks interesting. How to solve?
Outline (I'm on the phone now):
Obviously, optimal strategy is same for both players.
If d is max difference, you will never play more than 2d+1 because playing 1 is at least as good for all possible choices of the other player. (This is the main observation you needed.)
Then, write linear equations for the 2d+1 probabilities using "principle of indifference", there is a unique solution. (Some more proofs needed to argue correctness.)
Based on discussion with Egor.
Basic lemma from game theory: For all $$$p_k \gt 0$$$ we should have expected winning of exactly $$$0$$$ against pure strategy "say $$$k$$$".
$$$p_1$$$ is not zero, otherwise we can shift everything to the left. So, $$$\sum_{k=2}^{d+1} p_k \ge 1/2$$$. Now it is easy to see that for all $$$k \gt 2d+1$$$ $$$p_k=0$$$ (because we are certainly winning strictly more than 0 against this pure strategy). Now we can see than $$$p_k=p_{2d+2-k}$$$ (because everything is symmetric), and we have $$$d+1$$$ variables and $$$d+1$$$ linear equations.
Can you explain why the expected winning is exactly 0?
Because the two players are symmetric? So their expected winning should be the same.
No, I'm asking why the expected winning is zero against the pure strategy.
The optimal strategy is a linear combination of the pure strategies. The optimal strategy scores $$$0$$$ against itself, and never less than $$$0$$$ against any strategy. The rest is linearity of expectation.
That's not the complete explanation. It is not obvious that optimal strategy must not ever lose against every possible strategy, opponent don't know if we use optimal strategy or not. But nevertheless it is true, by minimax theorem.
With proper eps in LP I passed the test cases (Maybe it will fail in some test case).
If I'm not wrong then positive score in round 3 fetches a topcoder TShirt?
Right. Also looks like getting positive score was enough to qualify to Round 3 from all prev rounds. So you weren't actually competing against other people, only against yourself :D
Upd. not really, only 200 people qualify to Round 3, I thought it was 250
Where we can find editorials for this round ??
I think it's fair that if less than 200 have positive score on round 2A (in our case 132), then on round 2B 200+(200-round_2a_qualified) go on. Proof by (incorrect) feature scaling :)
That would be a clear violation of the rules!
I don't see how it violates a 404 HTTP Error, but it is morally OK, as Round 2A failed to get the top 200 contestants, and I haven't checked but I'm almost sure some failed qualificants from round 2A advanced from 2B
Does Topcoder still have problems with sending T-shirt to Russia?