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) |
Gentle Reminder: Round begins in 2 hours!
I want to get rating += 2.
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:
neal's solution did not fail because of time limit though. Not sure why it failed.
It failed because of overflow.
3 * Q[i]is a little too big forint:(I changed
inttounsignedin the practice room and it passes.Failed on the hard another time because of no time to delete the debugging output:(
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).
They might have consciously increased the time limit to make allow map solutions. The problem already had few ideas to think of:
Adding another idea of thinking about the range of solutions and an additional data structure would have been a little much.
Of course I know about it — I just introduced the idea of solution which I thought that is faster :)
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_boundon this sorted vector instead of map[]orfind. 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
mapis a stupid idea and try something not stupid.