- Problem Statement.
- A
**main()**with the examples compiled in. - A skeleton that compiles with
**main.cpp**. -
**Problem Given in Topcoder**: March 2014 -
**Competitors who opened the problem**: 451 -
**Competitors who submitted a solution**: 419 -
**Accuracy (percentage correct vs those who opened)**: 65.91% -
**Average Correct Time**: 22 minutes, 18 seconds.

That is the case in this problem, and like many BFS/Dijkstra problems, your best approach is not to build the graph ahead of time, but instead build it incrementally, while you are doing the BFS. What you'll do is create the starting node and push it onto your BFS queue. Then you process the queue, creating new nodes on-the-fly, stopping when you reach a target node.

A second challenge with this problem is figuring out what the nodes are. At a first glance, you might try to have a node for each number of emoticons. However, the clipboard is important too, so you need a way to store that in the nodes as well.

What I suggest is to label each node with *(e,c)*, where *e* is
the number of emoticons that have been typed/pasted,
and *c* is the number of emoticons in the clipboard.
You'll start with node *(1,0)*. Then, when you process the BFSQ, and you
are processing node *(e,c)*, you will have edges to:

- A node where you copy the emoticons into the clipboard:
*(e,e).* - A node where you paste the clipboard:
*(e+c,c)* - A node where you delete an emoticon:
*(e-1,c)*

When you process a node where *e* equals `smiles`, then you're done.

As always, an example will help. As it turns out, the graph that we build is always
the same. It's just where we stop that's different. So, when we start, here's
our graph and BFSQ. I'm keeping track of the shortest path to each node in the
`SP` variable:

We process the node, and that will create a new node by copying the emoticon to the clipboard. As it turns out, you can't delete the emoticon, because that will make zero emoticons, and if you paste the clipboard, you end up going back to the starting node. Here's the graph:

We process (1,1) now, as it is on the head of the BFSQ, and that will create a new node (2,1). As before, we can't delete the emoticon, and now if we copy the emoticons to the clipboard, we simply go back to (1,1):

We process (2,1) and that will create two new nodes: (3,1) by pasting, and (2,2) by copying. If you delete, you'll go back to node (1,1). Here's the graph. The BFSQ could have (3,1) or (2,2) first -- it just depends on which order you create them.

I'm showing one more step -- processing (2,2). That creates two more new nodes: (1,2) by deleting and (4,2) by pasting. Here's the graph and BFSQ:

I'm going to stop here -- by this point, you should see how we get examples 0 and 1 (and even 2, because (4,2) will have an edge to (6,2)).

It's always good to try this for yourself, but if you get stuck or confused, then take a look at my code below:

/* Topcoder SRM 612 D1 250-Pointer EmoticonsDiv1 James S. Plank Thu Mar 9 21:44:21 EST 2017 */ #include <string> #include <deque> #include <map> #include <iostream> #include <cstdio> #include <cstdlib> using namespace std; class EmoticonsDiv1 { public: int printSmiles(int smiles); }; int EmoticonsDiv1::printSmiles(int smiles) { deque <string> BFSQ; map <string, int> Shortest_Paths; int emoticons; int clipboard; int seconds; char buf[100]; // This is to create "e,c" from e and c using sprintf. string s; /* Put the starting state on the BFSQ. */ Shortest_Paths["1,0"] = 0; BFSQ.push_back("1,0"); while (1) { /* Grab the first node off the BFSQ. Turn the node name into emoticons & clipboard, and then get the number of seconds from the Shorest_Paths map. If the emoticons is our target, then we're done -- return the number of seconds. */ s = BFSQ[0]; BFSQ.erase(BFSQ.begin()); sscanf(s.c_str(), "%d,%d", &emoticons, &clipboard); seconds = Shortest_Paths[s]; if (emoticons == smiles) return seconds; /* Create a new node by copying the emoticons into the clipboard. If this node doesn't exist, create it and put it onto the BFSQ. */ sprintf(buf, "%d,%d", emoticons, emoticons); if (Shortest_Paths.find(buf) == Shortest_Paths.end()) { Shortest_Paths[buf] = seconds+1; BFSQ.push_back(buf); } /* Create a new node by pasting the clipboard. Only do this if the number of emoticons is less than the target. Put this onto the BFSQ if the node doesn't exist yet. */ if (emoticons < smiles) { sprintf(buf, "%d,%d", emoticons+clipboard, clipboard); if (Shortest_Paths.find(buf) == Shortest_Paths.end()) { Shortest_Paths[buf] = seconds+1; BFSQ.push_back(buf); } } /* Finally, create a new node by deleting one emoticon. If the result is a positive number, then put it on the BFSQ. */ if (emoticons > 1) { sprintf(buf, "%d,%d", emoticons-1, clipboard); if (Shortest_Paths.find(buf) == Shortest_Paths.end()) { Shortest_Paths[buf] = seconds+1; BFSQ.push_back(buf); } } } /* We will never get here, but we're keeping the compiler quiet. */ return -1; } |