## 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;
int can_meet;
int winner;
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;
}