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