SRM 682, D2, 1000-Pointer (FriendlyRobot)

James S. Plank

Fri Feb 3 14:42:38 EST 2017

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
tests.sh. MD5 hash: 35555b567830b401bb5aac7643e702be
answers.txt. MD5 hash: eaceaf20930952e0040b23eb540b85cd
Problem Given in Topcoder: February, 2016
Competitors who opened the problem: 271
Competitors who submitted a solution: 21
Number of correct solutions: 5
Accuracy (percentage correct vs those who opened): 1.8%
Accuracy (percentage correct vs those who submitted): 23.8%
Average Correct Time: 35:42.

In case Topcoder's servers are down

Here is a summary of the problem:

A robot accepts four instructions: U, D, L, R, for "move up", "move down", "move left" and "move right", respectively.
The robot starts at the origin.
Each movement is one unit.
The robot is given a list of instructions, whose size is between two and 300.
You are given a number changesAllowed, which is between 0 and the list's size. That is the number of instructions that you are allowed to change.
Return the maximum number of times that the robot returns to the origin after you have changed up to changesAllowed instructions.

The examples

# Instructions                                             changesAllowed   Answer
0 "UULRRLLL"                                                     1             3
1 "ULDR"                                                         0             1
2 "ULDR"                                                         2             2
3 "ULDRRLRUDUDLURLUDRUDL"                                        4             8
4 "LRLDRURDRDUDDDDRLLRUUDURURDRRDRULRDLLDDDDRLRRLLRRDDLRU       47            94
   RLRULLLLLRRRDULRULULRLRDLLDDLLRDLUUDUURRULUDUDURULULLD
   RUDUUURRRURUULRLDLRRRDLLDLRDUULUURUDRURRLURLDLDDUUURRU
   RRLRDLDDULLUDLUDULRDLDUURLUUUURRLRURRDLRRLLLRDRDUUUDRR
   RDLDRRUUDUDDUDDRLUDDULRURRDRUDLDLLLDLUDDRLURLDUDRUDDDD
   URLUUUDRLURDDDDLDDRDLUDDLDLURR" 
5 "UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU      300            150
   UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU
   UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU
   UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU
   UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU
   UUUUUUUUUUUUUUUUUUUUUUUUUUUUUU"
6 "UD"                                                           1              1
7 "UUUUDDLDLRRL"                                                 1              3

Testing yourself

Like the Cryptography Problem, I have a shell script tests.sh, that you can use to test your program. When you run tests.sh, your answer should be identical to answers.txt

Hints

This one took some thought and playing around before I arrived at a solution.

My first pertinent observation is that it always takes an even number of moves to get back to point (0,0).

My second pertinent observation is that if you start at (0,0) after executing instruction i, and you want to end at (0,0) after executing instruction j, then you can determine how many instructions you need to change in O(j-i) time. You do that by simply determining where you would be with no changes. Then it's a simple mathematical function.

Take an example -- suppose the moves are "ULUR" and you want to be at (0,0) in four moves. With no changes, you'll be at cell (0,2). If you change one of those U's to a D, then you'll end up at cell (0,0).

Suppose instead that the moves are "ULLR". Then you'll be at (-1,1) after four moves. If you change the U to an R, or if you change an L to a D, then you'll end up at cell (0,0).

I hope that helps you figure out the mathematical function.

Now, to solve this with dynamic programming, we need a recursion. Try this one out: Let M(i,c) be the maximum times that you reach (0,0) if you start at (0,0) after move i, with c changes left. Obviously, M(0,changesAllowed) solves the problem.

When c=0, you can calculate M(i,0) by simply running through the moves and counting how many times you reach (0,0).

To solve M(i,c), you determine how many changes are required to end at cell (0,0) after i+2 moves. Call that number x. If x ≤ c, then the best way for you to solve the problem by returning to cell (0,0) after two moves is 1 + M(i+2,c-x). Next, determine how many changes are required to end at cell (0,0) after i+4 moves. Again, call that number x If x ≤ c, then the best way for you to solve the problem by returning to cell (0,0) after four moves is 1 + M(i+4,c-x). Keep incrementing that value by two until it's too big, and return the maximum answer.

This memoizes pretty easily, and with the memoization, you can solve the problem within the topcoder constraints.

Let's try an example: UUUUDDLDLRRL, and changesAllowed = 1. The answer to this is 3, if you change the first L to a D.

So, let's start with M(0,1):

The first thing we do is determine how many changes we need to end up at (0,0) in move 2. The answer is one. So, solve M(2,0) and add 1 to the answer. M(2,0) equals one, so the solution here is two.
Now, determine how many changes we need to end up at (0,0) in move 4. The answer is 2, which is greater than c, so there's no answer here.
Now, determine how many changes we need to end up at (0,0) in move 6. The answer is 1, so solve M(6,0) and add 1 to the answer. M(6,0) equals 0, so the solution here is one.
Now, determine how many changes we need to end up at (0,0) in move 8. The answer is 1, so solve M(8,0) and add 1 to the answer. M(8,0) equals 2, so the solution here is three.
Now, determine how many changes we need to end up at (0,0) in move 10. The answer is 1, so solve M(10,0) and add 1 to the answer. M(10,0) equals 1, so the solution here is two.
Finally, determine how many changes we need to end up at (0,0) in move 12. The answer is 1, and M(12,0) is zero. So the solution here is one.

The best of these is three, so that's the answer!

Printouts where you can see the recursion

The following URLs show the examples, where I print out what's going on with the recursion. For the DP cache key, I use (i*301)+c. That's because the maximum size of the instruction string is 300.