Member Count: 599,037 - December 10, 2013  [Get Time]
 SRM 467
Added by mystic_tc , last edited by mystic_tc on Jul 02, 2011  (view change)
Labels:
(None)

Single Round Match 467
Thursday, April 15th, 2010

Match summary

The match consisted of problems that required either implementation work, thinking out a good solution or both. In division 1, the coders faced a tricky 250 points problem with low submission and accuracy rates. The 500 points problem was the total opposite - although its solution was not hard to code, it required some familiarity with math concepts or the ability to recognize patterns. The match winners were decided by the 1000 points problem, a solution to which only five coders were able to submit during the coding phase. The system tests revealed that only three of them were 100% correct. Giving rng_58, RAVEman and bwps the top three places and the admiration of the other coders.

In division 2, the coders also had to face the same complicated problem with the addition of a 1000 pointer that concealed a relatively simple solution inside what appeared to be a complicated simulation problem. Only one coder was able to solve all three problems correctly: evgenii, followed by Katran in a close second place and newcomer adhirajsomani in third.

The Problems

ShorterSuperSum
Used as: Division Two - Level One:
 Value 250 Submission Rate 609 / 679 (89.69%) Success Rate 579 / 609 (95.07%) High Score luch1t0 for 249.94 points (0 mins 27 secs) Average Score 217.06 (for 579 correct submissions)

It is important to note that the constraints of this problem specified that k and n will be <= 14. Seeing that constraints are so low, it might appear that simply implementing the recursion would run in enough time. It is of course not easy to prove it. In fact, with some analysis you can see that the time complexity of implementing the recursion is actually about O( SuperSum(k-1,n) ). (Assume that when k=1 you need n function calls, then try getting the number of function calls requred for k=2, and so and so.) So the easiest way to verify that the simple recursive algorithm will run in time is by implementing it and then testing for k=14 and n=14.

If unsure about the running time of the algorithm, there is always room for optimization, by adding memoization to the recursion, you can achieve an O(n2*k) time algorithm. Even more, if you notice that superSum(k, n) = superSum(k, n-1) + superSum(k-1, n) you could reduce this even further to O(n*k). However, in the case of the Dision I 500, you'll need to be more clever ;).

LateProfessor
Used as: Division Two - Level Two:
 Value 500 Submission Rate 237 / 679 (34.90%) Success Rate 35 / 237 (14.77%) High Score bachelorchen for 303.48 points (26 mins 50 secs) Average Score 237.67 (for 35 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 396 / 488 (81.15%) Success Rate 192 / 396 (48.48%) High Score blueblimp for 232.97 points (7 mins 47 secs) Average Score 149.40 (for 192 correct submissions)

This was indeed a very tricky problem. There are two different cases that are solvable differently. The solutions when bestArrival=worstArrival and bestArrival<worstArrival are different. A way to solve this problem would be to recognize that there is a cycle, it begins at time zero and repeats every waitTime + walkTime seconds. There is a hidden variable that I would call lateEnd, this variable is equal to waitTime + walkTime - lateTime, this variable is important because it determines the maximum time during walkTime at which the professor can arrive in such a way that you arrive late.

Boundary cases were the center of the problem and the main source of confusion. I would recommend stopping to really focus on the following paragraph in the statement:

Overall, John stands in front of the class door from time 0 to time waitTime, inclusive, then from time walkTime + waitTime to time walkTime + 2*waitTime, inclusive, and so on. At all other time moments he walks outside.

From this moment, the key to solving the problem lies in understanding the following about corner cases:
• If the professor arrives exactly at time waitTime, the student will be at the class room, he will not be late.
• If the professor arrives exactly at time lateEnd (waitTime+walkTime-lateTime), the student will arrive exactly lateTime seconds after the professor's arrival, thus he will be late.
• If the professor arrives at any other time between waitTime and lateEnd, the student will arrive more than lateTime seconds after the professor's arrival and be late for the class.

The solution for the worstArrival=bestArrival case is then to find the position of bestArrival relative to this cycle. The student will be late if and only if bestArrival is greater than the cycle's waitTime and less time or equal to the cycle's lateEnd. If the student will be late, the probability he will be late is 1.0, and 0.0 otherwise.

The solution for worstArrival>bestArrival is different and is based on probability theory. Once again, you must check all instances inside the cycle waitTime+walkTime cycle, but this time, count all the length 1 intervals inside the [bestArrival:worstArrival[ interval that belong to the late interval (that is, a case in which the interval is greater than a waitTime and less than or equal to a lateEnd.) The result probability is equal to this count / (worstArrival-bestArrival ), note that in this case, the boundary cases are ignored, since the probability that they will occur is ~0%.
```double getProbability(int waitTime, int walkTime, int lateTime, int bestArrival, int worstArrival)
{
int lateEnd = walkTime - lateTime;
int t = waitTime;
if( worstArrival > bestArrival) {
int s = 0;
while( t<worstArrival) {
for (int i=0; i<lateEnd; i++) {
if( t+i >= bestArrival && t+i < worstArrival ) {
s++;
}
}
t = t + walkTime + waitTime; //move to the next instance of the cycle.
}
return s / (double)(worstArrival - bestArrival );

} else {

while( t<=worstArrival) {
for (int i=1; i<=lateEnd; i++) {
if( t+i == bestArrival ) {
return 1.0;
}
}
t = t + walkTime + waitTime; //move to the next instance of the cycle.
}
return 0.0;

}
}```

MazeOnFire
Used as: Division Two - Level Three:
 Value 1000 Submission Rate 41 / 679 (6.04%) Success Rate 5 / 41 (12.20%) High Score Katran for 784.71 points (15 mins 48 secs) Average Score 611.53 (for 5 correct submissions)

There are two aspects of the game that need to be simulated: the spreading of the fire and the movement of the character. In this case, it is convenient to treat them separatedly. It can be noticed that the fire movement does not depend on the character's location, and the fire will eventually reach all the cells to which there is a path no matter what movements the character makes. On the other hand, the movement of the character should depend on the movement of the fire, because the time at which certain cells will get on fire, modify what the optimal path for the character is. By treating the fire and the character separatedly, we can begin simulating the fire and then use that information to give the correct choices to the character.

Hence the first subproblem is to simulate the movement of the fire, this can be done through many means. The easiest would be to copy many copies of the board, one for every turn number in which the cells that have fire during that turn are getting a 'F' added. The maximum number of turns needed might be as large as 50*50/2, about 50*50/2*(50*50) bytes of memory are necessary to store all the turns, which accounts to 2 MB. Such simulation might be complicated to code though and there is a more interesting way to see the problem.

Once a cell is set of fire, it will stay in this state until the end of the game, so all that is needed to know would be each cell's fireTime which would be a value that represents the first turn in which the cell is set of fire. It is also possible to note that a cell's fireTime is equivalent to the minimum distance between the cell and any cell that is on fire at the beginning of the game.

The minimum distance on a grid maze is a problem that can be solved by using a breadth-first search. Assume that each empty cell in the grid is a vertex and that it has an edge connecting it to any of the empty adjacent cells.

Once that each cell's fireTime is known, the character movement subproblem can be solved. Assume that a cell (x,y) is reachable from the character's initial cell (sx,sy) in less than fireTime turns, then it is possible for the character to stay in that cell until the fire reaches the cell. The maximum fireTime value of all of the reachable cells would be the solution to the problem.

In order to know if a cell (x,y) can be reached before its fireTime, we can use another breadth-first search starting from (sx,sy) to find the minimum distance between the origin cell and (x,y). This time, we must not only take into account that the character can move between empty cells, it is also necessary to stop the character from moving into cells that would be on fire by the time of the turn. It is also necessary to stop the character if it reaches a cell at exactly its fireTime value.

The execution time of both breadth-first searches is equal to O(number of vertices + number of edges) which in this case is O(width*height).

```final int INF  = 10000; //A large value.
final int[] dx = new int[]{0,0,1,-1};
final int[] dy = new int[]{1,-1,0,0};

public int maximumTurns(String[] maze) {
int w = maze.length, h = maze[0].length(), sx=0,sy=0;
int [][] fireTime = new int[w][h];
int [][] arrivalTime = new int[w][h];

//The first BFS, fill fireTime, the array that specifies the
//turn number at which the cell gets set on fire. Find 'F'
// cells and push them to the queue so that they become
// starting points. Also find the initial character's cell (x,y).
//
// A single queue is used to store both coordinates, first
// x is pushed to the queue, then y.
//
for (int i=0; i<w; i++) {
for (int j=0; j<h; j++) {
arrivalTime[i][j] = INF;
if(maze[i].charAt(j) == 'F' ) {
fireTime[i][j] = 0;
Q.offer(i);
Q.offer(j);
} else {
if(maze[i].charAt(j) == '\$') {
arrivalTime[i][j] = 0;
sx = i;
sy = j;
}
fireTime[i][j] = INF;
}
}
}

while( Q.peek() != null ) {
int x = Q.remove();
int y = Q.remove();
for (int t=0; t<4; t++) {
int nx=x+dx[t], ny=y+dy[t];
if( (nx>=0) && (nx<w) && (ny>=0) && (ny<h)
&& (maze[nx].charAt(ny) != '#')
&& (fireTime[nx][ny] > fireTime[x][y]+1)
) {
Q.offer(nx);
Q.offer(ny);
fireTime[nx][ny]=fireTime[x][y]+1;
}
}
}
//If the fire can never reach the starting point (sx,sy), then
//the character can stay in there indifinitely.
if( fireTime[sx][sy] >= INF ) {
return -1;
}

// The second BFS, moves the character around the map.
// Make sure the character does not goes through cells that would
// be on fire during the turn number. The character must also
// stop moving if the cell in which it is located becomes on fire
// exactly at that turn. It fills the arrivalTime array which
// is the minimum distance between (sx,sy) and the cell.
int best = 0;
Q.offer(sx);
Q.offer(sy);
while ( Q.peek() != null ) {
int x = Q.remove();
int y = Q.remove();

if( arrivalTime[x][y] <= fireTime[x][y] ) {
// the result is the maximum of the fireTime values of
// all the cells that can be reached before they are set on fire.
best = Math.max(best, fireTime[x][y] );
}
if( arrivalTime[x][y] < fireTime[x][y] ) {
// can move to another cell:
for (int t=0; t<4; t++) {
int nx=x+dx[t], ny=y+dy[t];
if( (nx>=0) && (nx<w) && (ny>=0) && (ny<h)
&& (maze[nx].charAt(ny) != '#')
&& (arrivalTime[nx][ny] > arrivalTime[x][y]+1)
) {
Q.offer(nx);
Q.offer(ny);
arrivalTime[nx][ny]=arrivalTime[x][y]+1;
}
}
}

}
return best;
}```

Another approach follows:
Simulation step by step, using an auxiliary maze, to mark the positions that are reachable by the character and by the fire.

```int dx[4] = {-1, 0, 1, 0};
int dy[4] = { 0, 1, 0,-1};
bool valid(int i, int j , int n, int m) {
return i >= 0 && i < n && j >= 0 && j < m;
}
class MazeOnFire {
public:
int maximumTurns(vector <string> maze) {
int h, w, res, nx, ny;
bool solved, fire;
vector<string> next;
res = 0;
h = maze.size();
w = maze[0].size();
next = maze;
solved = false;
while(!solved) {
//this turn is counted because the character is alive.
++res;
//the positions reachable by the character in next turn are marked here.
for(int y = 0; y < h; ++y) {
for(int x = 0; x < w; ++x) {
if(maze[y][x] == '\$') {
for(int i = 0; i < 4; ++i) {
nx = x + dx[i];
ny = y + dy[i];
if(valid(ny,nx,h,w) && maze[ny][nx] == '.') {
next[ny][nx] = '\$';
}
}
}
}
}
//the positions reachable by the fire are marked here
fire = false;
for(int y = 0; y < h; ++y) {
for(int x = 0; x < w; ++x) {
if(maze[y][x] == 'F') {
for(int i = 0; i < 4; ++i) {
nx = x + dx[i];
ny = y + dy[i];
if(valid(ny,nx,h,w) && maze[ny][nx] != '#' && maze[ny][nx] != 'F') {
next[ny][nx] = 'F';
fire = true;
}
}
}
}
}
//if the fire didn't reach any new cell of the grid
//the character will survive indefinitely
if(fire == false)
return -1;
maze = next;
//the flag solved is used to check if the character has survived this turn
//if not the main loop ends
solved = true;
for(int y = 0; y < h && solved; ++y) {
for(int x = 0; x < w && solved; ++x) {
if(maze[y][x] == '\$') {
solved = false;
}
}
}
}
return res;
}
};```

So at the beginning (second paragraph) it says that the maximum number of turns might be as large as 50*50/2. I interpreted that has it being the maximum and using my own method, I failed in the system tests because one of the tests expected a return value of 1433! So instead of giving an example of how big the number of turns can be, give the actual maximum possible number.

My method:

I did a simulation as described in the second paragraph but then to reduce the memory used, I only kept two copies of the table. The table after t turns, and after t-1 turns. The main observation used being, a cell can only be reached in t turns if one of the adjacent cells (or the cell itself) could be reached in t-1 turns

```public class MazeOnFire{
public int maximumTurns(String[] Maze){
int[] dx = new int[]{0,-1,0,1,0};
int[] dy = new int[]{0,0,-1,0,1};

int r=Maze.length, c=Maze[0].length();
boolean[][][] reachable = new boolean[2][r][c];
boolean[][][] fire = new boolean[2][r][c];
char[][] m = new char[r][0];
for(int i=0; i<r; i++) m[i] = Maze[i].toCharArray();

for(int i=0; i<r; i++)
for(int j=0; j<c; j++)
if(m[i][j]=='\$') reachable[0][i][j]=true;
else if(m[i][j]=='F') for(int t=0; t<2; t++) fire[t][i][j]=true;

//At first I'd used t<1275 but that proved to be wrong, so I used t<2500.
//Note: 2500 is a safe bet but not the optimum.
for(int t=1; t<2500; t++){
int num = 0;
for(int i=0; i<r; i++)
for(int j=0; j<c; j++)
if(reachable[(t-1)%2][i][j])
for(int a=0; a<5; a++)
try{
int nx = i+dx[a], ny = j+dy[a];
if(!fire[(t-1)%2][nx][dy] && isfree(m[nx][dy])){
reachable[t%2][nx][dy] = true;
num++;
}
}catch(Exception e){};
//If no cell was reachable in t moves
//then the game ended in t-1 moves.
if(num==0) return (t-1);
for(int i=0; i<r; i++)
for(int j=0; j<c; j++)
if(fire[(t-1)%2][i][j])
for(int a=0; a<5; a++)
try{
int nx = i+dx[a], ny = j+dy[a];
if(isfree(m[nx][dy])){
fire[t%2][nx][dy] = true;
reachable[t%2][nx][dy] = false;
}
}catch(Exception e){};

}
//After 2500 turns and there're still cells that are reachable
//we can safely assume it will never end.
return -1;
}
boolean isfree(char c){
return (c=='.')||(c=='\$');
}

}```
SuperSum
Used as: Division One - Level Two:
 Value 500 Submission Rate 198 / 488 (40.57%) Success Rate 171 / 198 (86.36%) High Score zhouerjin for 488.37 points (4 mins 24 secs) Average Score 334.32 (for 171 correct submissions)

Most coders managed to solve this problem by noticing that SuperSum(n,k) is equal to the binomial coeficient C(n+k, k+1). There are multiple ways to deduce this relationship. A simple way is to note that SuperSum(k,n) = SuperSum(k-1,n) + SuperSum(k,n-1) which is similar to the method to generate Pascal's triangle, starting from this knowledge, it may be useful to generate a table of the values for each k and n:

In case it is still not clear, note that we can actually use SuperSum(-1, n) = 1 as a base case instead of SuperSum(0, n) = n, without modifying the behavior of the function ( SuperSum(0,n) = SuperSum(-1,1) + SuperSum(-1,2) + ... SuperSum(-1,n) = 1 + 1 + ... 1 (n times) = n ).

After adding this new row, it can become clear that the anti-diagonals of this table actually form the rows of Pascal's triangle. Therefore, we can conclude that SuperSum(n,k) = C(n+k, k+1).

The problem then requires to calculate C(n+k, k+1) mod 10000007. The binomial can be calculated with k+1 multiplications and k+1 divisions. (Because C(n,k) = n! / (k! * (n-k)!) ) = n*(n-1)*...*(n-k+1) / k! ). Execution time is therefore not a problem. The extra complication is to perform the modular division. In this case it is best to calculate the numerator and denominator module 1000000007 separatedly and then calculate the modular multiplicative inverse of the denominator, then multiply the inverse to the numerator to get the final result. In this case, a simple way to get the multiplicative inverse is to notice that 1000000007 is prime, therefore Fermat's little theorem may be used to compute it.

```// Use 64 bits integers to avoid overflow errors during multiplication.
long modPow(long a, long x, long p) {
//calculates a^x mod p in logarithmic time.
long res = 1;
while(x > 0) {
if( x % 2 != 0) {
res = (res * a) % p;
}
a = (a * a) % p;
x /= 2;
}
return res;
}

long modInverse(long a, long p) {
//calculates the modular multiplicative of a mod m.
//(assuming p is prime).
return modPow(a, p-2, p);
}
long modBinomial(long n, long k, long p) {
// calculates C(n,k) mod p (assuming p is prime).

long numerator = 1; // n * (n-1) * ... * (n-k+1)
for (int i=0; i<k; i++) {
numerator = (numerator * (n-i) ) % p;
}

long denominator = 1; // k!
for (int i=1; i<=k; i++) {
denominator = (denominator * i) % p;
}

// numerator / denominator mod p.
return ( numerator* modInverse(denominator,p) ) % p;
}

public int calculate(int k, int n) {
return (int)( modBinomial(n+k,k+1, 1000000007) );
}```

NextHomogeneousStrings
Used as: Division One - Level Three:
 Value 1000 Submission Rate 5 / 488 (1.02%) Success Rate 3 / 5 (60.00%) High Score RAVEman for 524.02 points (34 mins 34 secs) Average Score 468.28 (for 3 correct submissions)

Usually when there is a request for a K-th lexicographically first string then the problem can be converted into a counting problem. More details: Assume that we have a function that can count the number of valid strings of a length that begin with a certain prefix. Then this function can be used to get the K-th string. For example, for the first character in the string, we must decide whether it is right to use 'a', 'b', ... or 'z'. If K was 50, and there were exactly 26 strings that begin with "a", then we can assume that the K-th string does not begin with 'a'. There are 26 strings that begin with "b" which added to the previous 26 that begin with 'a' it means that there are 52 strings that begin with a or b. Then we can assume that the 50-th string begins with 'b'. After this we need to find the 24-th (50 - 26) string that begins with "b". We may proceed and count the number of strings that begin with "ba", "bb", "bc", ... "bz" and get the 24-th of them.

```String getKth(int n, long k) {
// Get the k-th valid string of length n.
// Requires a function countWithPrefix(String) that counts
// the number of valid strings that begin with a prefix.
//
String s = "";
for (int i=0; i<len; i++) {
char ch = 'a';
while(ch <= 'z' ) {
String prefix = s + ch;
long x  = countWithPrefix(prefix);
// if the count is <= k, then we need to subtract it from
// k so that we worry only about the (k-x)-th string that comes
// after the current prefix.
if( x <= k) {
k -= x;
} else {
// if the count is > k, then ch must be the character to
// pick for this index.
break;
}
ch ++;
}
if( ch > 'z') {
return ""; //The total number of strings is <= k
}
s = s + ch;
}
return s;
}```
From this point, we need to solve the subproblem of counting the number of valid strings that begin with a certain prefix. This is a problem that can be divided into sub-cases (The number of strings that begin with "aaa" depends on the number of strings that begin with "aaaa", "aaab", ... , "aaaz" ). More so, you should notice that only the last n letters of a prefix matter (when n=4, the number of strings of size 10 that begin with "xaaaa" is the same as the number of strings of size 10 that begin with "yaaaa"). These are the rules that suggest a dynamic programming / memo-ization solution. Actually, only the last n-1 letters of the prefix are important, even if the state of the dynamic programming only considered the last n-1 characters, you can still treat the substrings of n characters at the time you decide whether a transition from a prefix to another is valid.

Even considering the last n-1 characters of a prefix, with 26 different symbols there are still O( 26n-1 * length_of_seed ) states, so further optimizations are needed. Note that letters are NOT indistinguishable from each other, since only strings that are lexicographically greater than or equal to seed are valid. This can be approached: Note that once the prefix is known to be strictly greater to the first substring of length(prefix) of seed, the characters become indistinguishable from each other. Then we can recognize three cases:

• Case 1: The prefix is lexicographically earlier than seed. Then no valid string that begins with this prefix exists, the result is 0.
• Case 2: The prefix is lexicographically greater than seed. Then the characters in the prefix are indistinguishable from each other.
• Case 3: The prefix is equal to the first substring of seed of the same length as the prefix. Then the characters are not indistinguishable from each other.

There are only (length of seed+1) different possibilities for case 3. (For seed="abcd" the possibilities are "", "a", "ab", "abc" and "abcd") which can be described by a single variable p, the length of the prefix.

As for case 2, since the characters are indistinguishible from each other, then prefixes such as "abbc", "xzzy" and "cttx" are all equal. We can enforce an encoding rule in which all of these cases can be represented by the same code. I recommend the following: Use 0 to represent the first character in the prefix, 1 to represent the second character and so and so. For example, the strings "abbc" and "xzzy" can be represented by (0 1 1 2) and the strings "abccba" and "xzyyzx" as (0 1 2 2 1 0). The total number of sequences of length 8 that follow that rule is relatively small, you can code a small dynamic programming program to calculate this number, which is 4140.

Those are the general ideas behind a solution, but there are still many details to clarify. Encoded numbers (0 1 2 2) need to get generated from prefixes. In this case I use a single function that will convert a prefix and convert it to the encoded version of the last n-1 (if existant) characters. It may happen that in a stage of the algorithm we call this function on a prefix that is not valid (one of its length n substring has more than d different letters), so it is useful to make this function able to return -1 in that case. Memo-ization or dynamic programming is also needed to compute both the second and third cases, since there is overlapping of cases. The memo-ization of second case will require to use the encoded prefixes (ie (0 0 1 2 2) ) as keys, so a HashMap (Java) or std::map (c++) can be used. Since maps require to store the keys, it might be useful to encode the prefixes not as arrays (many 4-byte words) but as single integers (4 bytes), for this matter the following solution will encode the prefix (0 0 1 2 2) as the decimal integer 22100 (since n is at most 8 this optimization is possible). The computation of case 2, requires to move from an encoded prefix (ie: 0 0 1 2 2) to other prefixes as long as such transition can be done without having more than d different characters in the current block of n characters. There is also an extra complication and it is that the number of strings that begin with a prefix can be very large, it is necessary to note that due to how the getKth method works, we only need to return 10^18+1 ( maximum K+1) in case we the result is greater than or equal to it.

Overall, beyond the dynamic programming problem that required all the previous paragraphs for an explanation, there is still a more complicated, implementation problem that requires to convert the previous ideas into working code. That is probably the reason so few coders were able to solve it during the match and even high rated coders had issues with getting a correct solution. The final result can be something like the following Java solution:

```public class NextHomogeneousStrings
{
final int TOTAL_CHARS = 26;
long INF = 1000000000000000001L;
int    n,d;
long[]   pow10;
long[]   mem2;
int      len;
String   seed;
ArrayList< HashMap<Long, Long> > mem;

// Counts the number of strings that begin with
// a given prefix , assuming that letters are indistinguishable
// from each other.
long countGreater(int p, long prefix) {
if(p==len) {
return 1;
}
//memoization from hash table:
if( mem.get(p).containsKey(prefix) ) {
return mem.get(p).get(prefix);
}
long res = 0;
int  mx = -1;
int t = Math.min(n-1,p);
for (int i=t-1 ; i>=0; i--) {
mx = Math.max(mx, (int)( (prefix/pow10[i])%10 ) );
}
long c = 0;
long tm = 0;
long[] buff = new long[10];
Arrays.fill(buff, -1);
for (int i= ( (t<n-1) ? 0 : 1) ; i<t; i++) {
int x = (int)( (prefix/pow10[i])%10 );
if( buff[x] == -1) {
buff[x] = c++;
}
if( t >= n-1 ) {
tm += buff[x]*pow10[i-1];
} else {
tm += buff[x]*pow10[i];
}

}
t = Math.min(n-1,p+1);
for (int j=Math.min(mx+1, d-1); j>=0; j--) {
long newprefix = 0;
if( t!=0 ) {
if ( buff[j] == -1 ) {
newprefix = tm + c * pow10[t-1];
} else {
newprefix = tm + buff[j] * pow10[t-1];
}
}
long fc = 1;
if( j==mx+1) { // a new one:
fc = ( TOTAL_CHARS - (mx+1) );
} else { //a known one:
fc = 1;
}
long x = countGreater(p+1, newprefix);
if ( x > INF/fc ) {
x = INF;
} else {
x = x*fc;
}
//Avoid returning a result larger than INF:
if ( x + res > INF ) {
res = INF;
} else {
res += x;
}

}
//save in hash table:
mem.get(p).put(prefix,res);
return res;
}
// Encodes a prefix for the last n-1 characters of a string, returns -1 if
// the string is not homogeneus.
// i.e: when n=4 reads "xaxaxxa",
// converts to "100" (in decimal, which describes (0 0 1) ).
long encodePrefix(String s) {
long[] buf = new long[26];
Arrays.fill(buf,-1);
long m = 0;
int c=0, j=0;
for (int i=Math.max(0,s.length()-(n-1) ); i<s.length(); i++) {
int x = (int)(s.charAt(i)-'a');
if( buf[x] == -1 ) {
buf[x] = c++;
}
m = m + pow10[j++]*buf[x];
}
if( (s.length() >= n) &&  (buf[ s.charAt(s.length()-n)-'a'  ] == -1 ) ) {
c ++;
}
if( c > d) {
return -1;
}
return m;
}

// Count the number of strings that begin with a given
// prefix that is equal to the first p characters of seed:
long countWithEqualPrefix(int p) {
if(p==len) {
//how many strings equal to seed are valid?
// 1 if and only if seed is a valid string.
return (encodePrefix(seed) != -1) ? 1 : 0;
}
if( mem2[p] != -1) {
return mem2[p];
}
long res = 0;
String s = seed.substring(0,p);
for (char ch=seed.charAt(p); ch<='z';ch++) {
String ns = s + ch;
// Verify that the current prefix is valid:
if( encodePrefix(ns) == -1) {
continue;
}
long x = countWithPrefix(ns);
if ( res > INF-x ) {
res = INF;
} else {
res += x;
}
}
return (mem2[p]=res);
}

// Count the number of valid strings that begin with a given
// prefix:
long countWithPrefix(String pref)
{
boolean greater = false;
long ms = encodePrefix(pref);
if( ms == -1) {
return 0;
}
for (int i=0; i<pref.length(); i++) {
if( ! greater ) {
if(seed.charAt(i) > pref.charAt(i) ) {
//Case 1, the prefix is lexicographically earlier, no
// valid strings begin with it.
return 0;
} else if ( seed.charAt(i) < pref.charAt(i) ) {
greater = true;
}
}
}
if( greater ) {
//case 2
return countGreater(pref.length() , ms);
} else {
//case 3
return countWithEqualPrefix(pref.length() );
}

}

String getKth(int n, long k) {
// Get the k-th valid string of length n.
// Requires a function countWithPrefix(String) that counts
// the number of valid strings that begin with a prefix.
//
String s = "";
for (int i=0; i<len; i++) {
char ch = 'a';
while(ch <= 'z' ) {
String prefix = s + ch;
long x  = countWithPrefix(prefix);
// if the count is <= k, then we need to subtract it from
// k so that we worry only about the (k-x)-th string that comes
// after the current prefix.
if( x <= k) {
k -= x;
} else {
// if the count is > k, then ch must be the character to
// pick for this index.
break;
}
ch ++;
}
if( ch > 'z') {
return ""; //The total number of strings is <= k
}
s = s + ch;
}
return s;
}

public String getNext(int d, int n, String seed, long k)
{
//initialize many variables that are needed by the other methods.

//An array of powers of ten to encode/decode prefixes easily.
pow10 = new long[18];
pow10[0] = 1;
for (int i=1; i< pow10.length; i++) {
pow10[i] = pow10[i-1]*10;
}
//copy the arguments to member variables.
this.d = d;
this.n = n;
this.seed = seed;

len = seed.length();
//initialize the memoization arrays/hash tables.
mem = new ArrayList<HashMap<Long, Long> >(len);
for (int i=0; i<len; i++) {
mem.add(i, new HashMap<Long, Long> () );
}
mem2 = new long[50];
Arrays.fill(mem2,-1);
return getKth(n,k);
}
}```

By vexorian

TopCoder Member

 Home  |   About TopCoder  |   Press Room  |   Contact Us  |   Privacy  |   Terms Developer Center  |   Corporate Services Copyright TopCoder, Inc. 2001-