Lewin's blog

Codechef March Cook-Off
By Lewin, history, 8 years ago, In English

Hello everyone!

I’d like you to invite for CodeChef March Cook-Off that will start at 21:30 IST of 19-th March 2017 (check your time zone here) and will last 2.5 hours.

I am the author of problems and editorials, while Errichto is the tester. There are also some other people who helped with translations and miscellaneous issues who I will fill in later.

There is no registration required, anybody with a CodeChef handle can participate. Top participants can win CodeChef laddus (details on the contest page).

You will be provided 5 problems. There's one problem that shows a style of problems I would like to see more in competitions. Let me know what your thoughts are after the contest.

Hope to see you all on the leaderboard!

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

Comments Comments (27)
| Write comment?
»
8 years ago, # |
  Vote: I like it -25 Vote: I do not like it

Why there is no such type of blog on codechef discuss forum as there was for for the past 2 contests, but there is a blog here on codeforces.

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

    Ok now there is an announcement.

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

remainder: the contest will start in less than 4 hours

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

Why is it so hard ? xD

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

so tough !!!! Even Nicky Minaj is finding it difficult :p :p

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

Why are we randomly extending the contest by 15min?

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

Errichto Why was i getting WA on correct solution for 3rd problem RAINBOW? Hope there's better testing next time :p

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

How to solve INCXOR? For n = 2, I was able to brute force that answer is 230·(231 - LSB(max) + 1) where LSB(max) = 2 power log2(maximum value). Is this extendable?

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

    You can use digit DP using the state (index, b_mask, xor_mask). index ranges from 30 to 0 (inclusive). b_mask and xor_mask are masks of size n-1. We assign the bits of b in levels, level 30 to level 0. The ith bit in b_mask is set if b[i] < b[i+1] using some previously assigned bits in indices [idx+1, 30]. For each level, just check all possibilities of assigning bits to that level in b[].

    Code

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

Very sad story, I ranked 10 in Rest of World when the original timer ended. I was very happy that I can gain some more laddus and get a step closer to have the new cool prizes.

After eating my cup noodles and got back to my computer, I found that my rank dropped to 11. When I first noticed that the contest was extended by 15 miuntes, only 2 minutes left and nothing I could do.

Goodbye my laddus :(

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

    "March Cook-Off 2017 has been made unrated." You are saved. :)

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

      Whatever it is rated or not, my laddus are gone :\ (unless those ranked top 10 when original timer ended are also rewarded)

      And personally, I would like this round to be rated as I am quite sure that my rating will increase :D

      Anyway, it is still fair for the round to be unrated as I believe many contestants are affected due to the data issue.

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

Can someone tell me the intuition behind the formula given in the Yet Another Card Game Editorial

p * (r / (r+b)) + (r+b-p) * (b / (r+b))

Also how to come up with above formulas ?

Can someone share his/her approach in detail ?

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

    The intuition is that all strategies will lead to the same expected value. Intuitively, the cards are played randomly, and the moves you have are fixed, so there's nothing you can really do to "beat" the randomness there in this case.

    We can get the final expected value by linearity of expectation. For a red token, it has probability r/(r+b) of getting matched with a red card. For a blue token, it has probability b/(r+b) of getting matched with a blue card. So, the final formula can be derived from an application of linearity of expectation.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it +4 Vote: I do not like it

      I really can't understand when cards are getting discarded, how we are using p times r/(r+b). I read it on codechef too still can't understand. Please can you elaborate a bit.

      We can get the final expected value by linearity of expectation. For a red token, it has probability r/(r+b) of getting matched with a red card. For a blue token, it has probability b/(r+b) of getting matched with a blue card. So, the final formula can be derived from an application of linearity of expectation.

      Won't r and b change after every extraction of token?

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

        The probablity that a card is matched with token of same color is not dependent on any one case. It's calculated as follows. Let us denote tokens by T1, T2... Tr + b where tokens T1 to Tr are red and Tr + 1 to Tr + b are blue tokens. Now for a token Ti where 1 ≤ i ≤ r, we have to find the probablity that it's matched with a red card. If we consider all possible ways to pick the cards, it will be , let us denote it by x. Now lets fix at any 1 ≤ i ≤ r a red card which means that at ith turn we'll pick a red card. Considering this the total number of cases when ith turn will be a red card are , let us denote it by y. Now obviously, the probablity that ith card is a red card is which you can simplify is nothing but and since we have proven it for a general 1 ≤ i ≤ r. The expectation is therefore . You can prove similarly for blue cards too.

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

    First, let us denote random variable X = Total Score at the end of all the turns. Now X = where Xi denotes whether the token at ith turn matched with a card or not. Now since expectation value follows linearity, therefore we can apply E(X) = . So, how to calculate E(Xi)? We know that it doesn't matter in this that Xi is dependent on Xj or not. So we can simply write E(Xi) as . Now, to sum over all Xi, we can see that first term will only appear when for p red tokens and second term will appear for r + b - p blue tokens, hence the sum over all Xi's is .

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

    Alternatively use a greedy approach. At each step,take the token of that color which has more coins. After taking that token,reduce the expected no of red and blue coins with probability of getting that coin.

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

I am sorry for invalid tests (c[i][j] = 0) in RAINBOW and thus extending the contest. We made some change in constraints there one day before the contest and I didn't modify my validator (program with asserts) — I will try not to let it happen again. And thanks for nice problems, Lewin!

If you think problems were hard, I encourage you to upsolve them. Upsolving is even more valuable for you skills than participating in contests itself.

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

Can someone formally prove the correctness of the solution for Yet Another Card Game.

Editorial Link

I am still not getting the intuition that why should every strategy be optimal?

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

    If at every move , if we take only red token ,then expected points are equal to N.
    If at every move , if we take only blue token ,then expected points are also equal to N.
    This means , at any move, we can either chose red token or blue token.

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

So is it unrated or when is rating going to be updated?

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

    "March Cook-Off 2017 has been made unrated."

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

Has anyone received their laddus points?

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

    It takes time for rating updates on CodeChef. For example, ratings for March long challenge which ended on 13th March have not been updated yet. So, laddu points are given only after rating update.

    → Reply