FALLACY OF WASSEYPUR - Editorial

rxhxn30 · March 23, 2023, 2:31pm

PROBLEM LINK: CodeChef: Practical coding for everyone

DIFFICULTY
SIMPLE

PRERQUISITES
None

PROBLEM
Sardar and Ramadhir have an army of size n and m respectively. There are k revenge targets, each denoted by (i,j). If i^j is odd, j is killed, else i is killed. Problem is to find out which person has a larger army size at the end.

EXPLANATION
The problem boils down to:-
Iterate through each revenge query, check the bitwise XOR of i and j. Subtract either n or m based on the XOR.
Finally compare n and m and conclude.

SOLUTION

Setter's Solution

    int n,m,k;
    cin >> n;
    bool a[1000007]={0},b[1000007] = {0};
    for(int i=0;i<n;i++){
        int x;
        cin >> x;
        a[x]=1;
    }
    cin >> m;
    for(int i=0;i<m;i++){
        int x;
        cin >> x;
        b[x]=1;
    }
    cin >> k;
    while(k--){
        int p,q;
        cin >> q >> q;
        if(!a[p] || !b[q]) continue;
        if((p^q)&1) {b[q]=0;m--;}
        else {a[p]=0;n--;}
    }
    if(n>=m) cout << "Sardar" << nline;
    else cout << "Ramadhir" << nline;

Time Complexity : (O(2*n+k))