Hey All!
Topcoder SRM 780 is scheduled to start at 12:00 UTC -5, Mar 7, 2020. Registration is now open in the Web Arena or Applet and will close 5 minutes before the match begins.
Thanks to misof for writing the problem set and coordinating the round.
This is the seventh SRM of Stage 2 of TCO20 Algorithm Tournament and TCO20 Regional Events Qualification
Stage 2 TCO20 Points Leaderboard | Topcoder Java Applet | Upcoming SRMs and MMs
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) |
Good luck to everyone!
I am unable to register for the contest. It says
There are no more spots available for Single Round Match 780.Same.
Same ((
I have just contacted with administrator and now they are fixing this issue. It seems like the upper limit of participation had set to 250 by mistake, which should be 2250 if usual. I think the issue will be solved in a few minutes.
UPD: It's fixed, thanks admins! Now just register!
I know it's my fault (new to Topcoder), but I find it really confusing that first line that is written as a summary of a test in batch testing is "Success: true" when the code runs. I thought it means sample is correct and submitted (obviously wrong) solution for the first problem. I figured it out only during second task.
My coding skill is so bad :(
Same :(
TL;DR
I have an impression that for 450 problem, on every stage, everyone involved in this SRM, did everything to make the task as much complicated as possible. The statement, the public and chat explanations during the round were useless. They just complicated my understanding even more.
The 450 task explanation was terrible. It is interesting that among 2 wikipedia definitions you have chosen the bad one. The other one is pretty clear:
"The prominence of a peak is "the minimum height necessary to descend to get from the summit to any higher terrain", which can be calculated for a given peak in the following way: for every path connecting the peak to higher terrain, find the lowest point on the path; the key col (or key saddle, or linking col, or link) is defined as the highest of these points, along all connecting paths; the prominence is the difference between the elevation of the peak and the elevation of its key col. See Figure 1."
I also tried to get the explanation of the prominence in the admin room. I gave the 3'rd example: H = {500, 300, 400, 200, 400, 700, 100, 300, 100, 300} Peaks correspond to indices 0, 2, 5, 7, and 9. Their prominences are 300, 100, 700, 200, and 200.
I did not know why the prominence of 400 is 100. I thought that you just take the path to any higher terrain and calculate the highest point on that path and in that case it should be 400-400 = 0. Instead of the correct explanation I got something like: "If you go to the left you will get 300 and this one is important.". When I asked why — how do you calculate that, I got no response...
When I tried to find the definition online, to understand the task, it was already after the contest.
Totally agree. Understanding the statement was the hardest thing to do in this problem.
Why the answer for heights "3 3 1 2 0" is 1?
The only Peak is "2". And we know the prominence of it is 2. So then why the answer is 1?
Prominence is 1 — the only path from 2 to higher mountain is 2 — 1 — 3, that means the prominence is equal to 2 — 1 = 1.
But didn't they say mountain has two side strictly less number? 3-3 does not have such. So I thought 3 is not a mountain.
3 is not a PEAK but it is a MOUNTAIN. The wording in the statement is confusing.
Okay, but then what's the speciality of peak? Prominence is defined by mountain,not peak. So why do we need peak? I feel like however careful I read the statement I am missing something
We only calculate prominences for peaks, but while calculating them we consider all mountains, not just peaks
Why didn't 1000 state that the root cannot be a leaf?
Doesn't it follow from number of vertexes being >= 4 ?
No, it stated that "each vertex that is not a leaf has at least two children", but it didn't specify whether it was possible for the root to have exactly one child (and therefore be a leaf).
(Of course, leaf refers to non-root vertices with degree 1 in this context, but sometimes a root with degree 1 is treated as a leaf.)
How can I set reminder for SRM?
You could check https://clist.by/ regularly. Also, Topcoder sends out SRM related emails if you've signed up for them — I've seen 24 hour reminder emails for SRMs.
Nice to see the editorial for SRM 780 out in the older (and better) format: https://www.topcoder.com/single-round-match-780-editorials/
Would be great if perhaps an email could be sent out once the editorial is published (that's how it used to be many years back in Topcoder).
We have started using the same stats again :)
Glad you like it :)
Can anyone explain Div2 Hard/Div1 Easy problem's approach more precisely.
There are a couple of observations, which I think break the problem down easily. ( Notation: We use $$$S_N$$$ for $$$\dfrac{N*(N+1)}{2}$$$ )
1). Each possible outcome of the whole series of games is completely determined by the subset of games won by one player. ( because, the rest of the games must be won by the second player )
2). Consider $$$S$$$ to be a subset of $$$ \{ 1,2,...,N \} $$$, which denotes the subset of games won by the first player ( you ). Then, your total score is $$$ R = Sum(S) = \sum\limits_{x \in S} x $$$. And, the opponents total score is simply $$$ S_N - R $$$.
Now, consider all subsets $$$S$$$ of $$$\{1,2,....,N\} \setminus {G}$$$. And count subsets $$$S$$$, if $$$ R < S_N - R $$$ and $$$ R + G > S_N - R - G $$$. ( note that these subsets are exactly those in which winning game $$$G$$$ matters )
Now, The probability that game $$$G$$$ matters is
$$$ \dfrac{ \text{Number of scenarios where game G matters} }{ \text{Total number of scenarios} } = \dfrac{ \text{Count of above subsets} }{ 2^N } $$$.
UPDATE: Small error here, $$$ \text{Total number of scenarios} = 2^{N-1} $$$, since we are only considering subsets of $$$ \{ 1, 2, ..., N \} \setminus G $$$
Implementation is tricky, because there is overflow, so you must maintain probabilities instead of SOS dp. ( $$$ 2^{100} $$$ is too large )
The SRM editorial takes an older probability distribution (starting with prob(0) = 1.0), and keeps splitting the current probability at any position prob[s] towards prob[s + g] (where s = each possible sum, and g = each element), in somewhat of a knapsack implementation. Any ideas how/why that works?
Counting the "good" subsets, which is, subsets with a particular sum is exactly a Knapsack problem. But instead of $$$dp[i][j]$$$ denoting number of ways of making sum $$$j$$$ using $$$i$$$ elements, we have $$$dp[i][j]$$$ denotes probability of making sum $$$j$$$ using $$$i$$$ elements. So, only the transition is a bit different from usual knapsack.
I have implemented both the solutions. Notice that the only difference is that to maintain probabilities, we divide by $$$2$$$ along the way, instead of dividing by $$$2^{N-1}$$$ at the end.
Simple Knapsack
Probability DP
You don't see the difference for small cases, but there is huge difference in large case. ( PS: tourist hacked me using this )