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
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!
Why don't we get mail for upcoming SRMs? Or is there something in the settings that we need to enable?
You can subscribe to the Competitive Programming Newsletter and Updates on this page. https://www.topcoder.com/community/competitive-programming
Showing this.
I got my 24 hour reminder. Too bad I have other stuff and there's no sane way to compete from a soyphone.
Gentle Reminder: Round begins in 20 mins! :)
Beginner question -
How to view which submission I made during the coding phase?
You can use Topcoder Stat.
Here are your submissions for 778.
I want to see in coding phase. During contest. This I couldn't find a way so I just resubmitted.
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?
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.
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.
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.
Thanks for the round!
My screencast: https://youtu.be/JDiaeE6qie4
Updated leaderboard: https://colab.research.google.com/drive/11UM7lZQ7-CCJiLAwVH1ENGfoyEEC28qs#scrollTo=e-1f_v5jFwEE
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 ?
Editorial (from arena): https://www.overleaf.com/read/cmxjtmzgmrbt
Apparently 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 :)
Is TeX display broken? MikeMirzayanov
I didn't know of the $$$O(k^3)$$$ solution and neither did the tester.
Those who precomputed till $$$k^2$$$ in 600 using $$$O(k^3)$$$ time, why does it work?
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.
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)
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.
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.
Any idea for div2 hard?
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 oneois 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.
Time complexity: O̷͍̞̜̲̟̰̺͗ͪ̋͛͟(̸̅̀͊̚͏͉͔̺͎Ṅ̡̼͖͚̟̙̣ͭ͋͂̾ͬ͑ͅͅ ̶̭̭ͩͥ̒ͧ͊̄ͫ̕ͅ×ͥ̎̚҉͇̜͖͚ ̵̸̪ͬ̇͛̓͛͜2̢̲̖͂̏̃̆̒͒́͠^̛̘̥̦̭̼̮̊͞0̧̺̈́ͥͫͥ̇̋ͫ̌̓.̴̛̳̮̻̦̿͐͛ͣ̇͗̊̀ͅ6̡̮͇̌̆̉͒̎̓̇̆̕͝9̡̩̘̫̰̫͕ͭͪ͌̑̆͗ͪ̄ͅ5̜̮͕͉̈͑͐̍̈ͨ√̰̭̗̜̮̘̾͘̕͢N̤͓̗̘͉͔ͤ͂͌̿̔̋́̅͘͠)̧̙͍͙̭̜̩̯͑̔͑̋͆̉̊ͅ.