Anachor's blog

Invitation to CodeChef May Cook-Off 2019 sponsored by ShareChat!
By Anachor, history, 6 years ago, In English

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: Mediocrity (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!!

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Clashing with Hourstorm 11

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    HourStorm is tomorrow , Cook off is today!

    → Reply
»
6 years ago, # |
← Rev. 5   Vote: I like it +21 Vote: I do not like it

Almost TLE :O 7.99 out of 8s

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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$$$.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

what will be the approach for Expected xor?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maintain the probabilities, that number will have bit i.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please elaborate a little?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        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]$$$.

        → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

when will the MOSS of the contest get over

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone have a solution to Nearest Color?

→ Reply
»
6 years ago, # |
  Vote: I like it +64 Vote: I do not like it

Amazing tests in BICLIQUE

Solution: lol lol lol

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply