SRM 605, D2, 250-Pointer (AlienAndPassword)

James S. Plank

• Problem Statement.
• A main() with the examples compiled in.
• A skeleton that compiles with main.cpp.

• Problem Given in Topcoder: 2014
• Competitors who opened the problem: 1006
• Competitors who submitted a solution: 968
• Number of correct solutions: 946
• Accuracy (percentage correct vs those who opened): 94.0%
• Average Correct Time: 9 minutes, 4 seconds.

In case Topcoder's servers are down

Here is a summary of the problem:

• You are given a string S.
• Your job will be to delete one character from S to obtain a potential password.
• Return how many potential passwords that you can generate in this way.
• Topcoder constrains S to be between 1 and 50 characters, but I am going to constrain them to be between 1 and 100,000 characters.

The examples

Testing yourself

I have a second shell script called time-tests.sh -- run this to see timings of each group of 20 tests from tests.sh. The input size in of these groups grows by a factor of 10 from the previous group.

Hints

/* find() is a procedure that finds string s in vector v.
   If s is in v, find() returns the index of s.
   Otherwise, it returns -1 */

int find(vector <string> v, string s)
{
  int i;

  for (i = 0; i < v.size(); i++) if (v[i] == s) return i;
  return -1;
}

/* Solve the problem by creating each potential password,
   and then trying to find it in a list of potential
   passwords.  If it's not there, add it to the list, and
   then return the list's size. */

int AlienAndPassword::getNumber(string S)
{
  vector <string> pot;
  string p;
  int i;

  for (i = 0; i < S.size(); i++) {
    p = S.substr(0,i) + S.substr(i+1);
    if (find(pot, p) == -1) pot.push_back(p);
  }
  return pot.size();
}

This solves the problem directly by generating each potential password, and then searching for it in a list of potential passwords. Why is this bad? Let's analyze it, when S has n characters, and all potential passwords are different:

• find() is potentially O(n²), because the loop iterates O(n) times, and the string comparison is O(n). Because you don't use reference variables, It's an additional O(n) to copy v. However, O(n²)+O(n²) is still O(n²).
• In getNumber(), the loop iterates O(n) times. Creating p is O(n) as well, but that's not really important, because as mentioned above, calling find() is O(n²)+O(n²).
• For that reason, this program is O(n³).

You can use a set instead of a vector, and get this down to O(n² log(n)) (which took 12 seconds on tests 81-100).

However, ask yourself some questions to prove when two potential passwords will be the same. Let's take as an example, S = "AABBCA".

• If you delete character S[i] and character S[j], and they are different, will the two potential passwords be the same or different? For example, if you delete an 'A', regardless of which one it is, the resulting password will always be different from when you delete a 'B'.
• If you delete character S[i] and character S[j], and they are the same, but there is a different character between them, will the two potential passwords be the same or different? For example, deleting the first 'A' in "AABBCA" will give you a different password than deleting the last one.
• This means that we can focus on characters that are the same, and there are no different characters between them. In this case, deleting the characters will yield the same password.