smartnj's blog

CodeChef April Cook-Off Rescheduled
By smartnj, 5 years ago, In English

Greetings to you all!

Note that CodeChef’s April Cook-Off is on a Monday this month instead of the usual Sunday. Also, this Cook-Off will use new cloud-based checkers, about which you can read here.

I take the opportunity to invite you to this 2.5-hour short contest. You’ll have 5 problems to solve and the best performers will be treated with Laddus redeemable for cool CodeChef goodies!

We will also be hosting a live problem discussion session on Tuesday (21st) from 5pm to 7pm IST on Zoom and Youtube Live, where our panelists, teja349 (Teja Vardhan Reddy) and RestingRajarshi (Rajarshi Basu) will discuss the Cook-Off problems. If you’re interested only in the hardest couple of problems, join in at 6pm. You can book your spot here.

The problem statements of the contest will be available in English, Hindi, Bengali, Russian, Mandarin, and Vietnamese.

The problem setting panel :

  • Setters: FastestFinger (Ayush Ranjan), smartnj (Naman Jain)
  • Tester: raja1999 (Raja Vardhan Reddy)
  • Editorialist: RestingRajarshi (Rajarshi Basu)
  • Statement Verifier: Xellos (Jakub Safin)
  • Admin: teja349 (Teja Vardhan Reddy)
  • Russian Translator: Mediocrity (Fedor Korobeinikov)
  • Vietnamese Translator: Team VNOI
  • Bengali Translator: solaimanope (Mohammad Solaiman)
  • Hindi Translator: Akash Shrivastava
  • Mandarin Translator: Qingchuan Zhang

Contest Details:

  • Time: 20th April 2020 (21:30 hrs) to 21st April (00:00hrs). (Indian Standard Time: +5:30 GMT) — Check your timezone.
  • Contest link: http://www.codechef.com/COOK117
  • 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 Indian and top 10 Global participants will receive CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here.

Good luck and have fun!

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

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

Reminder: Contest starts in 10 hours

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

Hope that codechef does not crash like last lunchtime.

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

    We're confident that the submission queue will not be a bottleneck like last Lunchtime, and we believe we've also improved the servers enough for it to not be an issue. Fingers crossed!

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

      Why doesn't codechef too keep a register option for contests to keep a track how many people are going to participate.This helps us too.

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

Thanks for a nice problem set. The difficulty gradient in Div2 was a bit skewed.

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

Wonderful improvement in servers !! The submission result was ready in less than a minute..Codechef does deserve an appreciation for this quick improvement after what happened in last lunchtime.

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

    minute ? Submissions got its verdict in secs:)

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

In tower counting problem do we needed to solve by brute force and calculating the slope ?

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

    Yes..O(n*n) works fine.

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

      Did anyones O(n^2) got AC ? Reason being O(n^2) can reach till 10^8 and i thought it might give TLE since we additional operational also in a loop.

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

        Actually, $$$O(n^2)$$$ did not reach $$$10^8$$$.

        According to the constraints, $$$\sum$$$$$$N$$$ does not exceed $$$20,000$$$ but $$$N$$$ in any test case does not exceed $$$2,000$$$. This implies there can be at most $$$10$$$ test cases having $$$N=2000$$$, which ends up giving a worst case running complexity of $$$10*2000^2$$$ ~ $$$4*10^7$$$.

        My $$$O(n^2)$$$ solution

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

How to solve D? (The Gifting Problem)

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

    First notice that $$$G(i,j)=i\oplus j$$$ (xor of $$$i$$$ and $$$j$$$). So if the initial array was $$$a$$$ then after a year the new array $$$b$$$ will satisfy $$$b_i = \displaystyle\sum_{j=0}^{N-1} \left(i\oplus j\right)a_j$$$. A naive way to obtain $$$b$$$ would be to add $$$ia_j$$$ to $$$b_{i\oplus j}$$$ for each $$$0\leq i,j < N$$$. This is readily an instance of xor convolution: the process is the same as multiplying two polynomials $$$P(x)=\displaystyle\sum_{i=0}^{N-1} ix^i$$$ and $$$Q(x)=\displaystyle\sum_{i=0}^{N-1} a_i x^i$$$ with $$$x^i \cdot x^j$$$ defined to be $$$x^{i\oplus j}$$$. So the final array is simply the coefficients of $$$P(x)^KQ(x)$$$. You can efficiently compute the power and product applying fast Walsh-Hadamard transform.

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

How to solve MINOPS?

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

    let x be the leftmost position such that s[x]!=r[x] , let y be the right most position such that s[y]!=r[y]. Then we need to solve for sub array [x,y] . Now answer cannot be greater than y-x+1 . Now create an array A which stores length of all continuous segments which are same in both arrays[x,y].sort the array in descending order. now the answer is ans = min(ans,2*(ans-A[0]),3*(ans-A[0]-A[1]),4*(ans-A[0]-A[1]-A[2])....,) .Because when we skip a segment which is same in both array , we increase number of operations by 1 . Also if we are skipping we will always skip the largest one. complexity O(n).

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

All the editorials can be found here.

And join us for the live stream tomorrow, where the panelists discuss the problems!

→ Reply