Блог пользователя Anachor

Автор Anachor, история, 5 лет назад, По-английски

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 [email protected])

Good Luck!

Hope to see you participating!!

Happy Programming!!

  • Проголосовать: нравится
  • +50
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Clashing with Hourstorm 11

»
5 лет назад, # |
Rev. 5   Проголосовать: нравится +21 Проголосовать: не нравится

Almost TLE :O 7.99 out of 8s

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

what will be the approach for Expected xor?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Maintain the probabilities, that number will have bit i.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you please elaborate a little?

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

when will the MOSS of the contest get over

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Does anyone have a solution to Nearest Color?

»
5 лет назад, # |
  Проголосовать: нравится +64 Проголосовать: не нравится

Amazing tests in BICLIQUE

Solution: lol lol lol

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.