hmehta's blog

By hmehta, history, 6 weeks ago, In English

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.

Learn more about problem writing and testing opportunities.

Choose Your Competition Arena

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

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)

Learn more about problem writing and testing opportunities.

Best of luck!
- the Topcoder Team

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

»
6 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

Your UI is brainFuck Orz

»
6 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

Gentle Reminder: Round begins in 90 mins!

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

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

        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, # |
  Vote: I like it 0 Vote: I do not like it

What was the idea of d2 1000?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    anyone solved this problem in python? I get TLE in one test case.

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

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

Why this SRM has started at :00 minute, while most of the previous ones started at :05?

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it -16 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it
»
6 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

@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.