hmehta's blog

Topcoder SRM 778
By hmehta, history, 5 years ago, In English

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!

  • Vote: I like it
  • +16
  • Vote: I do not like it

Comments Comments (25)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

Why don't we get mail for upcoming SRMs? Or is there something in the settings that we need to enable?

→ Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Gentle Reminder: Round begins in 20 mins! :)

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Beginner question -
How to view which submission I made during the coding phase?

→ Reply
»
5 years ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Thanks for the round!

My screencast: https://youtu.be/JDiaeE6qie4

Updated leaderboard: https://colab.research.google.com/drive/11UM7lZQ7-CCJiLAwVH1ENGfoyEEC28qs#scrollTo=e-1f_v5jFwEE

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Those who precomputed till $$$k^2$$$ in 600 using $$$O(k^3)$$$ time, why does it work?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any idea for div2 hard?

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +29 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Time complexity: O̷͍̞̜̲̟̰̺͗ͪ̋͛͟(̸̅̀͊̚͏͉͔̺͎Ṅ̡̼͖͚̟̙̣ͭ͋͂̾ͬ͑ͅͅ ̶̭̭ͩͥ̒ͧ͊̄ͫ̕ͅ×ͥ̎̚҉͇̜͖͚ ̵̸̪ͬ̇͛̓͛͜2̢̲̖͂̏̃̆̒͒́͠^̛̘̥̦̭̼̮̊͞0̧̺̈́ͥͫͥ̇̋ͫ̌̓.̴̛̳̮̻̦̿͐͛ͣ̇͗̊̀ͅ6̡̮͇̌̆̉͒̎̓̇̆̕͝9̡̩̘̫̰̫͕ͭͪ͌̑̆͗ͪ̄ͅ5̜̮͕͉̈͑͐̍̈ͨ√̰̭̗̜̮̘̾͘̕͢N̤͓̗̘͉͔ͤ͂͌̿̔̋́̅͘͠)̧̙͍͙̭̜̩̯͑̔͑̋͆̉̊ͅ.

    → Reply