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;
}

From this week on we start solving problems on Codechef, Interviewstreet etc. . with the view to improve your problem solving skills ..
          Apart from the code we will give a detailed mathematical and logical explanation about the problem.So lets start with something easy ..

LINK :: Question 1

Required Concepts : Euclid Algorithm

Well for both chefs we have A,B and C,D units that they can go .. so any length that is traversable by first chef is a multiple of gcd(A,B) and similarly any length that is traversable by second chef is a multiple of gcd(C,D) .. Hence units which are traversable by both are multiples of lcm=LCM(gcd(A,B),gcd(C,D)).Thus for the positive half of 1 to K number of such units equals K/lcm which is same on the other side of the rope. Hence our answer is 2*(K/lcm) + 1(bcz 0 is traversable by both as both can go forward and come back by same value).

typedef unsigned long long LL;
int T;
LL A,B,C,D,K;

LL gcd(LL a,LL b)    //euclid method for fast gcd
{
    if(b>a)
    return gcd(b,a);
    else
    return b==0?a:gcd(b,a%b);
}

int main()
{
    cin>>T;
    for(int i=0;i<T;i++)
    {
        cin>>A>>B>>C>>D>>K;
        LL n1=gcd(A,B);
        LL n2=gcd(C,D);
        LL den=gcd(n1,n2);
        LL S=n1/den;     //split the LCM part 1
        LL R=K/S;        //LCM part 2
        LL n4=R/n2;      //the final value
        cout<<(2*n4)+1<<endl;
    }
    return 0;
}

For finding LCM of a and b we used (a*b/gcd(a,b)) ..