hmehta's blog

By hmehta, history, 4 months ago, ,

Hey All!

Topcoder SRM 778 is scheduled to start at 12:00 UTC -5, Feb 15, 2020. Registration is now open in the Web Arena or Applet and will close 5 minutes before the match begins.

Thanks to jy_25 for writing the problems. Also thanks to a.poorakhavan and misof for testing the problem set and coordinating the round.

This is the fifth SRM of Stage 2 of TCO20 Algorithm Tournament and TCO20 Regional Events Qualification

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!

• +16

 » 4 months ago, # | ← Rev. 2 →   +16 Why don't we get mail for upcoming SRMs? Or is there something in the settings that we need to enable?
•  » » 4 months ago, # ^ |   +8 You can subscribe to the Competitive Programming Newsletter and Updates on this page. https://www.topcoder.com/community/competitive-programming
•  » » » 4 months ago, # ^ | ← Rev. 4 →   +17 Showing this.
•  » » » » 4 months ago, # ^ |   0 Will get it resolved asap!
•  » » 4 months ago, # ^ |   +3 I got my 24 hour reminder. Too bad I have other stuff and there's no sane way to compete from a soyphone.
 » 4 months ago, # |   +11 Gentle Reminder: Round begins in 20 mins! :)
 » 4 months ago, # |   0 Beginner question -How to view which submission I made during the coding phase?
•  » » 4 months ago, # ^ |   0 You can use Topcoder Stat.Here are your submissions for 778.
•  » » » 4 months ago, # ^ |   0 I want to see in coding phase. During contest. This I couldn't find a way so I just resubmitted.
 » 4 months ago, # | ← Rev. 6 →   0 Is there any way to view which case I failed in the system tests? Or do I have to wait for it to be added to practice and run it there?Basically my idea for the Div2 1000 was to try all n^2 possibilities for the bottom left point, for each rectangle who's bottom left point is below and left of it, stores its intersecting area. If at least k such areas exist sort in descending order and take max with the k-th value. Could someone please provide me with a countercase?
•  » » 4 months ago, # ^ |   0 Your Algorithm is indeed correct. It might be possible that the way you evaluated the kth value is wrong. Remember to use multiset instead of set over there.
•  » » 4 months ago, # ^ |   0 When you sign in on the site, you could view failed system tests or successful challenges in your room overview after some reasonable time of SRM's end. I'm sorry, but I know only path with 5 clicks (Member Profile -> SRM -> Past SRM -> Room Statistics -> Class Name) to get there.
 » 4 months ago, # |   +6 Easy is so bad for the topcoder format. Since the servers are either all slow or some are just inconsistently slow, it's impossible to guess if someones n^3log is TLE or not. I bet there are countercases to at least half of passed solutions.
 » 4 months ago, # |   +13 Thanks for the round!My screencast: https://youtu.be/JDiaeE6qie4
 » 4 months ago, # |   0 Hard is a joke.What's with limitations in Medium? Were you trying to cut $k^{3} / 2$ from $k^{3}$ ? Or maybe you have faster solution? If so, why not 2000 ?
•  » » 4 months ago, # ^ | ← Rev. 2 →   +13 Editorial (from arena): https://www.overleaf.com/read/cmxjtmzgmrbtApparently there's a O(k**2*log(m)) solution in medium, and in hard the intended solution is to do DP on "non-broken" profile and use convolutions to recover from this mistake :)
•  » » 4 months ago, # ^ |   0 Is TeX display broken? MikeMirzayanov
•  » » 4 months ago, # ^ |   0 I didn't know of the $O(k^3)$ solution and neither did the tester.
 » 4 months ago, # |   0 Those who precomputed till $k^2$ in 600 using $O(k^3)$ time, why does it work?
•  » » 4 months ago, # ^ |   +13 Because if we have two partial sums with the same remainder modulo the most optimal step, then we can replace everything between them with this most optimal step, so we never need more than k non-optimal steps.
•  » » » 4 months ago, # ^ |   0 Oh, that's nice! Combining the two approaches, we can also get O(k^2 logk) by calculating f(k^2-2k) ... f(k^2)
•  » » 4 months ago, # ^ |   +11 Let's find the best thing by value/weight, let it weight be b. I state that we won't use more than b other things combined. If we can find a subset of other things which total weight is divisible by b, then we can change it to correct number of things with weight b, it will be not worse. If we have at least b other things, we have such a subset, that's a classical problem.Your solution is nice, actually.
 » 4 months ago, # | ← Rev. 3 →   +8 Related to solving the 250 in $n^3$, is it possible to solve the following problem:Given an array of size $n$, find the $k$-th largest item of every prefix of the array.in $O(n)$ rather than $O(n \log{k})$?It's possible to do it in $O(n)$ when the array elements are in the range [0, $n$) (which solves the 250 in $n^3$ after compression), but I'm curious whether or not it's possible in general.
 » 4 months ago, # |   0 Any idea for div2 hard?
 » 4 months ago, # | ← Rev. 2 →   +29 Actually the Div1 Hard can be solved in O(N × 20.695√N). In this way, instead of transitioning DP to the next row, we will "slide" one cell — which means, maintaining the state of cell (x, y), (x, y+1), ..., (x, W), (x+1, 1), ..., (x+1, y-1). In this way DP transition is trivial doing in time complexity proportional to "the number of state in DP". Such technique is called "frontier DP algorithm" in Japan. Normally there are 2W states in DP, but we can reduce: If you regard 1x1 domino as "vertical domino", the horizontal domino has at least size 1x2, which means, we cannot place ooo...o..oo. only with horizontal domino because one o is isolated. So, the number of state will be near to fibonacci number FW, which means we can solve this problem in O(HW × FW). Assuming H≧W and N=HW, the time complexity is O(N × 20.695√N), which means we can solve it even if N=600.
•  » » 4 months ago, # ^ |   +6 Time complexity: O̷͍̞̜̲̟̰̺͗ͪ̋͛͟(̸̅̀͊̚͏͉͔̺͎Ṅ̡̼͖͚̟̙̣ͭ͋͂̾ͬ͑ͅͅ ̶̭̭ͩͥ̒ͧ͊̄ͫ̕ͅ×ͥ̎̚҉͇̜͖͚ ̵̸̪ͬ̇͛̓͛͜2̢̲̖͂̏̃̆̒͒́͠^̛̘̥̦̭̼̮̊͞0̧̺̈́ͥͫͥ̇̋ͫ̌̓.̴̛̳̮̻̦̿͐͛ͣ̇͗̊̀ͅ6̡̮͇̌̆̉͒̎̓̇̆̕͝9̡̩̘̫̰̫͕ͭͪ͌̑̆͗ͪ̄ͅ5̜̮͕͉̈͑͐̍̈ͨ√̰̭̗̜̮̘̾͘̕͢N̤͓̗̘͉͔ͤ͂͌̿̔̋́̅͘͠)̧̙͍͙̭̜̩̯͑̔͑̋͆̉̊ͅ.