### hmehta's blog

By hmehta, history, 10 months ago, ,

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!

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)

• +38

 » 10 months ago, # |   +11 Gentle Reminder: Round begins in 2 hours!
 » 10 months ago, # |   0 I want to get rating += 2.
 » 10 months ago, # | ← Rev. 2 →   0 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:
•  » » 10 months ago, # ^ |   0 neal's solution did not fail because of time limit though. Not sure why it failed.
•  » » » 10 months ago, # ^ |   +1 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.
 » 10 months ago, # |   +21 Failed on the hard another time because of no time to delete the debugging output:(
 » 10 months ago, # | ← Rev. 2 →   +2 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).
•  » » 10 months ago, # ^ |   +8 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.
•  » » » 10 months ago, # ^ |   +1 Of course I know about it — I just introduced the idea of solution which I thought that is faster :)
•  » » 10 months ago, # ^ |   +8 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.