hmehta's blog

TCO19 Algorithm WildCard and Parallel Rated Round
By hmehta, history, 5 years ago, In English

Hey All!

TCO19 Algorithm WildCard and Parallel Rated Round are scheduled to start at 12:00 UTC -4, August 17, 2019.

Registration is now open for both the matches in the Web Arena or Applet and will close 5 minutes before the match begins.

Good luck to everyone!

Topcoder Java Applet | Next SRM 765 — August 23

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)
  • Vote: I like it
  • +38
  • Vote: I do not like it

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

Gentle Reminder: Round begins in 2 hours!

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

I want to get rating += 2.

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

Adding steps-1 rooks instead of steps rooks passed the examples in the last problem. D: Also, it seems that neal [almost] managed to pass a $$$O(N^3)$$$ solution for the second problem. D:D:

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

    neal's solution did not fail because of time limit though. Not sure why it failed.

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

      It failed because of overflow. 3 * Q[i] is a little too big for int :(

      I changed int to unsigned in the practice room and it passes.

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

Failed on the hard another time because of no time to delete the debugging output:(

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

Good problemset overall. I do like 600-pts problem. The only sad thing is about my first-ever last place in SRM in my life, with getting -75.00 pts :)

However, for 600-pts problem, I thought that there are solutions which is far away faster (about 0.1 seconds) than 7 seconds of time limit. We don't need map or unordered-map, because the sum of $$$W$$$ and $$$X$$$ are less than $$$5.5 \times 10^8$$$ for any case. Since the sequence is kind of random, I expect $$$c_k \leq 7$$$ for all $$$k$$$, where $$$c_k$$$ is the number of ordered pair $$$(i, j)$$$ where $$$Q_i + Q_j = k$$$. So, we can use data structure which is similar to bitset. It will also fit in memory limit of 256MB, because we only need $$$\frac{5.5 \times 10^8}{21}$$$ 64-bit integers.

Anyway, my solution has failed in challenge phase, so I'm not sure about $$$c_k \leq 7$$$ (but almost sure).

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

    They might have consciously increased the time limit to make allow map solutions. The problem already had few ideas to think of:

    • First element will always be even, only possibility being $$$Q_0$$$
    • Now one needed to reduce the $$$N^3log(N)$$$ to $$$N^2log(N)$$$
    • In addition the implementation of $$$map$$$ also involved care, to avoid memory constrains.

    Adding another idea of thinking about the range of solutions and an additional data structure would have been a little much.

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

      Of course I know about it — I just introduced the idea of solution which I thought that is faster :)

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

    Yes, there are much faster solutions and even with the same complexity and general idea as the one with map. For example, you can just sort all $$$Q_i-Q_j-Q_0$$$ which are in the range $$$[2Q_0, 2Q_j]$$$, remove duplicates and use lower_bound on this sorted vector instead of map [] or find. See my solution in practice, it runs in less than a second and less than 64 MB.

    I agree that 600 is a nice problem, but I'm pissed off that the memory limit wasn't increased along with the time limit. A map with $$$2500^2$$$ elements already has trouble fitting into it (or exceeds it, details). If the basic idea of the problem is allowing whatever with the right idea to pass, the ML should be extra large too. If it's not, then there's no point in increasing the TL, just let people totally fail on example 1, realise map is a stupid idea and try something not stupid.

    → Reply