Byteknights and Byteknaves : Codechef

LINK :: Question

Required Concepts : Partial Difference

Explanation : A number n will be a possible answer if the number of people having n in their range is exactly n (Byteknights always tell truth and knaves lie ). Therefore for each a and b input we need to increment its value by 1 so that in the end we have an array that represents how many people have told element i to be in their range . Let this array be KNUM, then element i can be a byteknight if KNUM[i]=i

         Instead we store a partial difference array with diff[i]=knight[i]-knight[i-1] . Thus for each a,b we need to increase diff[a] and decrease diff[b+1] for ith entry.

Thus ,

                                      KNUM[i]=diff[0]+diff[1]...diff[i]

If every n is a value in between limits of ith bytelandian then he has to be a knight else for a value he can become a byteknave and this is needed to print the lexicographic smallest one. And since he will be a byteknave his limit should be excluded from the range of n we have taken as possible because he speaks lie always.

CODE EXPLAINED :

#include <cstdio>
#include <set>
using namespace std;

int main(){
    int T;          //the number of test cases
    for(scanf("%d", &T); T--; ){
        int N, lo[50000], hi[50000], diff[50002]={0};     

        //the arrays to store ranges and diff
        scanf("%d", &N);
        for(int i=0; i<N; i++){
            scanf("%d%d", lo+i, hi+i);
            diff[lo[i]]++;
            diff[hi[i]+1]--;
        }
        set<int> good;      //set of all possible byteknights
        int ans=0, count=0;
        //if knights[n]=n then it can be a byteknight and
        //knights[n]=sum diff[i] from 0 to n
        for(int i=0; i<=N; i++){
            count+=diff[i];
            if(count==i){
                ans++;
                good.insert(i);
            }
        }
        printf("%d\n", ans);
        for(int i=0; i<N; i++){
        //tells truth i.e all possible knights are in his range
         //he has to be a byteknight
            if(lo[i]<=*good.begin() && *good.rbegin()<=hi[i])  
                putchar('1');
            else{
                putchar('0');
      //is made a knave and his range can be excluded from good set
                good.erase(good.lower_bound(lo[i]), good.upper_bound(hi[i]));
            }
        }
        putchar('\n');
    }
    return 0;
}