NOTE- This editorial consists of images to assist in clarification. Its urged to read it when you have a good internet speed so that images load correctly. 
PROBLEM LINK:
Setter- Misha Chorniy
Tester-
Editorialist- Abhishek Pandey
DIFFICULTY
EASY-MEDIUM
PRE-REQUISITES
Looping, Logical Thinking.
(Knowing about Bit Manipulation will help, but not necessary. However, please have a look at binary representation of numbers and properties of â&â operator before reading the editorial)
PROBLEM:
There are N people who will form 2 groups of N/2 each per discussion. We have to calculate minimum number of discussion, as well as format of discussion such that every person is able to discuss with every other person.
QUICK EXPLANATION:
Thinking intuitively, we see that the number of games needed is Games=\lceil{log_2N}\rceil. Checking out binary form of numbers from 0 to {2}^{Games}-1 , we see that each bit is "0" N/2 times and "1" N/2 times. We pair the bits with same value in same group for that particular game, then move on to next bit. In case N is not a power of 2, we consider bit values such that number of times a bit is 0 or 1 is exactly N/2.
EXPLANATION:
For convenience of explanation, I have divided explanation into 3 parts. One for finding the number of discussions and 2 on construction of discussions.
Number of Discussions-
The very first instinct of many people was to conclude N/2 discussions are needed, by exchanging 1 person per discussion. However, this is wrong. I want you to think intuitively for a minute. When exchanging people one by one, people in a group are able to exchange views with atmost 1 new person. However, what if instead of 1 person, we take and mix half of the groups at once? And then in next turn, mix half of the new group such that people who havent exchanged views lie in different groups? You can prove that number of views exchanged per discussion is more this way. Can you see the logarithmic intuition now? Formal proof is in construction, discussed below.
Construction of games when N={2}^{K}-
We have to construct discussions in such a way so every person is able to exchange views with every other person. Let me refer to this as âHomogenous mixingâ of people. At first, it may seem puzzling to invent this, but the main idea is right under our noses! Its one of the problems where thinking in terms of binary makes things really easy.
Think in terms of binary, and write down numbers from 0 to N-1 in binary form. The intuition of writing from 0 to N-1 instead of 1 to N is that, numbers from 0 to N-1 can be represented in K bits, while in case of latter, N will need have 1 additional bit. You will notice that each bit âiâ is '0' N/2 times, and is '1' N/2 times. Is this just a co-incidence?
No! This property that a bit is 0 and 1 for N/2 times allows us to solve the question using this strategy! On writing numbers in binary form, you ought to see that âHomogenous mixingâ is a natural property of binary numbers. Meaning, for i'th game, if we group people with same i'th bit together, then we can easily achieve âHomogenous mixingâ after playing K games. And K is nothing but log_2N !! Refer to image below for greater clarity.
When N is not a power of 2-
Note that, the biggest setback here is that the property that âAny bit âiâ is 0 and 1 for N/2 times eachâ no longer holds! There is a two-fold problem here first that our number of games, i.e. log_2N is a decimal and second is regarding how to construct games.
Number of discussions-
First, we must check for number of games. Lets take N=6. Its obvious that N=6 cannot be done is lesser games than N=4, and definitely wont need more games than N=8. This means N=6 needs games equal to either N=4 or N=8. Obviously, by sample input/output, we can see that it needs games equal to N=8. Hence, we can modify our formula for number of games to Games=\lceil{log_2N}\rceil.
Construction of games-
We must do something so that the property of each bit being 0 and 1 for N/2 times each holds again. We can do so by ignoring some numbers. Let me call the ignored numbers as âDummy valuesâ.
Write the numbers from 0 to {2}^{Games}-1 in binary. Let K={2}^{Games}-N. Its easily seen that out of {2}^{Games} numbers, we are ignoring last K numbers. Ignoring all K numbers from only one side is reason why our property of N/2 zeroes and ones isnât holding. Notice one property of numbers in binary form. If X'th number (from start) has i'th bit 0, then X'th number from end has i'th bit 1 (and vice-versa). We can use this to make our property hold! If instead of ignoring all K numbers from end, we ignore first K/2 and last K/2 numbers, our property will hold. Check the image below for clarity, and Chef Vijjuâs corner for further discussion.
Another example where N=10.
EDITORIALISTâS SOLUTION:
Solution1- This one follows the approach of Editorial.
Solution2- Check out Chef Vijjuâs corner, 2a. This one is based on dummy numbers, but does not use bits.
Solution3- One of my favorite solutions, another easy way to achieve homogenous mixing. 2b at CVC 
Solution4- The simplest method to achieve homogenous mixing via odd even concept. Refer to 2c of Chef Vijjuâs corner.
TimeComplexity=O(Nlog_2N)
CHEF VIJJUâS CORNER
Chef Vijju is back, and with loads of lip smacking alternatives and mouth watering questions as usual.
1.Firstly clarifying why ignoring first K/2 and last K/2 numbers worked. The trick is that, if we ignore X'th number from start, then X'th number from end is causing excess of complementary bits at each index i, creating a imbalance. However, if we ignore both of them, altogether equal number of 0 and 1 are being ignored. Eg, take K=2 and N=6. Refer to my uploaded image, you will see that K/2=1, and first bit from start is 000 and first bit from end is 111. On ignoring any of these, there is an excess of the complementary bit, but on ignoring both, the equality is restored. Work out some examples if its still not clear, it will make sense if you work hard enough.
2.A very common question which I think must be going on in many peopleâs mind right now is that, well, its certainly not a bed of roses to see the binary perception of the problem. I can understand if many of you find it a bit hard to digest, or feel that its not so intuitive to think of altogether. After all, not only you have to imagine numbers in binary form, but that too from 0 to$N-1$ instead of 1 to N!
Not so easy to think if you are solving such a problem for first time. Even I had problem getting grasp of setterâs approach for the first time.
But it turns out, the binary number approach which I discussed in editorial is just one of the many approaches to achieve Homogenous mixing. After some twisted thinking and manipulation here and there (:D), I was able to come across some easy solutions to achieve homogenous mixing easily. From most difficult to most easiest, they are-
a.Refer to solution 2. In this, we make an array, with values from [1,N].
If N={2}^{K}, then life is simple. We make a window of length=N/2. People in same window are in same group, and size of window halves after every iteration. Lets say N=8. For first iteration, window length is 4, and groups are [(1,2,3,4),(5,6,7,8)].
For second iteration, window length=2, and groups are [(1,2),(3,4),(5,6),(7,8)]. There are more than 2 groups now. We will converge groups at odd positions, and groups at even positions together. Meaning (1,2) and (5,6) are combined together, and (3,4) and (7,8) are combined together for this round.
In final round, window length=1, and groups are [(1),(2),(3),(4),(5),(6),(7),(8)]. Groups at odd and even positions are combined, so we get 2 groups as (1,3,5,7) and (2,4,6,8). You will see that the grouping is happening exactly as if we are considering the binary approach for the problem!! (And this is the proof of correctness of this approach).
If N\ne{2}^{K}, we are using dummy values. Number of games is Games=\lceil{log_2N}\rceil. Lets take N=6 for example purposes. Number of games to be played is 3. We will make an array from [1,8], making sure that dummy numbers are equally distributed on both sides. Dummy numbers this time are 7 and 8. You can put either of them on any side. Lets say our array is [7,1,2,3,4,5,6,8].
Notice the equal distribution of dummy numbers. Dummy numbers will be considered by window in grouping, but they wont be printed. Lets see how our code works for this case. For first iteration, window length is 8/2=4. Groups for first iteration are [(7,1,2,3),(4,5,6,8)]. We have made an if statement, such that it will print a number only if its {\le}N.
So our code will print only (1,2,3) from first and (4,5,6) from second grup. Second iteration, groups formed are [(7,1),(2,3),(4,5),(6,8)]. After converging groups at odd and even index, they are (7,1,4,5) and (2,3,6,8). Our code hence prints (1,4,5) from first group and (2,3,6) from second group. Similarly third iteration happens.
This approach is also quite difficult, and the only reason one would prefer this over Binary approach is if he failed to think in terms of Binary, or really hates Binary and bits (Lol!). But nevertheless, some people did use this approach.
b. This one is pretty simple. In this one, we print the i'th and N/2+i'th term together and then club them together in copy array (meaning, these terms are adjacent in copy array). Then we overwrrite original array by copy array. This requires NO changes, we are NOT concerned if N is a power of 2 or not. The same method works for both cases, and hence this method is close
to my heart. However, N MUST be even. Seeing example, take N=6. Our array is [1,2,3,4,5,6]. We run a loop from 0 to N/2, and print the i'th and N/2+i'th term together. Meaning, for i=0, we print term at index 0 and 3+0=3, i.e. numbers 1 and 4. After loop finishes, we have printed
1,4,2,5,3,6 on screen. Our copy array is now [1,4,2,5,3,6] as well. Now we overwrrite our original array by copy array. We print 1,5,4,3,2,6 next term, and thats our new array. In final turn, we print 1,3,5,2,4,6 and we can see that we have achieved homogenous mixing. But what is the proof of its correctness? Will you guys work it out?
i) Give a proof of correctness of method in 2b. Describe the steps, your assumptions and intuition in detail. Decent answers will, as usual, get 10-25 points .
c. This approach is same as approach in b. , except that its a bit more simpler! We just club the terms at odd and even indexs together! Meaning, for N=6 and our array Arr[]=[1,2,3,4,5,6] , we print terms at odd indexes first, and then terms at even indexes. The output for first iteration is 1,3,5,2,4,6 , and this is the array Arr for next iteration. The next
terms printed are 1,5,4,3,2,6. I think you guys can work out the final iteration. What is the proof of its correctness? Its best if you guys work it out as well, because I dont want to spoonfeed you guys and hence spoil you!!
i) Give the proof of correctness of method in 2c. Describe your steps, assumptions and intuitions in detail. Decent answer(s) will be awarded 10-25 points
3.Well, from very start of this editorial I am referring to âA person being able to discuss with every other personâ as concept of âhomogenous mixingâ Do you know why? No, its not just because I love giving random names to concepts, but this naming allows me to do one thing. See below and find out wink 
-
i) What is this concept of âHomogenous mixingâ actually? Is it an algorithm, working, or a method? Does it even exist at all? Again, 10-25 points to anybody who is able to come up with decent explanations
ii) I have mentioned 3 extra solutions apart from the one based on editorial. Are their working essentially same? Are they nothing but different implementations of the Binary number concept which I described in editorial? Or are they something else? Its your turn to find out if they are just âMirror imagesâ or an opening to a whole new world of implementation
and algorithm!!
iii) How would you deal with the question if N can take odd values as well? What effect would it have on number of games and the construction? Will Binary approach still work? Why/Why not?
4.A problem on same concept (i.e. Binary) is here . You will love this problem if you think in terms of binary and powers of 2.