vjvjain0's blog

By vjvjain0, 3 months ago, In English,

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

Problem: Link

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.

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.

 
 
 
 
  • Vote: I like it
  • +29
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

thanks

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Excellent article,but what about cycles formed from more than 2 numbers?for example: 1 3 6 1,it is formed due to numbers 2,3,5. In this case,the formula for length of cycle =lcm(a,b)/a+lcm(a,b)/b wont be valid right?