***Picking Cards

Picking Cards

Problem Statement

There are N cards on the table and each has a number between 0 and N. Let us denote the number on the ith card by ci. You want to pick up all the cards. The ith card can be picked up only if at least ci cards have been picked up before it. (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 Format
The first line contains the number of test cases T. T test cases follow. Each case contains an integer N on the first line, followed by integers c1,..ci,...,cN on the second line.

Output Format
Output T lines one corresponding to each test case containing the required answer for the corresponding test case. As the answers can be very big, output them modulo 1000000007.

Constraints:
1 <= T <= 10
1 <= N <= 50000
0 <= ci <= N

Sample Input:

3  
3  
0 0 0  
3  
0 0 1  
3  
0 3 3

Sample Output:

6  
4  
0

Sample Explanations:

For the first case, the cards can be picked in any order, so there are 3! = 6 ways.
For the second case, the cards can be picked in 4 ways: {1,2,3}, {2,1,3}, {1,3,2}, {2,3,1}.
For the third case, no cards can be picked up after the first one, so there are 0 ways to pick up all cards.

---------------------------------------editorial-------------------------------

first of all we sort given array and check for all arr[i] if

arr[i]>i than there is no way to arrange these cars 

else

we have created a dp array  which contains no of cars eligible to place at ityh position  by dp[i], 

so multiply ans by dp[i]-i , i is subtracted since i illigible cards are already used  till 0 to i-1 place ../...

example -
0 0 0 1 2 6
dp array 3(0,0,0 are eligible at i=0 ) 4(0,0,0,1)  5(0,0,0,1,2)  6(all are eligible at i=3)   6(all)
now at i=0 there are 3 ways  so ans*=dp[0]-0;
at i =1 thre was 4 ways but one of the card is used at i=0; so now only 3  remaining ans*=dp[1]-1
at i=2 ans*dp[2]-2
at i=3 ans*dp[3]-3
at i=4 ans*=dp[4]-4
at i=5 ans*= dp[5]-5;

-------------------------------------------code------------------------------

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

typedef long int li;

#define test()    int test_case;cin>>test_case;while(test_case--)

#define fr(i,n) for(int i=0;i<n;i++)

#define frr(i,a,n) for(int i=a;i<n;i++)

#define sll(a) scanf("%lld",&a)

#define sl(a) scanf("%ld",&a)

#define si(a) scanf("%i",&a)

#define sd(a)  scanf("%ld",&a)

#define sf(a) scanf("%f",&a)

#define rn(a) return a

#define pai pair<int,int>

#define pal pair<li,li>

#define pall pair<lli,lli>

#define ff first

#define ss second

#define mod  1000000007

#define mp make_pair

#define pb push_back

#define pll(a) printf("%lld\n",a);

#define pl(a) printf("%lld\n",a);

#define pi(a) printf("%d\n",a);

#define pd(a) printf("%lf\n",a);

#define pf(a) printf("%f\n",a);

int has[10000000];

lli dp[1000000];

int main()

{

test()

 {

  int f=0;

  memset(has,0,sizeof(has));

   int n ;

    si(n);

     lli arr[n+10];

     fr(i,n)

      {

         cin>>arr[i];

        has[arr[i]]++;

 }

 

 sort(arr,arr+n);

  dp[0]=has[0];

  // note dp[i] containds all no of cards which

  // are eligible to place at ith position ....

  //  for example at i=2 all cads with no <=1 are 

  // eligible to place ..

   

 frr(i,1,n)

   {

     dp[i]=dp[i-1]+has[i];// dreating dp array 

   }

 lli ans=1;

 fr(i,n)

  {

    //cout<<" i "<<i<<" ar[i] "<<arr[i]<<endl;

    if(arr[i]>i)// if after sorting also at ith 

                // position value is more than no way to arrange 

     {

       f=1;

       cout<<"0"<<endl;

       break;

}

else

{

// else we can place all cards at it position  which are eligible 

 //  some of them are already used to fill till (i-1 )

 // no of remaining eligible cards are dp[i]-i(since i cards are already used )

ans=(ans*(dp[i]-(i)))%mod;

}

  }

  

  if(f==0)

   cout<<ans<<endl;

 }

}

----------------------------------------hack editorial--------------------------------

We first sort all the cards by the value on them, and we have `

c1≤c2≤⋯≤cn.

` Then we are going to "consider" those cards one by one from `c1` to `cn`. When a card becomes ready, i.e., the # of cards we have picked `≥` the value on that card, we will not pick it up immediately. Instead, we save it in a buffer, because this card can be picked up at any time in the future. Then, when do we pick a card? The answer is we will only pick a card when we have to do, and specifically,

1. when we have already picked `x` cards, and `x<ci`, where `ci` is the current card that is being considered;
2. when all the cards have already been considered.

If the first case happens, we have to pick a card from the buffer, otherwise, `ci` up to `cn` can never be considered. If `|buffer|=0` at this time, i.e., the buffer is empty, then it is impossible to pick up the remaining cards, hence the answer is 0; otherwise, we have `|buffer|` choices, and picking any of them will result in a different (but symmetric) way. After picking one card from the buffer, the buffer will have size `|buffer|−1`, and we have picked up `x+1` cards. Then, we have to re-consider `ci`.

If it is the second case, then actually we are done. At this time, any permutation of the buffer will correspond to a valid order of picking the rest of cards, and therefore `|buffer|!` ways.

Obviously the rule of product applies here, and the above process can be done by a simple linear scan. Including the sorting, the problem can be solved in `O(nlogn)` time.

---

For example, consider `

c1=0,c2=0,c3=2,c4=2.

`

• `buffer=∅`. Picked `0` cards.
• Consider `c1`. `0≤c1`, so `c1` can be picked up all the time in the future. No need to pick it up right now, just save it to the buffer. Now, `buffer={c1}`. Picked `0` cards.
• Consider `c2`, which is similar to `c1`, i.e., save it to the buffer. Now, `buffer={c1,c2}`. Picked `0` cards.
• Consider `c3`, where `0<c3=2`. In this case, we have to pick up one card from the buffer, and we have 2 choices. W.o.l.g., let's pick up `c1`. Now `buffer={c2}`. Picked `1` cards.
• Reconsider `c3`. Again `1<c3=2`. Pick up one card from the buffer. This time, there is only 1 choice. Now `buffer=∅`. Picked `2` cards.
• Reconsider `c3`. We have `2≤c3`, and thus we can save it to the buffer. `buffer={c3}`. Picked `2` cards.
• Consider `c4`. `2≤c4`, so we can save `c4` to the buffer as well. `buffer={c3,c4}`. Picked `2` cards.
• Finally, we have already considered all the `n` cards, and there are still two in the buffer, hence `2!=2` choices.

Therefore, the total # of ways `=2×1×2=4`.

 Tested by lydxlx

Problem Tester's code :

object Solution extends App {
  val MOD = 1000000007L
  val factorial = Array.fill(55555)(1L)
  for (i <- 1 until factorial.length) factorial(i) = factorial(i - 1) * i % MOD

  for (T <- 1 to readInt) {
    val N = readInt
    val a = readLine split(" ") map(_.toInt) sorted

    def doit(i: Int, cnt: Int, queue: Int, acc: Long): Long = 
      if (i == N) acc * factorial(queue) % MOD
      else {
        if (cnt >= a(i)) doit(i + 1, cnt, queue + 1, acc)
        else if (queue > 0) doit(i, cnt + 1, queue - 1, acc * queue % MOD)
        else 0L
      }

    println(doit(i = 0, cnt = 0, queue = 0, acc = 1L))
  }
}