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