In this HackerEarth Chess Tournament problem solution, 2N participants (P1, P2, P3 ...., P2N ) have enrolled for a knockout chess tournament. In the first round, each participant P2k-1 is to play against participant P2k, (1 ≤ k ≤ 2N-1). Here is an example for k = 4 :

Some information about all the participants is known in the form of a triangular matrix A with dimensions
(2N-1) X (2N-1). If Aij = 1 (i > j), participant Pi is a better player than participant Pj, otherwise Aij = 0 and participant Pj is a better player than participant Pi. Given that the better player always wins, who will be the winner of the tournament?


HackerEarth Chess Tournament problem solution


HackerEarth Chess Tournament problem solution.

#include<stdio.h>
int a[2000][2000],r[10][2010];
int main()
{
int n;
int p[]={1,2,4,8,16,32,64,128,256,512,1024,2048},i,j;
scanf("%d",&n);
for(i=1;i<=p[n]-1;i++)
{
for(j=1;j<=i;j++)
{
scanf("%d",&a[i+1][j]);
}
}
for(i=1;i<=p[n];i++)
{
r[0][i]=i;
}
for(i=1;i<=n;i++)
{
for(j=1;j<=p[n-i];j++)
{
if(a[r[i-1][2*j]][r[i-1][2*j-1]]==1)
{
r[i][j]=r[i-1][2*j];
}
else
{
r[i][j]=r[i-1][2*j-1];
}
}
}
printf("%d\n",r[n][1]);
return(0);
}


Second solution

#include <bits/stdc++.h>

using namespace std;

int A[1025][1025];
int tree[100005];

void build(int where, int left, int right)
{
if ( left > right ) return;
if ( left == right ) {
tree[where] = left;
return;
}
int mid = (left+right)/2;
build(where*2, left, mid);
build(where*2+1, mid+1, right);
int fs = tree[where*2];
int sc = tree[where*2+1];
if ( A[fs][sc] ) tree[where] = fs;
else tree[where] = sc;
}

int main()
{
int n;
cin >> n;
assert(n>=1 && n <=10);
for ( int i = 2; i <= (1<<n); i++ ) {
for ( int j = 1; j < i; j++ ) {
cin >> A[i][j];
assert(A[i][j] >= 0 && A[i][j] <= 1);
A[j][i] = (A[i][j]^1);
}
}
build(1,1,1<<n);
printf("%d\n", tree[1]);
return 0;
}