### hmehta's blog

By hmehta, history, 6 weeks ago,

Topcoder SRM 792 is scheduled to start at 07:00 UTC-4 on October 23, 2020

Registration is now open for the SRM in the Arena or Applet and closes at 06:55 UTC-4. The coding phase will start at 07:05 UTC-4, so make sure that you are all ready to go. Click here to what time it starts in your area.

There are two ways to compete in Algorithm Competitions or Single Round Matches (SRMs). Read here to find which works best for you.

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)

Best of luck!
- the Topcoder Team

• +31

 » 6 weeks ago, # |   -19 Your UI is brainFuck Orz
 » 6 weeks ago, # |   +18 Gentle Reminder: Round begins in 90 mins!
 » 6 weeks ago, # |   +5 The Div1 500 was fun, thanks!Maybe bound to a somewhat messy implementation with the given limits. But the idea is cool regardless.
•  » » 6 weeks ago, # ^ |   +10 Thanks, glad to hear you enjoyed it :)For people who proved an upper bound on their solution, what is the best one you have? (The best one I actually proved about a solution was <= 1945 jumps but it can definitely be improved.)
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   +23 I haven't tried to prove a bound, but my in-contest solution is able to pass system tests with a self-enforced limit of 1200 jumps. With some improvements (sorting things in the right order and refining the greedy algorithm), I have a deterministic solution in the practice room right now that passes system tests with a limit of 950.The main idea is that regardless of how many jumps we've used so far, if we make $2k$ consecutive jumps where $k$ of the jumps are positive and $k$ are negative, we can get an overall jump of any number in $-k^2, -k^2 + 2, \dots, k^2 - 2, k^2$; in other words, any number between $-k^2$ and $k^2$ with the same parity as $k$. This lets us generate any desired delta $d$ in about $2 \sqrt d$ jumps.By choosing an end result in the middle of the range of coordinates, this gives us a worst case of about $50 \cdot 2 \cdot \sqrt{1250}$, which is slightly over 3500.The main improvement we can make on top of this is that before we use this technique, we should greedily use our small jumps to move each frog directly to its target, until jumping directly toward the target is no longer helpful. Doing this with every frog in the right order gets the 950 result above.
•  » » » » 6 weeks ago, # ^ | ← Rev. 2 →   +18 If we're talking about solutions without proof, then my solution from the contest with a small modification (see practice room) passes with a self-imposed limit of 360, while the lower bound is 352 (otherwise there is not enough time to solve 25x0+25x2500).The idea is to pick a random destination position, in random order, and then keep going from larger jump to smaller. For each jump, if there's a way to make it while moving some frog towards its destination without overshooting, we do it, and if there's no such way, then we "save" this jump and this jump minus one for later. In the end, we use the saved pairs of jumps to move the frogs by 1.In case we did not succeed (not enough "1" jumps to make everything correct, or wrong parity), we repeat with different random destination positions and different total number of jumps (close to maximum).I'm pretty sure that it's possible to prove a bound that is similar (maybe not 360, but 400 or so).
 » 6 weeks ago, # |   0 What was the idea of d2 1000?
•  » » 6 weeks ago, # ^ |   +14 It's a fairly standard breadth-first search problem. The thing it wants to teach you is that you don't always have to have cells of the grid = vertices of the graph. Instead, you need to think in terms of states. The factory remains constant, only the two robots move. Thus, at any moment, the entire situation can be described by giving the positions of the two robots. These are the possible states = the vertices of the graph. There are (RC)^2 states. Edges represent all possible actions during the next second. ("If I'm in this state, what states are possible after one second?")
•  » » » 6 weeks ago, # ^ |   0 Wow, Thanks for this problem! It's such a a cool idea to uniquely determine state by combining position of both robots and then applying bfs using it.
•  » » » 6 weeks ago, # ^ |   0 I really liked the problem. Although I didn't have a single clue during the contest. This was my first SRM, thanks for such a beautiful problem(at least for me). I will definitely look forward for coming SRMs.
•  » » 6 weeks ago, # ^ |   0 anyone solved this problem in python? I get TLE in one test case.
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 This problem will be hard to solve in Python with the given TL. There are 40^4 states and 16 times more operations. That's too much for Python in 2 seconds. See for example the following simple code which just tries to add 40**4 integers in a list (very crude simulation of the BFS): q = list() q.append(1) idx = 0 while idx < len(q): num = q[idx] for i in range(16): if len(q) + 1 < 40**4: q.append(idx + i) idx += 1 This runs in almost 4 seconds on a more powerful machine than TC uses.
 » 6 weeks ago, # |   +38 Why this SRM has started at :00 minute, while most of the previous ones started at :05?
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   -16 Sorry, yeah it was an error while setting up the round and we didn't update it as we were close to the starting of the round when we realised. We will be more careful :)
 » 6 weeks ago, # |   0 The editorial is published by the way: https://www.topcoder.com/single-round-match-792-editorials/
•  » » 6 weeks ago, # ^ |   +3 Will it take forever for topcoder to complete system test phase for div2 ? Its been days now.
•  » » » 6 weeks ago, # ^ |   0 Uhm...? It shows it as complete in the Arena (even while I was writing the editorial, which was on the day of the competition)? If you are looking at the Web arena — don't :D
•  » » » » 6 weeks ago, # ^ |   0 It was my first contest on Topcoder , things are not in order at all there :/ It was so hard to even learn to how to write a contest on topcoder ... And now I came to know web arena never shows completed system test phase :/ Can you please help me and tell the difference between Arena and Web-Arena ? Topcoder seems like something alien to me now.
•  » » » » » 6 weeks ago, # ^ |   0 Yeah, the web arena was a good thing to do but they never really completed it (as far as I know they are starting it from scratch?). Anyway, using the Java Applet (see for example this tutorial: https://www.topcoder.com/thrive/articles/setting-up-the-topcoder-java-applet-arena-and-kawigi-editor) is very ancient in terms of an interface, but works.
•  » » » » » 6 weeks ago, # ^ |   0 Also, take a look at — https://www.topcoder.com/community/arena Match results are here : https://community.topcoder.com/stat?c=round_overview
 » 6 weeks ago, # |   +4 @hmehta — It might be useful to add links to the problem in the editorial for easier navigation. Currently I have to go to the problem archive and search for the problem statement.