`I -- BFS solution`\n\nWell, the BFS solution is straightforward: we can keep track of all the possible positions of the racecar after `n` instructions (`n = 0, 1, 2, 3, 4, ...`) and return the smallest `n` such that the target position is reached. Naive BFS will run at `O(2^n)` since for each position we have two choices: either accelerate or reverse. Further observations reveal that there may be overlapping among intermediate states so we need to memorize visited states (each state is characterized by two integers: car position and car speed). However, the total number of unique states still blows up for large target positions (because the position and speed can grow unbounded), so we need further pruning of the search space.\n\n---\n\n`II -- DP solution`\n\nDP solution works by noting that after each reverse, the car\'s speed returns to `1` (the sign can be interpreted as the direction of the speed). So we can redefine the problem in terms of the position of the car while leave out the speed: let `T(i)` be the length of the shortest instructions to move the car from position `0` to position `i`, with initail speed of `1` and its direction pointing towards position `i`. Then our original problem will be `T(target)`, and the base case is `T(0) = 0`. Next we need to figure out the recurrence relations for `T(i)`.\n\nNote that to apply the definition of `T(i)` to subproblems, the car has to start with speed of `1`, which implies we can only apply `T(i)` right after the **reverse** instruction. Also we need to make sure the direction of the initial speed when applying `T(i)` is pointing towards the final target position.\n\nHowever, we don\'t really know how many **accelerate** instructions there should be before the **reverse** instruction, so theoretically we need to try all possible cases: zero `A`, one `A`, two `A`, three `A`, ... and so on. For each case, we can obtain the position of the car right before the **reverse** instruction, which will be denoted as `j = 2^m - 1`, with `m` the number of `A`\'s. Then depending on the relation between `i` and `j`, there will be three cases:\n\n1. `j < i`: the reverse instruction is issued before the car reaches `i`. In this case, we cannot apply the definition of `T(i)` to the subproblems directly, because even though the speed of the car returns to `1`, its direction is **pointing away from** the target position (in this case position `i`). So we have to wait until the second reverse instruction is issued. Again, we don\'t really know how many accelerate instructions there should be in between these two reverse instructions, so we will try each of the cases: zero `A`, one `A`, two `A`, three `A`, ..., etc. Assume the number of `A` is `q`, then the car will end up at position `j - p` right before the second reverse instruction, where `p = 2^q - 1`. Then after the second reverse instruction, our car will start from position `j - p` with speed of `1` and its direction pointing towards our target position `i`. Since we want the length of the total instruction sequence to be minimized, we certainly wish to use minimum number of instructions to move the car from `j - p` to `i`, which by definition will be given by `T(i-(j-p))` (note that in the definition of `T(i)`, we move the car from position `0` to position `i`. If the start position is not `0`, we need to shift both the start and target positions so that the start position is aligned with `0`). So in summary, for this case, the total length of the instruction will be given by: `m + 1 + q + 1 + T(i-(j-p))`, where `m` is the number of `A` before the first `R`, `q` is the number of `A` before the second `R`, the two `1`\'s correspond to the two `R`\'s, and lastly `T(i-(j-p))` is the length of instructions moving the car from position `j - p` to the target position `i`.\n\n2. `j == i`: the target position is reached without any reverse instructions. For this case, the total length of the instruction will be given by `m`. \n\n3. `j > i`: the reverse instruction is issued after the car goes beyond `i`. In this case, we don\'t need to wait for a second reverse instruction, because after the first reverse instruction, the car\'s speed returns to `1` and its direction **will be pointing towards** our target position `i`. So we can apply the definition of `T(i)` directly to the subproblem, which will be `T(j-i)`. Note that not only do we need to shift the start and target positions, but also need to swap them as well as the directions. So for this case, the total length of the instructions will be given by `m + 1 + T(j-i)`. \n\nOur final answer for `T(i)` will be the minimum of the above three cases.\n\n---\n\n`III -- Intuitive explanation of the optimizations`\n\nAs I mentioned in section `I`, we need further optimizations for the BFS solution to work efficiently. This turns out also to be the case for the DP solution. To see why, recall that in the first case of the DP solution, we don\'t really impose any upper limit on the value of `q` (we do have limit for the value of `m` though: `j = 2^m-1 < i`), while in the third case, we don\'t really have any upper limit for the value of `m`. Apparently we cannot explore every possible values of `m` and `q` (there are infinitely many).\n\nto be updated...\n\n---\n\n`IV -- Solutions`\n\nHere is a list of solutions: one BFS, one top-down DP and one bottom-up DP. \n\nThe BFS runs at `O(target * log(target))` in the worst case, with `O(target * log(target))` space. The reasoning is as follows: in the worst case, all positions in the range `[-target, target]` will be visited and for each position there can be as many as `2 * log(target)` different speeds.\n\nBoth the top-down DP and bottom-up DP run at `O(target * (log(target))^2)` with `O(target)` space. However, the top-down DP may be slightly more efficient as it may skip some of the intermediate cases that must be computed explicitly for the bottom-up DP. Though the nominal time complexity are the same, both DP solutions will be much more efficient in practice compared to the BFS solution, which has to deal with `(position, speed)` pairs and their keys for hashing, etc.\n\n
\n\nBFS solution:\n\n```\npublic int racecar(int target) {\n Deque queue = new LinkedList<>();\n queue.offerLast(new int[] {0, 1}); // starts from position 0 with speed 1\n \n Set visited = new HashSet<>();\n visited.add(0 + " " + 1);\n \n for (int level = 0; !queue.isEmpty(); level++) {\n for(int k = queue.size(); k > 0; k--) {\n int[] cur = queue.pollFirst(); // cur[0] is position; cur[1] is speed\n \n if (cur[0] == target) {\n return level;\n }\n \n int[] nxt = new int[] {cur[0] + cur[1], cur[1] << 1}; // accelerate instruction\n String key = (nxt[0] + " " + nxt[1]);\n \n if (!visited.contains(key) && 0 < nxt[0] && nxt[0] < (target << 1)) {\n queue.offerLast(nxt);\n visited.add(key);\n }\n \n nxt = new int[] {cur[0], cur[1] > 0 ? -1 : 1}; // reverse instruction\n key = (nxt[0] + " " + nxt[1]);\n \n if (!visited.contains(key) && 0 < nxt[0] && nxt[0] < (target << 1)) {\n queue.offerLast(nxt);\n visited.add(key);\n }\n }\n }\n \n return -1;\n}\n```\n\n
\n\nTop-down DP:\n\n```\npublic int racecar(int target) {\n int[] dp = new int[target + 1];\n Arrays.fill(dp, 1, dp.length, -1);\n return racecar(target, dp);\n}\n\nprivate int racecar(int i, int[] dp) {\n if (dp[i] >= 0) {\n return dp[i];\n }\n \n dp[i] = Integer.MAX_VALUE;\n \n int m = 1, j = 1;\n \n for (; j < i; j = (1 << ++m) - 1) {\n for (int q = 0, p = 0; p < j; p = (1 << ++q) - 1) {\n dp[i] = Math.min(dp[i], m + 1 + q + 1 + racecar(i - (j - p), dp));\n }\n }\n \n dp[i] = Math.min(dp[i], m + (i == j ? 0 : 1 + racecar(j - i, dp)));\n \n return dp[i];\n}\n```\n\n
\n\nBottom-up DP:\n\n```\npublic int racecar(int target) {\n int[] dp = new int[target + 1];\n \n for (int i = 1; i <= target; i++) {\n dp[i] = Integer.MAX_VALUE;\n \n int m = 1, j = 1;\n \n for (; j < i; j = (1 << ++m) - 1) {\n for (int q = 0, p = 0; p < j; p = (1 << ++q) - 1) {\n dp[i] = Math.min(dp[i], m + 1 + q + 1 + dp[i - (j - p)]);\n }\n }\n \n dp[i] = Math.min(dp[i], m + (i == j ? 0 : 1 + dp[j - i]));\n }\n \n return dp[target];\n}\n```

Race Car

Problem Description

Problem Description

Answer Panel