Live Archive 6831 - Knights of the Round Table

Problem Statement:
6831 - Knights of the Round Table

Solution:
Essentially a combinatorics problem, and hence pretty mathematical, but can be solved intuitively. To simplify the problem let's label the knights from 1 to K as well, where the knight's label determines which seat he is supposed to sit on. To get the idea on how to solve this problem, let's discuss the following test case:

chair[i] : represent numbers of the chairs
which[i] : which knight sits on chair[i]
fixed[i] : has knight i used? (hence fixed on a chair)

Test Case:
5 1
5 1

diagrams:
chair:     1  2  3  4  5
which:     5
fixed:     0  0  0  0  1

Here let's consider filling in the chairs from left to right. Let S be a set containing knights that have not been placed on any chair (initially empty), and W be the number of ways of placing the knights, initialized to 1. Starting from chair i = 1 to 5:
1. chair[1]: 1 is already filled. But fixed[1] is not set, so knight[1] has not yet been seated. So S = {1}.
2. chair[2]: fixed[2] is not set, so knight[2] is not yet seated, i.e. S = {1,2}. Now, chair[2] is empty, so we can place any knights in S (1 or 2) and put it on chair[2]. Hence we update W := W * 2 = 2.  We are left with 1 element in S, can be either knight[1], or knight[2]. It does not matter. So WLOG, S = {1}.
3. chair[3]: fixed[3] = 0, so S = {1,3}. chair[2] is empty, so W := W * 2 = 4. Remove one element in S, so say S = {3}.
4. chair[4]: similar, W = 8, say S = {4}
5. chair[5]: fixed[5] is set, so knight[5] is already used. Hence S remains {4}. chair[5] is empty, so place the only element in S on this chair.

So W = 8.

We see that we can calculate the value of W iteratively in a linear manner! You can try another set of values, the idea remains the same, that is, to maintain the set S of knights not yet seated. Play around with other values and convince yourself that you get the idea.

Here comes the last observation: If we start filling in at the correct chair, we should have the number of empty chairs encountered so far always less or equal to the number of knights not yet seated. Otherwise, we will have less knights to fill in the remaining chairs, which is contradictory to the fact that the number of free seats should in the end equals to the number of free knights. So we must find the right chair to start our algorithm which fulfil the above requirement. You can look at my implementation below to get a clearer idea:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <cstring>
using namespace std;

int fix[1000003];
int filled[1000003];
int vis[1000003];
int K, D;
long long ans;
long long MOD = 1000000007LL;

int main(){
    int u,v;
    while(scanf(" %d %d", &K,&D)!=EOF){
        ans = 1;
        memset(filled, 0, sizeof filled);
        memset(fix, 0,sizeof fix);
        memset(vis, 0, sizeof vis);
        for(int i=0;i<D;++i){
            scanf(" %d %d", &u, &v);
            filled[v] = u;
            fix[u] = 1;
        }
        int balance = 0;
        int beg = 1;
        int state = 0;
        for(int j=1;j<=2*K;++j){
            int i = (j>K?j-K:j);
            if(!state){
                if(!fix[i] && filled[i]){
                    beg = j;
                    state = 1;
                    balance ++;
                }
            } else {
                if(fix[i]) --balance;
                if(filled[i]) ++balance;
                if(balance<0){
                    beg = -1;
                    state = 0;
                    balance = 0;
                } else if(balance == 0 && j-beg+1 == K){
                    break;
                }
            }
        }
        long long cnt = 0;
        for(int j=beg;j<=2*K;++j){
            int i = (j>K?j-K:j);
            if(vis[i])break;
            vis[i] = 1;
            if(!fix[i])++cnt;
            if(!filled[i] && cnt != 0){
                assert(cnt != 0);
                ans *= cnt;
                ans %= MOD;
                --cnt;
            }
        }
        cout << ans << endl;
    }
    return 0;
}