CareerCup

You can also use greedy approach. Try to assign k consecutive ad boards to the rightmost position of the current window of size M. This should give the optimal result.

a simple solution is assign 0/1 to every solution and check if all the constraints are satisfied for a given assignment.
backtrack during the assignment process if any condition is violated.

* assign 0/1 to every position

First i proposed brute force method of checking all the combinations (Time Complexity: 2^N) but he asked for a better solution, then i proposed the below solution.

Please note from here on wherever i mean N / M, i actually mean floor value of N / M.

To get the minimum number of boards required we can calculate in greedy method, where we will have to select K boards (all the remaining boards if there are no K boards) after every M - K boards, which gives us as below.

min_boards = (N / M) * K if N % M <= M - K
           = (N / M) * K + (N % M - (M - K)) otherwise

There are 4 different cases possible as listed below.

Case 1: N % M = M - K
Here the only arrangement possible is ----XXX----XXX----XXX---- for 25, 7, 3
Since the first M elements should have K selections, you can only arrange K selections among those M elements, the same applies for all successive M elements.
If you have to get a different combination for the last group (15 - 21 elements in the above example) you will have to remove at least one of the selection from the K selections, in which case the last M elements (19 - 25 elements in the above example) will lose a selection in which case minimum K criteria is not satisfied.
The same is the case for all the previous groups as well, therefore no other combination is possible.

Case 2: N % M = 0
We have an algorithm explained further down to analyze this case. Here since we have N / M groups, this is equivalent to T(G, M, K) where G = N / M.

Case 3: N % M > M - K
For example we consider ----XXX----XXX----XXX----X for 26, 7, 3
Since the first M elements should have K selections, you can only arrange K selections among those M elements, the same applies for all successive M elements.
The last M elements have K selections (XX----X in above example), but the first M - N % M (2 in above example) selections actually belong to the N / M group (3rd in above example), but it is not affordable for us to lose these selections as it will not let us satisfy the criteria of minimum K selection for the last M elements.
Similarly the same applies to all the previous groups. Therefore M - N % M selections in every group do not change and therefore there is no point calculating combinations for the same.
We can actually remove these elements and then try for the combinations.
Removing M - N % M elements in every group will make you remain with N % M elements in every group. If you notice carefully now the number of groups has increased by 1. So the new number of groups would be N / M + 1. As we removed M - N % M selections in every group K will now be K - (M - N % M), which is also same as N % M - (M - K).
Therefore this boils down to T(N / M + 1, N % M, N % M - (M - K))

Case 4: N % M < M - K
Let's consider ----XXX----XXX----XXX-- for 23, 7, 3
Since the first M elements should have K selections, you can only arrange K selections among those M elements, the same applies for all successive M elements.
For the last M elements (17 to 23 --XXX-- in above example) we cannot afford to lose these K selections out of these M elements. Therefore the combinations in the last group (15 - 21 elements in the above example) cannot have selections in the first N % M elements.
The same applies to all the earlier groups.
Therefore we could as well get rid of so many elements in every group and also the last N % M elements as we don't get to any selection in these.
Therefore we will end up with M = M - N % M, number of goups G = N / M and K will remain the same.
Therefore this boils down to T(G, M - N % M, K).

Assuming S(N, M, K) is the total number of combinations for N, M, K, based on the above analysis for different N, M, K we get the below relation between S and T.

S(N, M, K) = 1 if N % M = M - K
           = T(N / M, M, K) if N % M = 0
           = T(N / M + 1, N % M, N % M - (M - K)) if N % M > M - K
           = T(N / M, M - N % M, K) if N % M < M - K

Based on the above relation between S and T you will end up needing to calculate T(G, M, K) where G is number of groups, each group containing M elements and N = G * M. This can be calculated as below.
Since N % M = 0, N can be divided into groups of size M each.
Since each group has to have K selected we cannot move the selection to other groups.
Now we get the different combinations for each group separately, selecting K boards out of M. Suppose we generate all the combinations and store in array l[MCK] identifying each combination by its index in the array. We can go for list and use iterator to navigate if M is large as MCK does not fit in the array for M > 33. Time complexity involved here is M * MCK and space complexity is MCK as you can use BitSet for each combination.
But for the contiguous sake we can have only some combinations in group 1 against every combination in group 2, so we can calculate all combinations that can preceed each combination, say we get m[][] where m[i][j] is set if combination j can preceed combination i. We can go for maps if M is large as MCK does not fit in the array for M > 33. This can be achieved in M * MCK * MCK time complexity and MCK space complexity as BitSet can be used for second dimension array.
This applies not just for group 1 and group 2 but for any group x and group x + 1.
Let's say V(G, i) is the total number of combinations where group G can have combination i.

T(G, M, K) = sum of V(G, i) for i from 0 to MCK - 1.
V(G, i) = sum of V(G - 1, j) for all j for which m[i][j] is set.
        = 1 if G = 1.

This can be calculated by having an array v[g][i] where g is group index and i is combination index.
Calculate the values from g = 0 for all combinations based on recursive relation.
To save space we could as well have two arrays c[i] and p[i] where c holds values for current group combinations and p holds values for previous group combinations. We can go for maps if M is large as MCK does not fit in the array for M > 33.
This can be achieved in (N / M) * MCK * MCK time complexity and MCK space complexity.
So the total time complexity all three put together is M * MCK + M * MCK * MCK + (N / M) * MCK * MCK and space complexity is MCK.
But i was asked for even more better solution.
Any suggestions are most welcome.

Here is solution in java. Just find the minimum number of boards required first and check for all the combinations. In this case, we check for many combinations (sub problems) again and again. If there is a way to store this result in some DS, we can improve the performance through dynamic programming.

public static int possibleWays(int n, int m, int k) {

        /* c -> minimum board required */
        int c = n / m * k;
        int total = 0;
        if (n % m > m - k) c += n % m - (m - k);

        int array[] = new int[n];
        for (int i = 0; i < n; i++) {
            if (i >= n - c) array[i] = 1;
            else array[i] = 0;
        }

        do {
            if (validateCombination(array, m, k)) total++;
        } while(nextCombination(array));
        return total;
    }

    private static boolean nextCombination(int[] array) {
        boolean swapFound = false;
        int i, j;
        int n = array.length;

        for (i = n - 1; i > 0; i--)
            if (array[i] == 1 && array[i - 1] == 0) break;

        if (i == 0) return false;

        for (j = i - 1; j >= 0; j--)
            if (array[j] == 0) {
                swapFound = true;
                break;
            }

        if (swapFound) {
            swap(array, i, j);

            /* Sort bit array after swapping */
            int k = i;
            for (int i1 = i; i1 < n; i1++) {
                if (array[i1] < array[k]) {
                    swap(array, i1, k);
                    k++;
                }
                else if (array[i1] > array[k]) {
                    k++;
                }
            }
        }

        return swapFound;
    }

    private static boolean validateCombination(int[] array, int m, int k) {
        int n = array.length;

        for (int i = 0; i <= n - m; i++) {
            int tempK = k;
            for (int j = i; j < i + m; j++)
                if (array[j] == 1) tempK--;
            if (tempK > 0) return false;
        }
        return true;
    }

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

This should be approached and most probably solved using dynamic programming.

This should be approached and probably solved using dynamic programming.

Here is the DP approach to solve the problem.
First, we need to calculate the minimum number of boards of advertisement needed.

numBoards = (N/M) * K + Math.max(0,(K-(M - N % M)))

Next step is to find recursive solution for sub-problems.
If there are n boards that need t advertisements and m consecutive boards have been skipped,
then

numWays (n,t,m) = numWays(n-1,t-1,0)                      if m == M-1
                = numWays(n-1,t-1,0) + numWays(n-1,t,m+1)  if m < M-1
                = 1                  if k == 0 && n+m < M
                = 0                  if k == 0 && n+m >= M

Our final result will be numWays (N, numBoards, 0).

There are two ways to subdivide the problem. One to put an advertisement at nth billboard and other is not to put an advertisement on the billboard. If m = M-1 billboards have been skipped, then we cannot skip the current billboard and we have to place an advertisement on current billboard (condition 1). If m < M-1 billboards have been skipped, it is our option whether to put an advertisement on current billboard or not (condition 2).
The terminating condition of 1 means that the current placement is valid. A condition of 0 means the current placement is invalid.

Because of the recursive subproblems, the actual solution is exponential run time, however, if we use DP approach of creating solution bottom-up, our solution will be O(N*numBoards*M).

Here is the java code for a working implementation.

static int numWays (int N, int M, int K) {

    int numBoards = (N/M) * K + Math.max(0,(K-(M - N % M)));

    int[][][] matrix = new int[N+1][numBoards+1][M];

    for(int t = 1; t < numBoards+1; t++) {
      for(int m = 0; m < M; m++) {
        matrix[0][t][m] = 0;
      }
    }

    for (int n = 0; n < N+1; n++) {
      for(int m = 0; m < M; m++) {
        if(n+m >= M)
          matrix[n][0][m] = 0;
        else {
          matrix[n][0][m] = 1;
        }
      }
    }

    for (int n = 1; n < N+1; n++) {
      for(int t = 1; t < numBoards+1; t++) {
        for(int m = 0; m < M; m++) {
          if(m == M-1) {
            matrix[n][t][m] = matrix[n-1][t-1][0];
          }
          else {
            matrix[n][t][m] = matrix[n-1][t-1][0] + matrix[n-1][t][m+1];
          }
        }
      }
    }
    return matrix[N][numBoards][0];
  }

Did anyone solved this in ruby ?

Have anyone solved this in Ruby ?

plz help me solve this expression m=5 n=9 calculate the value of m+=n++- ++m+n

plz help me solve this expression m=5 n=9 m+= n++-++m+n

one solution is by doing permutations twice , like doing permutations of length M zeros with K ones and performing outward permutation by considering the whole string and permutating it by considering M length string as single entity.

after observing examples i am thinking that answer should be sum of c(m,k+i)
where i=0,1,2.....until m<=k+i
let me know if i am wrong.

Here is a rough outline for a solution that I *think* should work.I might try to code it out later.

As an example, I'll use a total length of 8, a sequence length of 4 and a required number of boards in each sequence of 2.
Take the length of the sequence of boards and calculate all the permutations that make for the required number. E.g. for the given, we have:
x x 0 0
x 0 x 0
x 0 0 x
0 x x 0
0 x 0 x
0 0 x x
An optimal solution will continuously repeat one of these subsequences. Why? Because they are the minimum subsequences that fit the requirements they are optimal, and each solution when chained together maximizes the space between the x'es to the maximum possible, thus minimizing the number of x'es that need to be placed.

So the number of possible sequences is the number of permutations of the sequence length (2^sequence_length).
However, this isn't quite good enough because we might have a remainder, so then we just need to calculate the number of combinations for the remainder (in conjunction with each pattern) that are acceptable solutions and add those together, then multiply the whole thing by two since we could take the remainder from the front or from the back.

Total=N
M banners should have atleast K consecutive banners.

We can solve this in 2 steps:

1. First assigning K blocks consecutively from end in a M window size.
2.Then running a loop which assigns an ad as we move on from index N-M to N.

The pseudo code is like:
for(j=0;j<k;j++)
{
arr[N-M+j]='C'
}
for (j=M;j<N;j++)
{
a[j]='C'
}

1st loop puts K banners from last in a M size banner block and second for loop keep on putting one banner each from Mth position to N.

int factorial(int num)
{	int fact=1;
	for( int i=1;i<=num;i++){fact = fact*i;}
	return fact;
}
int findpossibleadvertisements(int n,int m,int k)
{
	int start = m;
	int end = m+k;
	int adcount =0;
	while(end!=n)
	{
		adcount = acdount + (factorial(m)/(factorial(k)*factorial(m-k));		
		start++;end++;
	}
	return adcount;
}

int factorial(int num)
{	int fact=1;
	for( int i=1;i<=num;i++){fact = fact*i;}
	return fact;
}
int findpossibleadvertisements(int n,int m,int k)
{
	int start = m;
	int end = m+k;
	int adcount =0;
	while(end!=n)
	{
		adcount = acdount + (factorial(m)/(factorial(k)*factorial(m-k));		
		start++;end++;
	}
	retuen adcount;
}

missing fourth way: C00C