SRM 612, D1, 250-Pointer (EmoticonsDiv1)

James S. Plank

Sat Nov 19 11:37:24 EST 2016
As usual, your first temptation -- to derive an answer mathematically -- is bound to leave you frustrated. When you see a problem like this -- where you are performing steps, and you want to minimize the number of steps that you are performing, you should think Breadth-First-Search. Can you turn your problem into a graph? Can you solve your problem by finding the shortest path from one node to another in the graph? If so, then BFS is your answer.

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:

For each edge, you'll check to see if the new node is already on the BFSQ. If it is, then you ignore it. You should also check for illegal nodes -- for example, when e is negative, or e is too big (in my code, I decided that if e was greater than smiles, then I would ignore the edge to (e+c,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)).

My Solution

My solution is in Solution.cpp. I use a string to label the nodes "e,c". I also use a map, keyed on the strings, to hold the shortest paths. I can tell whether a node exists by checking the map for its label. I use sprintf() to create labels, and sscanf() to turn a label into e and c.

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;
}