Thursday, October 30, 2014

SPOJ - Musketeers (MUSKET)

Problem Statement:
SPOJ - MUSKET

Summary:
N people are standing in a circle. In each round, a person will fight his right neighbor. The loser leaves the circle and the circle tightens. Given a matrix A(i,j) where 1 indicates person i wins against person j and 0 otherwise, find the number of people who may be the last man standing, and output all of them.

Solution:
I think this problem is very difficult :O The DP idea goes as follows:
We focus on one person at a time to determine whether he can be the last man standing. Call this person P.

Amongst the rest N-1 people, there are some who P can win a fight against. We check each of them one by one in the following manner:
Call the current person Q. Hence if there exist a way such that P and Q be the last people standing, then P can defeat Q, hence P may be the last man standing. The chord PQ dissect the circle into 2 parts. For each part, P and Q must be able to "clear" those people by fighting them at the right time. We say that P can meet Q. So we check, for each part:
If there is a person between P and Q, call R, that can be won over by either P and Q, then if people between P and R can be cleared, and people between R and Q can be cleared, then P can meet Q through R. We check for all such R.

Implementation:

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


int win[103][103];
int can_meet[103][103];
int winner[103];
int N;
int ans;

int meet(int i, int j) {
    if ((i+1)%N == j || i==j) return 1;
    if (can_meet[i][j] != -1) return can_meet[i][j];
    //can i meet with j using a intermediary person?
    for(int mid = (i+1)%N; mid != j; mid = (mid+1)%N) {
        if(win[i][mid] || win[j][mid]){
            if(meet(i, mid) && meet(mid, j)){
                can_meet[i][j] = 1;
                return 1;
            }
        }
    }
    can_meet[i][j] = 0;
    return 0;
}

void solve(){
    for (int i=0;i<N;++i){
        for(int j=0;j<N;++j){
            if(i==j || !win[i][j]) continue;
            if(meet(i, j) && meet(j, i)){
                winner[ans++] = i+1;
                break;
            }
        }
    }
    printf("%d\n", ans);
    for(int i=0;i<ans;++i){
        printf("%d\n", winner[i]);
    }
}


int main(){
    int tc;
    cin >> tc;
    while(tc--){
        ans = 0;
        cin >> N;
        for(int i=0;i<N;++i){
            for(int j=0;j<N;++j){
                scanf("%1d", &win[i][j]);
            }
        }
        for(int i=0;i<N;++i){
            for(int j=0;j<N;++j){
                can_meet[i][j] = -1;
            }
        }
        solve();
    }
    return 0;
}