vjvjain0's blog

By vjvjain0, 3 months 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

By vjvjain0, history, 13 months ago, ,

Hello Codeforces Community!

ENIGMA Programming Club, ABESEC are here to present coding event Battle of Brains. The goal is to strengthen the problem-solving skills and logical thinking of students. The Club is organizing its first Coding Competition:

Battle Of Brains

Gear up to rack your brains and enhance your skills in this battle of brains!!

So hurry and register yourself and set the mood to code your hearts out!

CONTEST DETAILS:

The contest will consist of two rounds — a qualifier round and a final round.

A team can be of at max 2 participants.

ONLINE QUALIFICATION ROUND

DATE and TIME: 1st November at 8:30PM IST

DURATION: 3:00 Hrs

PLATFORM: CODECHEF

First Register here: https://www.codechef.com/BOBQ2018

Then Here: https://goo.gl/forms/lxd62qyPhk6P3sYe2

Top 50 teams will be qualified for the onsite round. The maximum number of teams that will be selected from a college would be 5. Only those teams who fill the Google Form would be considered for Round 2.

Happy Coding!

• +14

By vjvjain0, 17 months ago, ,

Hey guys! I was doing a question and got an idea of this interesting question.

You are given an n size array a. The ith element of array a[i] is the frequency of the element. You are given q queries which has inputs left limit l and right limit r. You have to tell the median for the range.

1<=n<=10^6
1<=q<=10^5
1<=l<=n
1<=r<=n

Example:

5 2
4 7 9 1 2
1 2
3 5

Output:

2
3

Share your approaches in the comments. I don't if this is already a question on some online judge.