DFMTRX - Editorial

vijju123 · January 28, 2020, 5:46pm

PROBLEM LINK:

Div1
Div2
Practice

Setter- Kasra Mazaheri
Tester- Encho Mishinev
Editorialist- Abhishek Pandey

DIFFICULTY:

Medium-Hard

PRE-REQUISITES:

Constructive Algorithms OR Classical Round Robin

PROBLEM:

For a given N, make such a 2-D \ N \times N matrix such that for every i from 1 to N, all elements from 1 to (2N-1) lie in i'th row and i'th column combined.

QUICK-EXPLANATION:

Key to AC- Observing pattern led to lot of ACs.

Realize that for every odd N (except N=1, obviously) , no answer exists. Now, we can do 2 things to solve the problem. The first is to observe the pattern and extend it. The second way is to correlate the problem to Round Robin tournament.

Lets correlate it to Round Robin theory. Fill (2N-1) in the diagonal. We now have to fill the remaining matrix with (2N-2) elements. Now, look at one of the halves of the matrix. Since there are 2 halves, each half can be filled with N-1 elements.

In each half, we have N rows (or columns!) - let them represent teams. We define A[i][j]= \text{Day when i'th team fights against j'th team}. Now we can either run Round Robin Tournament algorithm independently on the 2 halves (taking care to map days correctly in latter half else they will also be in range [1,N-1]) .

Alternatively, to make the implementation easier, pair elements such that their sum is 2*N-1, i.e. pair (1,2N-2) , (2, 2N-3)....(2N-2,1). We run round robin in one half, and if A[i][j]= \text{first element of pair} , then A[j][i] = \text{second element of the pair}.

EXPLANATION:

We will discuss the following in this editorial-

Simple proof on why answer does not exist for odd N
Pattern based Solution
Round Robin based solution (in brief)

Lets get started without delay

Proof that Doofish Matrix doesn't exist for odd N (Must Read)

This is a very crucial part of the question, and simultaneously the part where I feel most of participants got away with…sub-optimal proofs. First we will discuss the proof itself, and then I will elaborate on why that proof is good and what things you need to keep in mind while proving to avoid committing mistakes.

Our proof will be from that of contradiction - because such proofs are significantly easier many times than proof by construction (its natural fault finding in construction v/s construction , we all know what humans prefer )

Lets say we have a N \times N sized Doofish Matrix A. What we basically have is, for each (row,column) pair (i,i), we have all elements from [1,2N-1] in it. Now, few obvious observations follow-

Lemma \ 1- We have N slots in diagonal but (2N-1) elements. Hence, there will at least be 1 element x which never occurs on diagonal as long as N > 1.
Lemma \ 2- We have (2N-1) slots to fill in each row-column pair. We have to fill them with (2N-1) elements such that each element occurs at least once. \implies Each element must occur exactly once in each row-column pair.

\text{"Very wise and unintuitive lemmas you pointed out above, Meester Editorialist"}
- \text{Someone from the crowd}

Now, we know that x does not occur on diagonal anywhere. Look at cell indices where x occurs. Say x occurs in cells \large (i_1,j_1), (i_2,j_2),...,(i_p,j_p). Since x does not occur on diagonal, we know that i_k \neq j_k \forall k \in [1,p] for all of the cells where x occurs.

What does this mean? Simple, that row and column indices of cells where x occurs is not same. We are talking of obvious stuff so far. Now, lets get to the point!

List valid indices for rows/columns, i.e. all numbers from 1 to N, in a line. Eg - [1,2,3,...,N]. If x occurs in cell (i_k,j_k), then form a pair of these 2 numbers from list and call them related. These are related in the sense, that x occurs in cell (i_k,j_k) and satisfies its existence in i_k'th row and j_k'th column. We obviously notice that, since x occurs only once in a row-column pair, any number can be related with exactly 1 other number (and that number must not be related with any other number either!).

Now, 2 things can happen (w.r.t. parity of N).

If N is even, all the numbers from 1 to N get paired off nicely. Yay, we achieved nothing with this exercise.

If N is odd, one number will be left off. This is because we always eliminate/pair numbers taking 2 at a time. Notice that , by our lovely and obvious lemma 2, x can occur ONLY once in each row-column pair.

What does this mean? What state are we exactly in? Where are we going with this?

Our current state is that, we took all numbers from 1 to N, for each (i_k,j_k) where x occurred, we paired those numbers together and are finally left with one single index, say L with no other index to pair it with. This means x occurs such that it satisfies its existence only in L'th row and L'th column. But this is only possible for a diagonal element, and is a contradiction to our established fact that (i_k \neq j_k) for x.

Hence, we prove by contradiction that if N is odd, our lovely N \times N matrix A is not doofish matrix. Note that obviously, N=1 is a corner case because of whats mentioned in Lemma 1. Doofish Matrix exists for N=1.

Think about it for a minute. You cannot place x on diagonal. Anywhere else you place x, will satisfy relate/pair 2 numbers from the list. No matter where you place x (Except diagonal), it will occur in 2 row-column indices which are related. And also x can only occur once in a given row-column pair due to limited slots. All these contradictions point towards impossibility of Doofish Matrix for odd N.

Grasp the above proof, try the above exercise if you want. Once you grasp it, try to see why its amazing. I can go on and on here, but to keep editorial short, I will just say that this proof makes no assumption or anything about ideal strategy to make Doofish Matrix. All the assumptions used are obvious assumptions inferred from problem statement, and the method of grouping - although tricky to discover, is very neat.

If you want a lot more detail on why other proofs were sub-optimal and why I feel this proof is better than those, I have made a section in bonus corner for that.

Pattern based Solution

This section is going to be graphic (no pun intended!). The section will mainly be, kind of “showing” the pattern. With pattern based stuff, there is this thing that theres not a lot of meaty part. We see examples, we notice a pattern and thats it. This means that many times there are issues when trying to come up with a pattern based solution. I have briefly discussed some of them and their solutions in the bonus corner for the interested people.

The first image is Fig.1 and the next one is Fig.2. This pattern based solution is taken from the video editorial of @som_s_mukherji . The only reason being, in case the editorial is not clear to you, you guys will have an additional resource to refer to. There are a LOT of patterns to make Doofish Matrix, and you can refer to the linked paper at the end to see alternate construction methods.

The first step to solve the problem was, to fill all the diagonals with same element - preferably (2N-1). The diagonal divides the matrix into 2 triangular halves- upper and lower. For sake of convenience, lets fill upper half with numbers from [1,N-1] and other half with numbers from [N,2N-2].

Now, our current state is, we have 2 triangular halves. We want a algorithm which will take a half and fill it appropriately. Lets first discuss this algorithm, and then worry about the next half. Lets try to see the algorithm, or rather, the pattern to make Doofish matrices.

Say we are filling the upper half (with numbers in range [1,N-1]) first. Now, observe the last 2 Doofish matrices (N=6,8) given in the image. Note the following points:

Closely look at the last number in first row. Its always N-1. Now, pay attention to the last column.
You can see that second row’s last element is/can-be always 2. Also, you will see that consecutive elements at the last column are at a gap of 2. Hence, its not hard to deduce that except for last element, all elements are given by:
A_{i,N} = [(N-2)+2i] \% (N-1) +1 \ \ \forall i \in [0,N-1]
Write all numbers from [1,N-1] in a line. Now come at the next vacant cell in that row, in the upper half triangle which we have to fill. You will see that this element will be "\text{Element in last Column} \% (N-1) +1. All further elements in the row are just [Previous \ Element +1] \%(N-1) +1

With this algorithm, we can populate the upper triangle. Now we have to repeat the sample algorithm on lower triangle, but with values in range [N,2N-1]. The easiest way to achieve this is by reflecting the upper triangle along diagonal, and adding N-1 to all values in lower triangle. In other words, simple have A[j][i] = A[i][j]+(N-1) and we will have same effect as if we ran the algorithm on lower triangle with values [N,2N-2].

This ends the pattern based solution. There are a LOT more patterns available, so I do advice to at least check out the paper linked in bonus section for alternate algorithms. The sole purpose of considering this pattern over others was the fact that you guys can go refer to something else as well in case the editorial does not clear everything up.

Round Robin based Solution (Brief Discussion)

We will briefly discuss the intuition of this solution.

Say we are to make a Doofish matrix of size N, where N is obviously even. We fill the diagonal with (2N-1). Now we are to fill rest of the matrix with values from [1,2N-2]. Again, the diagonal divides the matrix into 2 triangles - upper and lower. Lets try to fill upper triangle with numbers in range [1,N-1] , and other with numbers from [N,2N-2].

The first thing to do is, to look at Round Robin Scheduling. If you haven’t yet, please go through the link in wikipedia and at least read the Scheduling section. Notice that it says that if we have N teams, and N is even, we just need (N-1) days to complete the tournament - provided we are able to hold multiple rounds in a day (and a team plays only one match a day).

This provides the first hint. What if I define the values of matrix, i.e. A[i][j] as-
A[i][j] = \text{Day when i'th team plays against the j'th team}

Keeping focus still at upper triangle, we realize the following things must hold in the round robin tournament:

A team has to play exactly one match against every other team. This means that A[i][j] will only have a single value at a given cell (instead of having multiple values at same cell). [ Very trivial and mundane stuff to point out - but necessary].
A team can only play one match a day. This means that, a row or column cannot have duplicate value as that will mean 2 matches in a day for some team. Hence, the row/column will be filled with (unique/distinct) values in range [1,N-1] with each value occurring at most once in that row/column.
If for 2 cells, (i_1,j_1) and (i_2,j_2), the value of matrix is same, i.e. A[i_1][j_1] = A[i_2][j_2], then we know that i_1 \neq i_2 \neq j_1 \neq j_2 else a row/column will have duplicate values. (Beware - If you are reading on phone, the not equal to sign (\neq) looks exactly same as equal to sign (=). The sign used above is not equal to).
We are trying to hold as many rounds as possible in parallel. Hence, At every step, we will pair off all the (currently available) teams from 1 to N to fight or contest against each other. Mathematically, this means that, if its possible for A[i_1][j_1] to be equal to A[i_2][j_2], then they will be equal. This step is analogous to the step where we paired off numbers from 1 to N for the value x in our proof.

If you see closely, and refer back to our proof, you will see that this round robin scheduling results in a Doofish Matrix! What did we do so far? We just looked at some Round Robin tournament properties, saw what effect/constraints they put on the matrix and realized that “Hey! These are same as the properties we established in our proof!”. This is more than enough of an intuition to that Round Robin Scheduling will result in a Doofish Matrix - at least in the upper half!

If the upper half is filled validly, the only thing remaining is to fill the lower half - but with values in range [N,2N-2]. The easiest way, as usual, is to make A[j][i] = A[i][j] + (N-1) as you will see that this will result in as if we performed Round Robin Scheduling in lower half but with values in range [N,2N-2] (why?).

Now all that is left is applying the algorithm in upper half, or rather, just implementing Round Robin Scheduling. Since it is purely classical implementation, it is not discussed in the editorial (as frankly, there is nothing to discuss. Everyone will have to hunt for implementations THEY tune with). You can refer to setter or tester’s code as usual for implementation references.

We shall, however, discuss one implementation for sake of completeness of the editorial. To schedule matches in round robin fashion, the tester has used the O(N^2logN) recursive algorithm, while the setter has used an O(N^2) approach. We shall discuss setter’s implementation below.

Imagine all teams are arranged in a circle uniformly, i.e. distance between the adjacent teams is constant. Now, following cases arise-

If N is odd -
- Although its not required for the question, as Doofish Matrix doesnt exist for odd N, the algorithm for even N uses this solution.
- Say we are in the i'th iteration.
- Draw a line from i'th team’s position to the centre of the circle. Note that this is nothing but radius of the circle. Call this line OP.
- Schedule matches between all the teams such that the chord joining them is perpendicular to OP.
- The above might sound complex, but it is just “Schedule matches between both the teams at a distance of 1 from i'th team, then both teams at distance of 2 from i'th team, …, both teams at distance of N/2 from i'th team.”
Case when N is even -
- Ignore the last team and schedule the matches for remaining N-1 cases using the algorithm for odd case.
- In odd N case, exactly one team was at break every day.
- Hence, we take the team we ignored, and ask it to fight against the team at break. This completes the algorithm.

The code for it is below:

Code

        ll nn=n-1;
		for(ll i=0;i<nn;i++){
			ll l=(i-1+nn)%nn;
			ll r=(i+1+nn)%nn;
			tmp[i][nn]=i;
			tmp[nn][i]=i;//We just add (N-1) while printing lower matrix
			for(ll j=0;j<nn/2;j++){
				tmp[l][r]=i;
				tmp[r][l]=i;
				l=(l-1+nn)%nn;
				r=(r+1+nn)%nn;
			}
		}

SOLUTION

Setter

// ItnoE
#include<bits/stdc++.h>
using namespace std;
typedef vector < vector < int > > Grid;
const int N = 2019;
bool M[N];
Grid G[N];
inline void Solve(int n)
{
    if (M[n])
        return ;
    M[n] = 1;
    Grid &A = G[n];
    A = vector < vector < int > > (n, vector < int > (n, 0));
    if (n & 1)
    {
        for (int i = 0; i < n; i ++)
            for (int j = 1; j <= n / 2; j ++)
            {
                int a = (i + j) % n;
                int b = (i - j + n) % n;
                A[a][b] = A[b][a] = i;
            }
        return ;
    }
    int m = n / 2;
    Solve(m);
    if (m & 1)
    {
        for (int i = 0; i < m; i ++)
            for (int j = 0; j < m; j ++)
                A[i][j] = A[j][i] = A[i + m][j + m] = A[j + m][i + m] = G[m][i][j];
        for (int i = 0; i < m; i ++)
            A[i][i + m] = A[i + m][i] = i;
        for (int d = 1; d < m; d ++)
            for (int i = 0; i < m; i ++)
                A[i][m + (i + d) % m] = A[m + (i + d) % m][i] = m + d - 1;
        return ;
    }
    for (int i = 0; i < m; i ++)
        for (int j = 0; j < m; j ++)
            A[i][j] = A[j][i] = A[i + m][j + m] = A[j + m][i + m] = G[m][i][j];
    for (int d = 0; d < m; d ++)
        for (int i = 0; i < m; i ++)
            A[i][m + (i + d) % m] = A[m + (i + d) % m][i] = m + d - 1;
    return ;
}
inline Grid Matrix(int n)
{
    Solve(n);
    Grid A = vector < vector < int > > (n, vector < int > (n, 0));
    for (int i = 0; i < n; i ++)
        A[i][i] = 2 * n - 1;
    for (int i = 0; i < n; i ++)
        for (int j = i + 1; j < n; j ++)
            A[i][j] = G[n][i][j] + 1, A[j][i] = 2 * n - 2 - G[n][i][j];
    return (A);
}
int main()
{
    int q;
    scanf("%d", &q);
    for (; q; q --)
    {
        int n;
        scanf("%d", &n);
        if (n == 1)
            printf("Hooray\n1\n");
        else if (n & 1)
            printf("Boo\n");
        else
        {
            printf("Hooray\n");
            Grid A = Matrix(n);
            for (int i = 0; i < n; i ++)
                for (int j = 0; j < n; j ++)
                {
                    printf("%d", A[i][j]);
                    if (j < n - 1)
                        printf(" ");
                    else
                        printf("\n");
                }
        }
    }
    return 0;
}

Tester

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
 
int grid[2011][2011];
int temp[2011][2011];
 
void showTemp(int n)
{
    int i,j;
 
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=n;j++)
        {
            printf("%d\t",temp[i][j]);
        }
        printf("\n");
    }
}
 
void buildUpper(int n)
{
    if (n == 2)
    {
        grid[1][1] = 1;
        grid[1][2] = 2;
        grid[2][2] = 1;
 
        return;
    }
 
    int i,j;
 
    if (n % 4 == 0)
    {
        buildUpper(n / 2);
 
        for (i=1;i<=n/2;i++)
        {
            for (j=i;j<=n/2;j++)
            {
                temp[i][j] = grid[i][j];
                temp[i + n/2][j + n/2] = grid[i][j];
            }
        }
 
        for (i=1;i<=n/2;i++)
        {
            int value = i + n / 2;
            for (j=n/2+1;j<=n;j++)
            {
                temp[i][j] = value;
 
                value++;
                if (value > n)
                    value = n / 2 + 1;
            }
        }
    }
    else
    {
        buildUpper(n / 2 + 1);
 
        for (i=1;i<=n/2;i++)
        {
            for (j=i;j<=n/2;j++)
            {
                temp[i][j] = grid[i][j];
                temp[i + n/2][j + n/2] = grid[n/2 + 1 - j][n/2 + 1 - i];
            }
        }
 
        for (i=1;i<=n/2;i++)
        {
            int value = i + n / 2 + 1;
            for (j=n/2+1;j<=n;j++)
            {
                temp[i][j] = value;
 
                value++;
                if (value > n + 1)
                    value = n / 2 + 2;
            }
        }
 
        for (i=1;i<=n/2;i++)
        {
            temp[i][n - i + 1] = grid[i][n/2+1];
        }
    }
 
    for (i=1;i<=n;i++)
    {
        for (j=i;j<=n;j++)
        {
            grid[i][j] = temp[i][j];
        }
    }
}
 
int main()
{
    int i,j;
    int q;
    int test;
 
    scanf("%d",&q);
 
    for (test=1;test<=q;test++)
    {
        int n;
 
        scanf("%d",&n);
        
        int cp = n;
        while (cp > 1)
        cp /= 2;
        
        if (cp != 1)
        return 0;
 
        if (n == 1)
        {
            printf("Hooray\n1\n");
            continue;
        }
 
        if (n % 2 == 0)
        {
            printf("Hooray\n");
        }
        else
        {
            printf("Boo\n");
            continue;
        }
 
        buildUpper(n);
        for (i=2;i<=n;i++)
        {
            for (j=1;j<i;j++)
            {
                grid[i][j] = n + grid[j][i] - 1;
            }
        }
 
        for (i=1;i<=n;i++)
        {
            for (j=1;j<=n;j++)
            {
                printf("%d",grid[i][j]);
 
                if (j != n)
                    printf(" ");
            }
            printf("\n");
        }
    }
 
    return 0;
}

Time Complexity=O(N^2LogN)
Space Complexity=O(N^2)

CHEF VIJJU’S CORNER

If you liked the problem, you can find alternate perspective of it in here . This proof in editorial is derived from there, and there are 2 alternate construction algorithms given there as well!!
With respect to Doofish Matrix, answer the following:
- Say you are allowed to put multiple elements at diagonal. Find the minimum value K such that if K extra elements are allowed on diagonal, then Doofish Matrix is possible for odd N.
- Find maximum upper bound on L such that if the statement asked to populate row-column pair with numbers from [1,L], Doofish matrix is possible for odd N
Say Doofish Matrix need not be a square matrix. It can be any N \times M matrix. With respect to this, answer the following:
- What ambiguities arise with above definition if standard conditions of Doofish Matrix apply?
- Say that I resolve above ambiguity by saying “For every row column pair (i,j), every element from [1,N+M-1] must be present in it.”. Can you find the base cases where the modified Doofish Matrix does not exist?
You are given a 3-D cube of dimensions N \times N \times N. If it satisfies some conditions (given below) related to what we saw in the problem, we call it Doofish Cube. Hence, with respect to the problem Doofish Matrix, answer the following:
- You have to fill the cube with numbers from [1,3N-1]. Find the condition(s) when Doofish cube is not possible. (Hint: Can we repeat the proof in editorial?)
- Answer above part for values in range [1,N] and [1,N+1]. Is there any difference in your answer? Can you comment on upper bound L such that if we are to fill cube with numbers from [1,L], then Doofish Cube is possible only for N \implies N \% 3==0 .
- Lets say that the cube (or rather, cuboid) is of dimensions X \times Y \times Z. How does this affect the upper bound on L and case making on when Doofish Cuboid is possible?

Why the proof in editorial is good.

First we will discuss why other proofs were sub optimal.

Taking one of the proofs a contestant told me he used, “I fill entire diagonal with (2N-1), or any element k and now *insert some math here* I get that each cell needs \large \frac{N}{2} cells so…”

Now, why is this wrong? I will point some flaws here-

The proof fills all diagonal elements with k and claims that since it cannot proceed after a point for odd N, odd N must be impossible. But where does the proof prove that filling entire diagonal with k is optimal? What about Doofish matrix where entire diagonal is not same? The proof assumes that Doofish matrix are possible only if diagonal are filled with same element, and backfires strongly for Doofish Matrices where diagonals are not same. Perhaps its possible that no doofish matrix exist with diagonal elements not being same, but that has to be proved as well! We cannot just take this fact for granted. So if your proof did not answer this, its suboptimal!
At one point the proof says I have N*(N-1)/2 cells to fill with (N-1) elements and so each element gets N/2 cells. What does this N/2 cell mean? What compulses that each element should occur exactly in N/2 cells? If your proof does not answer that, its sub-optimal!

But look at the proof in editorial. It does not make any assumption about optimal solution. It uses only the lemmas obvious from problem statement, and hence is more general than the other proofs. Thats why I like this proof over the rest - call me biased I dont care . I agree that the proof is hard to come up with - even I had to bang my head for a day to grasp it, but its beautiful and worth it.

Issues with pattern based solutions

To notice the issues in pattern based solutions, we should first know what exactly a pattern based solution strives for.

A pattern based solution tries to go through favourable solutions and notice an underlying pattern/relation followed by them which can non-trivially aid in finding the construction/solution.

There are multiple problems which are faced here-

How to generate enough solutions to see the pattern ?
How to filter favourable solutions out of above to see the pattern?
How to be sure that the pattern is valid and does not fail for higher N ?

For first part, usually people use the brute force generators. While it works in many problems, I will ask you was it feasible here? The most brute force approach to fill a matrix and check if its doofish or not would be to try all \large (2N-1)^{N^2} matrices? Or perhaps if you optimize you can get a factorial complexity brute force which deals with permuting the row-column pair. But the issue is clear - how many solutions can it generate?

For this problem, it required to use intuition and draw examples by hand. And not just any examples, draw favourable examples by hand. If you referred to my images where I drew doofish matrix for N=6,8, you will know that those were not the only Doofish matrix for N=6,8. But they were favourable Doofish matrices which let me see a pattern and generalize it.

With above 2 in mind, I will not be surprised if people say this Q took them more than 2 days to solve. Observing pattern takes time, energy and a lot of alertness. Especially when you skip the step of filtering favourable solutions.

The last hurdle, i.e. proving if the pattern holds for larger N is sadly skipped by almost everyone. Everyone goes for proof by AC approach, but honestly it will help you in solving harder problems if you stop and try to prove your pattern’s correctness. These are the little points where you will apply and improve your math skills - and trust me it does come in handy. Proving whether a solution/pattern solves a problem or fails to solve it is something you will be using everywhere - even in your jobs. So yeah, don’t skip this step

Why filling diagonal with 2N-1 made implementation easier?

Filling diagonal with either 1 or (2N-1), i.e. an extreme value is desired as then we can simply use A[j][i] = A[i][j]+(N-1) without worrying for any corner cases.

Why A_ji = A_ij + N-1 results in Round Robin Scheduling in lower matrix

The upper matrix follows Round Robin Scheduling as we applied the algorithm to it.

Now, copy the corresponding values from upper matrix to lower matrix. This can be done in 2 ways:

Mirror reflecting values along diagonal
Rotating lower matrix until its same in orientation as upper matrix and copying corresponding values.

This lower matrix obeys Round Robin Scheduling because upper matrix obeys it (and lower matrix is a copy of upper matrix).

Adding any constant K to all values does not make any relative difference between these values. Hence, adding N-1 results in lower half having Round robin Scheduling with values in range [N,2N-2]

Setter's Notes

Expected Solution:

It can proven mathematically that the answer only exists for even N and N = 1.
Now to create the matrix for even N, we first put 2N-1 in the diagonal of the matrix.
Now consider a tournament. Every pair of team have to play exactly one match against each other. No team can play two games in a day. It can be proven that the minimum number of days required to finish such tournament is N-1 for even N.
Now we define D[i][j] to be the day team i plays against team j. Now we can use this data to solve our original problem.
Pair the numbers from 1 to 2N-2 (like say (1, 2N-2), (2, 2N-3), ...). Now for each i and j from 1 to n such that i < j, we set ans[i][j] = (the first number in the D[i][j]-th pair) and ans[j][i] = (the second number in the D[i][j]-th pair). It can be seen that this provides a valid solution. Also array D can be built recursively by handling the cases properly.

The question can also be solved in O(N^2) by using following algorithm to schedule matches in a round-robin fashion:

To construct the tournament for N teams, we do as follows :

N is odd : In this case the required number of days is N. To achieve this bound, we can arrange the teams around a circle (with equal distances from adjacent teams). On the i-th iteration we pick the i-th team and draw all the chords (between any two teams) that are perpendicular to the line connecting the i-th team with the center of the circle (it’s easy to see that this actually works).
N is even : In this case the required number of days is actually N-1. We can ignore the last team and then we have N-1 teams (which is odd) and so they have a tournament with N-1 days. Now on the i-th day of that tournoment, we can tell the N-th team to play with whichever team (from the first N-1 ones) that is on a break on that day. It’s easy to see that in an odd tournament every team will be on a break exactly once.

This construction is pretty straightforward and it makes implementation much easier.

??????

Not able to observe patterns? We can do 2 things.

Either you can commit to praying and worshipping the God of Observation day and night.
Or you can try the related problem section.

God of Observation

bigg%20boss