SRM 695, D1, 300-Pointer (BearPasswordLexic)

James S. Plank

Mon Sep 5 01:01:35 EDT 2016
It's an awkward problem writeup, but once you understand what the problem is asking, you can start to craft a solution. Here are two things that have to be true about x:
  1. x[0] has to equal x.size(). This is because there have to be exactly N one-character strings, and x.size() is equal to N.
  2. Suppose j is the largest value for which x[j] is greater than zero. Then there has to be a string with j consecutive characters, and there have to be two strings with j-1 consecutive characters, and three strings with j-2 consecutive characters, and so on.
So, here's an idea. Let's create a data structure S, which is a map of two integers. If S[j] = k, then the password will have k substrings of exactly j consecutive characters.

Let's do some examples:

To create S, you need to find the largest value j such that x[j] is non-zero. Then you add one value to S[j], and you subtract one from x[j], two from x[j-1], three from x[j-2] and so on. If you get to a point where some value of x is negative, then you return "".

Keep doing this until every value of x is zero. Then your map S is done.

To create the password from S, you will start with S's largest key, and add that many a's. Then go to the smallest key, and add that many b's. Continue like that. For example, suppose that S is { [1,1], [2,1], [3,1], [4,1] }. Then the password will be "aaaabaaabb".

If S is { [1,1], [3,2] }, then the password will be "aaabaaa".

To reiterate, your steps here are:

My Solution