AlexandrYegorov
BAN USERCode
#include <iostream>
#include <vector>
bool CheckPathFromPoint(const std::vector<std::vector<int>>& data, size_t y, size_t x, int prevVal)
{
if(y == 0 && x == 0)
return data[0][0] != prevVal;
if(y < 0 || x < 0)
return false;
if(data[y][x] == prevVal)
return false;
auto res = CheckPathFromPoint(data, y-1, x, data[y][x]);
if(res)
return res;
return CheckPathFromPoint(data, y, x-1, data[y][x]);
}
bool CheckPath(const std::vector<std::vector<int>>& data)
{
auto res = false;
if(data.size() > 2 && data[0].size() > 1)
res = CheckPathFromPoint(data, data.size()-2, data[0].size()-1, data[data.size()-1][data[0].size()-1]);
if(res)
return res;
if(data.size() > 1 && data[0].size() > 2)
return CheckPathFromPoint(data, data.size()-1, data[0].size()-2, data[data.size()-1][data[0].size()-1]);
}
The solution is not optimized - its complexity is O(2 in power of N+M) where N and M are the matrix's dimensions. To optimize it the dynamic programming approach should be used - it gives O(N+M) complexity;
The path length is always N+M, if N+M is even the number of 1s and 0s is equal.
Well, it seems there is no right and easy solution so far.
- AlexandrYegorov May 06, 2019I do believe it is possible to think of a nice and easy solution.
How many strings of 'a's and 'b's we can make? It is 2^(N) where N is the length of the string and 2 is a number of different symbols.
How many strings with "bbb" in them? We reduce the length of the string by 3(it is 2^(N-3)) and put "bbb" into all possible position into each such strings. How many positions? N-3+1 = N-2;
So, it is the initial formula from the first answer - (N-2)*2^(N-3). Now we have to handle the duplicates.
When do we have a duplicate? Then we insert "bbb" before "b" symbol in the string - the next insertion will give us the same result. How many times we insert before "b"? Half of the total number of insertion (there is the same number of insertions before "a" and before "b"). So, each insertion before "a" and after "a" give the different unique combinations, and insertion before "b" and after "b" gives the same unique combination. So, all we need to do is to multiply the formula by 3/4.
The resulting formula is (3/4)(N-2)*2^(N-3).
The general version is (3/4)(N-b+1)2^(N-b) where b is the length of "bb..bbb" string.
The code in C/C++
int GetNumberOfString(int N, int b)
{
return (3*N-3*b+3)*(pow(2, N-b))/4;
}