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!
Reminder: Contest starts in 10 hours
Reminder 2: Starts in 20 min
Hope that codechef does not crash like last lunchtime.
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!
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.
Thanks for a nice problem set. The difficulty gradient in Div2 was a bit skewed.
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.
minute ? Submissions got its verdict in secs:)
In tower counting problem do we needed to solve by brute force and calculating the slope ?
Yes..O(n*n) works fine.
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.
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
How to solve D? (The Gifting Problem)
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 \lt 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.
How to solve MINOPS?
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).
Could you help me with my code. I implemented the same.
All the editorials can be found here.
And join us for the live stream tomorrow, where the panelists discuss the problems!