vjvjain0's blog

By vjvjain0, 5 years 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 code_hard123 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

| Write comment?
»
5 years 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.

»
5 years 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.

  • »
    »
    5 years 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.

»
4 years 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?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I have thought about this. This is what I feel. Please excuse me for my mathematical expression. Above method deals only with such cycles where 2 numbers are involved. However, the answer that we have got by consideration of those cycles alone can be used to see that it is going to be same for other cycle. Assume a cycle . We will have a common element. Let it be (2^k)*(u1+u2+u3+.. ui). and by the other way (2^k)*(v1+v2+v3+... vj). Here, we know all u's are odd and all v's are odd. But u1+u2+u3+...ui = v1+v2+v3+..vj. However, as parity is same on both sides i and j,number of u's and v's are also going to have same parity . Therefore, length of cycle (i+j) will be even.