imAnik's blog

Invitation to CodeChef July Cook-Off 2019
By imAnik, 5 years ago, In English

Greetings Codeforces community!

CodeChef’s July Cook-Off is here! That means two and a half hours of engaging problems designed specifically to serve your intellectual appetite. So, get ready to code and compete! Further, all our problem statements will be available in English, Hindi, Bengali, Russian, Mandarin and Vietnamese.

Additionally, if you have some original and interesting problem ideas and want them to be used in CodeChef's contests, you can share them with CodeChef admins here.

Hoping to see you join your fellow coders and participate in the contest. Joining me on the problem setting panel are:

I hope you will enjoy solving them. Please give your feedback on the problem set in the comments below, after the contest.

Contest Details:

Time: 21st July 2019 (2130 hrs) to 22nd July 2019 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Contest link: https://www.codechef.com/COOK108

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
  • +78
  • Vote: I do not like it

Comments Comments (26)
| Write comment?
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

expecting nice questions from this contest!!

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

Waiting.....

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

25 minutes to go!

→ Reply
»
5 years ago, # |
← Rev. 8   Vote: I like it -40 Vote: I do not like it

This has become commonplace at CodeChef now. Almost every other short contest has this sort of variation. Current scenario * 245 ACs * 32 ACs * 21 ACs * 5 ACs * 3 ACs

It's really sad :/-

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

    Has become? I don't remember a time when this was not the norm at CodeChef.

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

How to solve Expected Product problem?

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

    Without the MODULO N thing, the answer would be (sum(arr)/n)^k (Handle the MODULO 1e9 + 7)

    Because of the MODULO our numerator would change

    Consider this case: n = 3, k = 2 ,arr = [a,b,c]

    k = 0 numerator = 1%MOD

    k = 1 numerator = ((1*a)%n + (1*b)%n + (1*c)%n)%MOD

    k = 2 numerator = ((a*a)%n + (b*b)%n + (c*c)%n + 2*(a*b)%n + 2*(b*c)%n + 2(a*c)%n )%MOD

    Basically it is a variant of polynomial multiplication (exponentiation) Now while implementing this you need to consider remainder modulo N as the exponent and its number of occurrences as the coefficient.

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

    Let's solve the counting version of this problem, instead of the expectation version.
    For each z in [0,N-1], we want to count the number of way the score can equal z.

    Think what you could do if K was 2?
    Can you come up with a dp solution in O(N^2)? Something like this : 

    for each i,j < N   
ways [2] [ (i * j) % N ] += ways [1] [i] * ways[1] [j]

Here ways [x] [y] = number of way the score can equal y after first x moves.

    Continuing this dp, you definitely can solve the original problem in O(N^2 * K).
    But think carefully that you almost repeat the same thing in every step and actually you can do something like binary exponentiation here. Actually you can thus calculate ways[4] from ways[2], ways[8] from ways[4] and so on.

    I think you will get the idea if you think a bit.

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

Please add problems to practice.

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

How to solve the Two Variables Problem in Div 2 ?

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

    for me, I do simulation on x and y until 2e9 (I do it on precompute) to get all valid x, then it turns out that it only shows 61 x's, so just precompute it, save it in an array, then do binary search to get answer

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

      I Did not get it completely !

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

        In simple words, you need to do it greedily. I can explain it through an example. Consider X_f = 9

        1. The smallest number whose larger than Y=0 -> 1, add it 1*1 to Y, assign X=1
        2. The smallest number whose larger than Y=1 -> 2, add it 2*2 to Y, assign X=2
        3. The smallest number whose larger than Y=5 -> 3, add it 3*3 to Y, assign X=3
        4. The smallest number whose larger than Y=14 -> 4, add it 4*4 to Y, assign X=4
        5. The smallest number whose larger than Y=30 -> 6, add it 6*6 to Y, assign X=6
        6. The smallest number whose larger than Y=66 -> 9, add it 9*9 to Y, assign X=9

          6 steps.

          Now it is easy to see that Y is increasing exponentially, you can do a formal proof as an exercise here. But to see it quickly, you can observe the sums and first see that for the first few values, Y grows as N^3. Later, this growth only increases. Now if you find all these values till you get 10^9 (the maximum possible X_f), you will see that you have a very small number of iterations is 61 as dickynovanto1103 points out. Now you can store these and just binary search. My solution passed even without storing these.
        → Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Any solution for War in Treeland Again using DP or Centroid Decomposition ?

The problem was similar to 990G - GCD Counting, but my DP solution that solved this problem got a TLE.

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

Hi...I think this link https://discuss.codechef.com/tags/cook108/ is not accesible...can you please help fix it?

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

    Its because the editorial has not beeen published yet.Hopefully I think it will be published in few hours.

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

wrt EXPTPROD problem:

I may be in a completely incorrect direction but can someone point out why:

S0 = Random variable for initial value of S
Si = Random variable for value of S after i operations
A = Random variable representing result of picking a number in sequence a1...an uniformly randomly.

S1 = S0*A           =>  E[S1] = E[S0] * E[A] (since A & S0 are independent);
S2 = S1*A = S0*A^2  =>  E[S2] = E[S1] * E[A] = E[A]^2 (since A in 2nd move is independent of S1);
....and so on

Sk = S0 * A^k       => E[Sk] = E[A]^k

Hence, expected value of S could be computed as expected value of sequence A raised to k.

But as you have guessed correctly, this approach does not give an AC xD

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

    Yes, your idea is correct if the move is : S = S * X
    But in this problem, we had : S = (S * X) % n
    I think that is what you are missing here.

    → Reply