Ashutosh
BAN USERI thought about a recursive solution with complexity Nx(num of ladders).
Better solutions welcome:
int min_rolls(node * start)
{
int arr[6] = {INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX}
int i = 0;
int j = 0;
for(int i = 1; i <= 6; i++)
{
// if its 50 then return 1;
if(*start+i == 50)
return 1;
// for each ladder climbup & recursive call min_roll
if(is_ladder(start+i) && ladder_top(start+i) < 50)
arr[i-1] = min_rolls(ladder_top(start+i));
else if(is_not_snake(start+i))
// keeping track of last non_ladder non_snake index
j = i;
}
// if all 6 indexes are not snakes & ladders then
// recursively call min_rolls with last non_ladder non_snake index.
if(j != 0)
{
arr[j-1] = min_rolls(start + j);
}
return ( MIN(arr[0-5]) +1 );
}
for(int i = 0; i < N ; i++)
{
for(int j =0; j < M ; j++)
{
if(row[i] > arr[i][j])
row[i] = arr[i][j];
if(col[j] < arr[i][j])
col[j] = arr[i][j];
}
}
for (int k = 0 ; k < N ; k++)
if(row[k] == col[k])
{
// got position
}
2 3 4 5
4 5 6 7
1 2 3 0
9 8 7 6
row[] = 3, 3, 2, 0
col[] = 2, 2, 2, 2
Algorithm:
The idea of the problem is from the famous game: Tetris
Lets see how it works. Consider m = 5;
Given an array : 4 3 3 2 1 2 3 4 4 7, we treat each number as a piece in Tetris,
which falls down from the ceil. Our task is to try to keep the same number stacked on the same column.
Consider the moment that 7 is going to fall down. The snapshot of our game now is like :
7
4
4 3 2
4 3 2 1 _
Note that, the size of a row is designed as M, which is 5 here.
Just like Tetris, this game has a similar rule that:
if a row is full of numbers then it should be eliminated.
So when 7 goes down, it becomes:
4
4 3 2
4 3 2 1 7 //This row is full and to be eliminated
Then the bottom row is gone.
It becomes
4
4 3 2
As the numbers falls down, eventually, the game will end in a status that no row is full.
So we have at most M - 1 numbers left at the final stage.
But it is not over. We can easily prove that, if there is a solution, it must be in the number
left at the final stage; but we can not guarantee all numbers left are the correct solution.
So we need to scan the array again, and count the numbers left to find the correct solutions and report their frequencies.
Implementation:
struct node
{
int val;
int count;
};
Create following var for keeping track
struct node tracker[3];
for each node in input array arr
{
if(tracker[0].val == arr[i])
{
tracker[0].count++;
}
else if(tracker[1].val == arr[i])
{
tracker[1].count++;
}
else if(tracker[2].val != 0)
{
tracker[0].count--;
tracker[1].count--;
tracker[2].count--;
}
if(tracker[0].val == 0)
{
tracker[0].val = arr[i];
tracker[0].count++;
}
else if(tracker[1].val == 0)
{
tracker[1].val = arr[i];
tracker[1].count++;
}
else if(tracker[2].val == 0)
{
tracker[2].val = arr[i];
tracker[2].count++;
}
}// for end
// reset the counters
tracker[0].count = 0;
tracker[1].count = 0;
tracker[2].count = 0;
for each node in input array
{
if(tracker[0].val == arr[i])
tracker[0].count++;
else if(tracker[1].val == arr[i])
tracker[1].count++;
else if(tracker[2].val == arr[i])
tracker[2].count++;
} // for end
Create a BST while iterating over the array from right to left, maintain the values of greater element while inserting (i.e the point from where the left child is added)
- Ashutosh March 21, 2020