SRM 486, D1, 300-Pointer (OneRegister)

James S. Plank

Sun Nov 4 10:47:46 EST 2012. Most recent revision: Tue Mar 29 20:54:17 EDT 2022.

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: 2010
Competitors who opened the problem: 718
Competitors who submitted a solution: 665
Number of correct solutions: 350
Accuracy (percentage correct vs those who opened): 48.7%
Average Correct Time: 26 minutes, 28 seconds.

In case topcoder's servers are down

Here is a description of the problem.

You have just bought the worlds cheapest computer. It contains one register, and programs consist of a sequence of instructions.
There are four instructions:
- '+' Adds the register to itself.
- '-' Subtracts the register from itself.
- '*' Multiplies the register with itself.
- '/' Divides the register by itself.
You are given two numbers, s and t. Each is between 1 and 1,000,000,000.
Your job is to return the smallest program that, when it starts with s in the register, ends up with t in the register. Return it as a string.
If there are two programs with the size, then prefer the lexicographically smallest of these, where '*' comes before '+', which comes before '-', which comes before '/'.
If there is no program that will work, then return the string ":-(".

The examples

#       s       t  answer
# ------- ------- ------------------
0       7     392  "+*+" -- 7+7 = 14; 14*14 = 196; 196+196 = 392.
1       7     256  "/+***"
2       4     256  "**"
3       7       7  ""
4       7       9  ":-("
5      10       1  "/"

Standard tests.sh and answers.txt (read the Cryptography problem if you need instruction).

Hints

Your first temptation with a problem like this one is try to be smart. Yes, you can represent each reachable number with an equation, but it's not helpful, so don't even go there. What you should be thinking is the following:

You can view the value of the register at each point in time to be a node on a graph.
One node is s, and the other node is t.
Each "instruction" is an edge, from the value of the register before the instruction to the value of the instruction after the register.
A "program" is a path on the graph from s to t.
Therefore, the "smallest" program will be the shortest path from s to t, where every edge has a weight of one.
So this is a BFS.

Problems like this have a pattern for your solution: Push the first node onto your queue, and then when you pop a node from the queue and process its adjacency list, you look to see if each adjacent node exists. If it does, ignore it (because it's already on the queue), and if it doesn't, create it, set its distance and back-link, and push it onto the queue.

You'll either find the shortest path to t this way, or if you do it right, you'll run out of nodes on the queue and determine that there's no path.

What does it mean to "do it right"?

It means that you shouldn't create nodes if you know they are useless. For example, it makes no sense to create nodes that are bigger than s and t. Why? Because the '+' and '*' operations only make them bigger, and the '-' and '/' operations go to the nodes 0 and 1 respectively. When you process s, you'll create the nodes 0 and 1, so you'll never need to create them again. So there's no point in having nodes that are greater than s and t.

You also need to process the adjacency lists in the correct order. That means '*' before '+' before '-' before '/'.

Finally, you need to decide what data structures you want -- what information you want to keep and what information you want to ignore. Let me tell you my data structures:

A vector called Q to hold my queue. Q[i] is the value of the node on the queue. Obviously, Q[0] will equal s. I'll call push_back() to push nodes onto the queue, and I won't bother popping. I'll keep track of the "front" of my queue with an integer, f, which starts at 0. Instead of doing pop_front(), I'll simply increment the f.
A vector called BL to hold back-links. BL[i] holds the index of the back-link for Q[i].
A string called I to hold the instructions. I[i] holds the instruction that created node Q[i]. I'll start by making I[0] equal to 'S', to signify that no instruction created s.
A set called N that contains all of the nodes on Q. I can use this to determine whether I've created a node already.

I'm not ready to write my BFS. Let's go through some examples to help:

Example 3

In this example, s = t = 7. Although it's trivial, let's go through what our data structures look like. When we start, we push 7 onto Q. We'll push -1 onto BL and 'S' onto I. And we'll add 7 to N. Finally, we set f to 0. We have the following:

f  Q             BL             I             N              Action
0  7             -1            "S"            { 7 }          Start

We "pop" 7 off the Q by looking at Q[f] and incrementing f. Since Q[0] equals t, we're done. We look at the node's back link, and see that it's -1, so there's no path. We'll return "".

Example 4

In this example, s = 7 and t = 9. Since s is the same as in the last example, we can start with the data structures in the same state:

f  Q             BL             I             N   
0  7             -1            "S"            { 7 }

However, now, when we "pop" 7, we need to process its adjaceny list.

The first edge, '*', would be to node 49. Since that node is greater than s and t, we can ignore it.
The next edge, '+', would be to node 14. Similarly, we ignore that.
The next edge, '-', is to node 0. We can create that and push it onto the queue.
The last edge, '/', is to node 1. We can create that and push it onto the queue.

When we're done, here's the state of our data structures:

f  Q             BL             I             N          
1  7,0,1         -1,0,0        "S-/"          { 0, 1, 7 }

We now look at node 0, which is Q[1]. The first three edges on its adjacency list ('*', '+' and '-') are all to node 0, and the last edge '/' is undefined. So we do nothing and move onto the next node on Q by incrementing f. Here's our state:

f  Q             BL             I             N          
2  7,0,1         -1,0,0        "S-/"          { 0, 1, 7 }

We now look at node 1, which is Q[2]. The first edge on its adjacency list, '*', is to node 1, so we can ignore it. Similarly, I assume that you can see that we can ignore '-' and '/' henceforth, so I'm going to stop mentioning them. The '+' edge goes to node 2, so we add it to Q and update the rest of the data structures. Here's our state:

f  Q             BL             I             N          
3  7,0,1,2       -1,0,0,2      "S-/+"         { 0, 1, 2, 7 }

We look at Q[3], which is node 2. The only edge here will be '*', because we process it before '+', and they both go to the same node: 4. We add it to our data structures:

f  Q             BL             I             N          
4  7,0,1,2,4     -1,0,0,2,3    "S-/+*"        { 0, 1, 2, 4, 7 }

Now We look at Q[4], which is node 4. Its '*' edge is to a node that's too big, so we only consider the '+' edge to 8:

f  Q             BL             I             N          
5  7,0,1,2,4,8   -1,0,0,2,3,4  "S-/+*+"        { 0, 1, 2, 4, 7, 8 }

Finally, we process Q[4], which is node 8. Both the '*' and '+' edges are too big, so we can't add anything to the queue. Here's our state:

f  Q             BL             I             N          
6  7,0,1,2,4,8   -1,0,0,2,3,4  "S-/+*+"        { 0, 1, 2, 4, 7, 8 }

Since f equals Q.size(), we're done, and we haven't found t. We can return -1.

Here's our final graph, that we constructed on the fly:

Example 0

Now s equals 7 again, and t equals 392. Because t is bigger, we can create more nodes. Here is how we create and process the graph:

                                        BL                         I                          
f  Q                                    0 1 2 3 4 5 6 7 8 9 a b    0123456789ab   N          
0  7                                   -1                         "S"             { 7 }        
1  7,49,14,0,1                         -1,0,0,0,0                 "S*+-/"         { 0, 1, 7, 14, 49} 
2  7,49,14,0,1,98                      -1,0,0,0,0,1               "S*+-/+"        { 0, 1, 7, 14, 49, 98} 
3  7,49,14,0,1,98,196,28               -1,0,0,0,0,1,2,2           "S*+-/+*+"      { 0, 1, 7, 14, 28, 49, 98, 192} 
4  7,49,14,0,1,98,196,28               -1,0,0,0,0,1,2,2           "S*+-/+*+"      { 0, 1, 7, 14, 28, 49, 98, 192} 
5  7,49,14,0,1,98,196,28,2             -1,0,0,0,0,1,2,2,4         "S*+-/+*++"     { 0, 1, 2, 7, 14, 28, 49, 98, 192} 
6  7,49,14,0,1,98,196,28,2             -1,0,0,0,0,1,2,2,4         "S*+-/+*++"     { 0, 1, 2, 7, 14, 28, 49, 98, 192} 
7  7,49,14,0,1,98,196,28,2,392         -1,0,0,0,0,1,2,2,4,6       "S*+-/+*+++"    { 0, 1, 2, 7, 14, 28, 49, 98, 192, 392} 
8  7,49,14,0,1,98,196,28,2,392,56,4    -1,0,0,0,0,1,2,2,4,6,7     "S*+-/+*++++"   { 0, 1, 2, 7, 14, 28, 49, 56, 98, 192, 392} 
9  7,49,14,0,1,98,196,28,2,392,56,4    -1,0,0,0,0,1,2,2,4,6,7,8   "S*+-/+*++++*"  { 0, 1, 2, 7, 14, 28, 49, 56, 98, 192, 392} 
DONE!

We're done, so we can use BL to figure out the path from Q[9] back to Q[0]. It is Q[9] - Q[6] - Q[2] - Q[0]. Using those indices, we can build the path using I[2]+ I[6]+ I[9] = "+*+", which is the right answer. Here's the graph that we constructed:

Hopefully, that gives you enough detail and information to implement this!