Greetings Codeforces community! We welcome programmers all over the world to participate in CodeChef’s May Cook-Off sponsored by ShareChat. The contest will feature brand new and exciting problems for you to sharpen your skills. Problems statements will also be available in multiple languages. Participation could also bring you closer to work opportunities at ShareChat — India’s fastest growing social network. Job opportunities are open to programmers across the world and internship opportunities are exclusively aimed at final year B.Tech students who have already been placed and looking forward to gaining startup experience. Visit the contest page for more details. I hope you will join your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:

Setters: solaimanope (Mohammad Solaiman), Anachor (Pritom Kundu), Erfan.aa (Erfan Alimohammadi)

Admin: kingofnumbers (Hasan Jaddouh)

Tester and Editorialist: teja349 (Teja Vardhan Reddy)

Statement Verifier: Xellos (Jakub Safin)

Mandarin Translator: huzecong (Hu Zecong)

Vietnamese Translator: Team VNOI

Russian Translator: Fedosik (Fedor Korobeinikov)

Bengali Translator: solaimanope (Mohammad Solaiman)

Hindi Translator: Akash Shrivastava

#### Contest Details:

**Start Date & Time:**19th May 2019 (2130 hrs) to 20th May 2019 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone**Contest link:**https://www.codechef.com/COOK106**Registration:**You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.**Prizes:**Top 10 performers in Global and top 10 performers in Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://discuss.codechef.com/t/how-do-i-win-a-codechef-goodie/7344 (For those who have not yet got their previous winning, please send an email to winners@codechef.com)

Good Luck!

Hope to see you participating!!

Happy Programming!!

Clashing with Hourstorm 11

HourStorm is tomorrow , Cook off is today!

Almost TLE :O 7.99 out of 8s

Does Problem Bitsetbaba and Power Grid based on Gaussian Elimination to find the subset with given xor?

Gaussian Elimination for finding rank of binary matrix of all numbers as rows.

In Bitsetbaba and Power Grid, why is the answer not number of elements divided by number of unique poisitive elements

For any positive number, the numbers will make pairs. So after one number (say x) we get pairs say (a, b), (c, d), (e, f), ...

Now for second number (say y) if we have another pairing. If it a pairs up with c then a ^ c = y Claim is that b ^ d = y. a ^ b = x and c ^ d = x so a ^ b ^ c ^ d = 0. Now a ^ c = y then b ^ d = y.

So with every unique number the number of component gets divided by 2.

I have only read first sentence.

If you something like $$$x=[1,2,3]$$$, you can obtain only numbers smaller than $$$< 4$$$. So answer is divided by $$$4$$$.

I think the component gets divided by 2 only when the current number inserted lets say a[i] is not the xor of the subset of already inserted i-1 elements otherwise we will get an edge which will be in the same component. Correct me If I am wrong

So If I am right how can we check whether the number we inserted is the xor of subset of already inserted elements.

what will be the approach for Expected xor?

Maintain the probabilities, that number will have bit i.

Can you please elaborate a little?

Let X be a random variable denoting the resultant beauty of the exhibition.

Then X can be written as: $$$X = 2^{31} * X_{31} + 2^{30} * X_{30} + ... + 2^1 * X_1 + 2^0 * X_0$$$, where $$$X_i$$$ denotes the $$$i$$$-th bit of X.

Now, $$$E(X) = 2^{31} * E(X_{31}) + 2^{30} * E(X_{30}) + ... + 2^1 * E(X_1) + 2^0 * E(X_0)$$$, by linearity of expectation.

and also $$$E(i)$$$ = Probability of the $$$i$$$-th bit being equal to 1. To compute $$$E(i)$$$, you may write a simple $$$dp$$$ as $$$dp[i][j][k]$$$ which is the probability of obtaining a subset of the first $$$j$$$ numbers where the $$$i$$$-th bit is having a value equal to $$$k (k = 0/1)$$$.

and $$$E(i) = dp[i][n][1]$$$.

when will the MOSS of the contest get over

Does anyone have a solution to Nearest Color?

Hi. All the editorials are published here :).

Amazing tests in BICLIQUE

Solution: lol lol lol

I did note that problems with YES/NO answers need a LOT of tests to not be very weak. *shrugs*

Could someone explain GCDSET? Isn't it just counting the number of multiples in the range $$$[l,r]$$$ ?

Didnt solve it . But what it seemed to me was — divide l and r by the desired gcd. Suppose we get l' and r'. Now there is a set made out of numbers between l' and r' . These numbers must be mutually co prime. We have to report the maximum number of elements in this set.

There is one corner case. What if there is only one multiple in range [l,r], then answer maybe 1 or 0 depends on this multiple.