### hmehta's blog

By hmehta, history, 3 months ago, ,

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.

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!

• +94

 » 3 months ago, # |   +91 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
•  » » 3 months ago, # ^ |   +8 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).
•  » » 3 months ago, # ^ |   0 500 was nice — why do fractions instead of floats though?
•  » » » 3 months ago, # ^ |   +43 Because you could squeeze $N^3$ then by skipping states with low probability.
•  » » 3 months ago, # ^ |   +30 Wonderful round! Thank you and congratulations.D1 500 especially with the bear Lemac had clean and delicious solution.
 » 3 months ago, # |   -10 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.
•  » » 3 months ago, # ^ |   +27 Registration is only available starting 24 hours before the competition
•  » » » 3 months ago, # ^ |   0 I see. Thanks.
 » 3 months ago, # |   +9 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?
•  » » 3 months ago, # ^ | ← Rev. 2 →   +7 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.
 » 3 months ago, # |   0 Gentle Reminder: The Round begins in less than 2 hours and 50 mins
•  » » 3 months ago, # ^ |   +12 Round begins in 10 mins :)
 » 3 months ago, # |   +40 Hints: div1-250 MeanMediangreedy div1-500 PBGthe problem is easier if Limak is a grizlly bear div1-1050 LShapeIt'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
•  » » 3 months ago, # ^ |   +6 editorial of div2 1000 please
•  » » » 3 months ago, # ^ |   0 Div 1-250 is Div2-1000
•  » » » » 3 months ago, # ^ |   0 xdNo, it isn't. But solution to div2-1000 is mentioned in div1-250 editorial.
•  » » » » » 3 months ago, # ^ |   -9 O_o Congratulations.
 » 3 months ago, # | ← Rev. 9 →   -27 _
•  » » 3 months ago, # ^ |   +1 I think it's not, answer will be 162, i also checked brute force one, it also gives 162.
•  » » » 3 months ago, # ^ | ← Rev. 4 →   -27 _
•  » » » » 3 months ago, # ^ |   +7 how you sure about i<=j<=k? you have to sort i,j,k
 » 3 months ago, # |   0 Auto comment: topic has been updated by hmehta (previous revision, new revision, compare).
 » 3 months ago, # | ← Rev. 2 →   +6 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
 » 3 months ago, # | ← Rev. 2 →   +51 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!
•  » » 3 months ago, # ^ |   +16 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).
•  » » 3 months ago, # ^ |   +8 It's not completely different, author's solution calculates prefix sums of the same DP.
•  » » » 3 months ago, # ^ |   -9 Что слишком умный? Поздравляю с 10 местом папаша. Удачи в жизни, слушайся маму и помагай родителям. Ты никого здесь не обижай. У меня папа MikeMirzayanov, я ему скажу и ты серым станешь, как я.
•  » » 3 months ago, # ^ |   +13 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 xudyh 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.
•  » » » 3 months ago, # ^ |   0 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
•  » » » » 3 months ago, # ^ |   +21 Xd it wasn't supposed to sound that way
 » 3 months ago, # |   +18 How would google know/contact if somebody is interested?
•  » » 3 months ago, # ^ |   0 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).
•  » » » 3 months ago, # ^ |   +3 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.
•  » » » » 3 months ago, # ^ |   0 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?
 » 3 months ago, # |   +35 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 of d and $C = 11$ is the number of possible grade) 3 tourist, 5 Um_nik, 9 lyrically, 10 IH19980412, 12 ainta, 29 mnbvmar, 33 ariacas, 34 jy_25, 70 roll_no_1, 80 fetetriste, 100 scott_wu, 101 Persian.Gulf, 103 beet, 109 zhongzihao, 129 CLown1331, 140 Foyaz05, 143 Noureldin2022, 148 seica, 149 Tsutajiro, 160 koyumeishi, 162 prprprpony, 169 kzyKT 
•  » » 3 months ago, # ^ |   +5 xdCan you please tell me how did you get this list other than going through all submissions?
•  » » » 3 months ago, # ^ |   +19 I got this list by staying up late and OCD :)
•  » » » » 3 months ago, # ^ |   +38 OCD people don't post a list like that...
•  » » 3 months ago, # ^ |   +6 tourist's code seems more like $O(N^3 * C^2)$
•  » » 3 months ago, # ^ |   +18 Cool stats! Though my solution is actually $O(N^3C^2)$ and doesn't sort d.
•  » » » 3 months ago, # ^ |   0 Even um_nik's
 » 3 months ago, # |   +8 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 :(
 » 3 months ago, # |   0 Where can I find Div.2 Editorials ? Errichto