vjvjain0's blog

By vjvjain0, 4 weeks ago, ,

Hi! The motivation for writing this editorial is because lot of programmers were asking for explanation of solution for $D$ in comments and I was also one of them stuck in it. Since official editorial has not been published yet, I have thought of writing one.

First of all I would like to give credit to this comment by Dipjal which was a huge help for me to solve this problem.

Editorial

Let us first be clear with the fact that whenever there is cycle of odd length in a graph it can never be a bipartite graph. I recommend to read more about this if you don't understand before moving ahead. You can read it from here.

Claim: Only elements with same powers of $2$ in $B$ will form a bipartite graph. For example $B=(6,12)$ will not form a bipartite graph while $B=(4,12)$ will form one.

Proof: We can easily check if any two elements can be in $B$ at same time to form a bipartite graph. Let us consider two numbers $a$ and $b$. Then they form a cycle of length $\frac{lcm(a,b)}a$ $+ \frac{lcm(a,b)}b$.

Consider $a=8$ and $b=12$ and see following graph.

Now $\frac{lcm(a,b)}a$ $+ \frac{lcm(a,b)}b$ will be odd when $x\neq y$ where $a=2^x \times c$ and $b=2^y \times d$.

When $x>y$ then $\frac{lcm(a,b)}a$ will be $2^{x-x} \times e$ which is odd and $\frac{lcm(a,b)}b$ will be $2^{x-y} \times f$ which is even.

When $x<y$ then $\frac{lcm(a,b)}a$ will be $2^{y-x} \times e$ which is even and $\frac{lcm(a,b)}b$ will be $2^{y-y} \times f$ which is odd.

Hence, we have proved that only elements with same powers of $2$ in $B$ will form a bipartite graph.

The task is simple now. Just find highest powers of $2$ for every element in $B$. Now we keep majority elements with same power and discard the rest.

Time Complexity: $O(nlog(maxB))$

Suggestions are welcomed :)

PS: At the time of writing this editorial, the official one was already posted.

• +29

 » 4 weeks ago, # |   +1 For example B=(6,12) will not form a bipartite graph while B=(4,8) will form one. How come {4, 8} has same power of 2 in them ?. I think you've mistakenely put this eg.
•  » » 4 weeks ago, # ^ |   0 Thanks. I have updated.
 » 4 weeks ago, # |   0 How do you prove Let us consider two numbers a and b. Then they form a cycle of length lcm(a,b)/a +lcm(a,b)/b.
•  » » 4 weeks ago, # ^ |   0 You can see from the graph above: if one starts from 0, goes to a, 2*a, ... k*a where k = lcm(a,b)/a then actually it comes to lcm(a,b). Similarly if we start from 0 => b => 2*b => ... => m*b with m = lcm(a,b)/b then we come to the same lcm(a,b), so the cycle formed with k+m edges.
 » 3 weeks ago, # | ← Rev. 2 →   0 thanks