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:
- 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.
- 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:
- In Example 0, x = { 5, 0, 0, 0, 0 }.
That means that S will be { [1,5] }.
- In example 1, x = { 4, 2, 1, 0 }. That means that S will be { [1,1], [3,1] }.
- In example 3, x = { 4, 3, 2, 1 }. That means that S will be { [4,1] }.
- Here's one that's not in the examples. Suppose x = { 7, 4, 2, 0, 0, 0, 0 }. Then
there have to be two strings of three consecutive characters, and one of one character.
S will be { [1,1], [3,2] }.
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:
- Create the map S from x, by finding the largest index j of x that is
non-zero, adding an entry for S that corresponds j, and then subtracting from
all of the x values that have indices less than or equal to j.
- From S, you create the password using the high values of S for the
character 'a', and the low values for the character 'b'.