Hey All!
UPD — Editorials https://www.topcoder.com/single-round-match-768-editorials/
Topcoder SRM 768 is scheduled to start at 11:00 UTC -4, Oct 10, 2019. Registration is now open for the SRM in the Web Arena or Applet and will close 5 minutes before the match begins.
Interested in working at Google? Well as a #TCO19 sponsor, they are looking to hire folks like you! Join us for SRM 768 to opt into their exciting job opportunities!
Thanks to Errichto for writing the problems for the round. Also thanks to xudyh and misof for testing the problem set.
This is the first SRM of Stage 1 of TCO20 Algorithm Tournament.
Stage 1 TCO20 Points Leaderboard | Topcoder Java Applet | Next SRM 769 — Oct 19, 07:00 UTC-4
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!
As I said in the other comment, I'm quite proud of problems. They should be fun to solve, so consider participating.
Also, for a moment I thought that misof finally participated in some CF round and got red :D
Yeah, they were pretty nice. I wasted a lot of time on various slightly wrong assumptions in 500, then switched to 250 and all of a sudden solved both lol (I guess — I'm outside and can't open the arena onva phone).
500 was nice — why do fractions instead of floats though?
Because you could squeeze $$$N^3$$$ then by skipping states with low probability.
Wonderful round! Thank you and congratulations.
D1 500 especially with the bear Lemac had clean and delicious solution.
Hi. I know this may not be a good question but I really cannot find the registration button on Web Arena (in fact I cannot even find this match). If I remember this correctly, the upcoming SRMs would be shown in the Active Matches section but I can only find the past SRM767. Thanks for your help.
Registration is only available starting 24 hours before the competition
I see. Thanks.
How will the score for each SRM contribute in TCO20 leaderboard? And these points will be used for selection in TCO regionals like they were used in TCO19?
The points will be awarded according to your placement after the match:
Division 1:
1st Place: 5 points
2nd-10th Place: 4 points
11th-25th Place: 3 points
All other positive scores: 2 points
Division 2:
1st Place: 3 points
2nd-10th Place: 2 points
All other positive scores: 1 point
Points you gather in the next stage((Jan — March) will be used for TCO Regionals Qualification. More on that will be announced later.
Gentle Reminder: The Round begins in less than 2 hours and 50 mins
Round begins in 10 mins :)
Hints:
greedy
the problem is easier if Limak is a grizlly bear
It's almost correct to take the sum over $$$min(x1-x2, x1-x3, x2-x3) + min(y1-y2, y1-y3, y2-y3)$$$. For what cases this doesn't work? Try to form it in a way that doesn't produce any cases.
Editorial for div1 problems: https://docs.google.com/document/d/1XbeqZMHsNjv2J3h8x0PsJnBn4IV8llJx9hT39iQkOcY/edit?usp=sharing
editorial of div2 1000 please
Div 1-250 is Div2-1000
xd
No, it isn't. But solution to div2-1000 is mentioned in div1-250 editorial.
_
I think it's not, answer will be 162, i also checked brute force one, it also gives 162.
_
how you sure about i<=j<=k? you have to sort i,j,k
Div2 1000 solution: Let $$$dp[i][s][p]$$$ be the number of ways of grading subjects from $$$i...n$$$, where sum $$$s$$$ is already achieved and $$$p$$$ denotes the number of grades >= the median. You can arbitrarily assign any grade to position $$$i$$$ and add $$$dp[i][s + grade_i][p + (grade_i >= median)]$$$ to the current dp value. Our goal is to reach a sum of $$$mean*n$$$ while keeping $$$p > n / 2$$$ Finally the answer is $$$dp[1][0][0]$$$. Code
I have a completely different solution for the medium: let's assume that instead of 3 types of bears, we have N types of bears! Then it's pretty straightforward to compute dp[i,j] — expected place of j-th bear in a tournament with i bears. And then we return the average of the expected places of the polar bears.
Thanks a lot for the round!
My solution is basically the same, just from a bit different concept: we can choose the strength of other polar bears in such a way that Limak has $$$G+k$$$ stronger and $$$B+(P-1-k)$$$ weaker opponents; since everything is symmetrical there, the answer is the average of his expected places for all $$$k$$$. When $$$k$$$ is fixed, it's just trivial $$$O(N^2)$$$ DP, and it's the same DP for all $$$k$$$ since its states are (number of remaining stronger bears, weaker bears).
It's not completely different, author's solution calculates prefix sums of the same DP.
Что слишком умный? Поздравляю с 10 местом папаша. Удачи в жизни, слушайся маму и помагай родителям. Ты никого здесь не обижай. У меня папа MikeMirzayanov, я ему скажу и ты серым станешь, как я.
I couldn't see any direct solution (without subtracting grizzly and brown) and later misof came up with same solution as mine, so I thought there is no reasonable alternative. It turns out that jqdai0815 had something else but we assumed it's the same thing. I'll make sure next time to ask a tester about each solution or just read their code. Maybe I would try to modify the problem a little bit to make only one solution work but well, that's all fine.
And thanks for explaining your solution, Petr and Xellos.
Your post sounds like something terrible happened and I don't understand why. It's perfectly fine that there is more than one solution unless one of them is significantly simpler than everybody expected
Xd it wasn't supposed to sound that way
How would google know/contact if somebody is interested?
We will share your profile details (like ratings, match performance etc) and contact email with Google if you opted-in — (either on google form or the arena survey you must have encountered while registering for the round).
Speaking of Google, could you please fix your Chrome version website? I could have not displayed the problem archive on Chrome. Now I can't even log in. It would be nice to support the browser of your sponsor.
hmehta I think that you may have something wrong with your routing. Today I was going through overall rating and was asking db queries to get me 200 handles starting from something. Suddenly your server became unavailable (obviously because of the heavy load, which I generated...) and I'm still being rerouted to the broken one, even after I refresh. When I opened an incognito window, I was redirected to the working server.
Could you please fix your infra?
list of contestants who solved div1-easy with $$$O(N^2 C^3)$$$ DP after sorting
d(instead of $$$O(N)$$$ greedy) sorted by rank ($$$1 \le N \le 49$$$ is the length ofdand $$$C = 11$$$ is the number of possible grade)xd
Can you please tell me how did you get this list other than going through all submissions?
I got this list by staying up late and OCD :)
OCD people don't post a list like that...
tourist's code seems more like $$$O(N^3 * C^2)$$$
Cool stats! Though my solution is actually $$$O(N^3C^2)$$$ and doesn't sort
d.Even um_nik's
Can someone please explain the solution of DIV1-medium a bit more. As suggested in editorial I have solved sushi from atcoder DP contest but even after that it is unclear to me :(