Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

The problem below appeared on the last Code Sprint 2 programming competition (it's over already). The base cases are clear, but developing an algorithm that solves all possible cases has been a challenge so far.

There are N cards on the table and each has a number between 0 and N on it. Let us denote the number on the Nth Ni. You want to pick up all the cards, but you can only pick a specific Nth card if you already picked Ni cards before. (As an example, if a card has a value of 3 on it, you can’t pick that card up unless you’ve already picked up 3 cards previously) In how many ways can all the cards be picked up?

Input are the cards with their respective numbers, and the output should be the total number of ways possible to pick them up.

Sample Input:
0 0 0 
Sample Output:
6

Sample Input:
0 0 0 0 
Sample Output:
24

Sample Input:
0 0 1
Sample Output
4

Sample Input:
0 3 3
Sample Output:
0
share|improve this question

3 Answers 3

up vote 3 down vote accepted

Here's a quick implementation in java. The idea is to find how many cards can be picked each step by counting the number of cards with a number below this step and subtracting the number of cards already picked. Of course a lot of work is unnecessarily repeated, but this should give a good idea of how to approach this problem.

public class PickCards {
public static int countLessOrEqualThanMax(int[] cards, int max) {
    int count = 0;
    for (int number : cards) {
        if(number <= max) count++;
    }
    return count;
}

public static void main(String[] args) {
    int[] cards = {0, 1, 2, 4, 3};
    int numberOfWays = 1;
    for(int i = 0; i < cards.length; i++) {
        int ways = Math.max(0, countLessOrEqualThanMax(cards, i) - i);
        numberOfWays *= ways;
    }
    System.out.println(numberOfWays);
}

}

share|improve this answer
    
This answer is correct: you can reduce the running time to linear by using counting sort on the cards, precomputing the answers of countLessOrEqualThanMax and then iterating over the cards in their sorted order. –  Alex ten Brink Jan 9 '12 at 15:39

As a starting point, for the case where all cards are zero:

Output = N!

For example:

Sample Input: 0 0 0

Sample Output: 3 x 2 x 1 = 6.

Clearly, any card with a number higher than 0 will reduce the number of possible ways of picking up the cards.

Any card with "N" on it will make it impossible to pick up the cards.


Edit:

Consider N=4 cards where:

A=0, B=0, C=1, D=2

C can't appear in column 1. D can't appear in column 1 or 2.

  1. A, B, C, D - Y
  2. A, B, D, C - Y
  3. A, C, B, D - Y
  4. A, C, D, B - Y
  5. A, D, B, C - N
  6. A, D, C, B - N

  7. B, A, C, D - Y

  8. B, A, D, C - Y
  9. B, C, A, D - Y
  10. B, C, D, A - Y
  11. B, D, A, C - N
  12. B, D, C, A - N

  13. C, A, B, D - N

  14. C, A, D, B - N
  15. C, B, A, D - N
  16. C, B, D, A - N
  17. C, D, A, B - N
  18. C, D, B, A - N

  19. D, A, B, C - N

  20. D, A, C, B - N
  21. D, B, A, C - N
  22. D, B, C, A - N
  23. D, C, A, B - N
  24. D, C, B, A - N
share|improve this answer
    
Yep that far I had arrived as well. The challenge is to create an algorithm that will solve all the possible cases. –  daniels Jan 9 '12 at 12:23
    
@daniels: I've expanded my answer. –  Kramii Jan 9 '12 at 12:46
    
Kramil, that helps, but having the algorithm itself would help even more. I am taking a look FranKL's algo now. Looks like he nailed it, do you agree? –  daniels Jan 9 '12 at 13:09
    
@daniels: FrankL's method looks fine, but is a lot of work when a simple formula can give the answer. –  Kramii Jan 9 '12 at 13:16
    
@Kramil, And what's that formula? Cause I agree a formula would be ideal, but I fail to see how we could develop one single formula that solves all possible inputs. –  daniels Jan 9 '12 at 13:36

The algorithm in pseudocode isn't efficient, but it will find ALL cases

   //Create an array that stores card number, 
   //position, and a flag that denotes it is picked or not, 
   //initialize with not picked:
   (1, 10 , false) , ( 2, 9, false) .....

   // try to pick each item in array, 
   // and spawn a new sub-process tree for each possible move
   trypick(ARRAY)
   // try all cards one by one
   for i = 1 until N 
       if ARRAY[i].ispicked 
           // just skip it if its already picked
           do nothing 
       else
           // if its pickable hurray, but we are not 
           // generating a sub-process tree if it is not a valid case
           if ARRAY[i].number <= ARRAY[].Count(ispicked) 
               // pick it
               ARRAY[i].ispicked = true
               // spawn a new array tree for each possible 
               // move for the subtree generated
               trypick(ARRAY)  
   if ARRAY[].Count(ispicked) = N
       // we have picked all cards, lets ad plus one to our total
       totalways++   
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.