We invite you to participate in CodeChef’s May Lunchtime, this Saturday, 30th May, from 7:30 pm to 10:30 pm IST.
3 hours, 5 problems.
We will also be hosting a live problem discussion sessions where our panelist, RestingRajarshi will discuss the Lunchtime problems. Find more details here. Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.
Joining me on the problem setting panel are:
Setters: Vivek Vivek1998299 Chauhan , Raj Khandor , Vinit Vitz Solanki , Shahjalal YouKn0wWho Shohag , Ritesh Gupta
Admin : Teja teja349 Vardhan Reddy
Tester: Radoslav radoslav11 Dimitrov
Editorialist: Taranpreet taran_1407 Singh
Post-Contest Streaming: Rajarshi RestingRajarshi Basu
Statement Verifier: Jakub Xellos Safin
Mandarin Translator: Gedi gediiiiiii Zheng
Vietnamese Translator: Team VNOI
Russian Translator: Fedor Mediocrity Korobeinikov
Bengali Translator: Mohammad solaimanope Solaiman
Hindi Translator: Akash Shrivastava
Prizes:
Top 10 Indian and top 10 Global school students from ranklist will receive certificates and CodeChef laddus, with which they can claim cool CodeChef goodies. Know more here.
Good luck and have fun!
What kind of food will there be for lunch?
You have achieved Komedy.
You will definitely get laddus if you perform good.
Codechef Laddus
beef
Codechef please sort the questions by difficulty, I mean the most difficult one was on top and I spent a good time figuring it out. Meanwhile, checked the dashboard and bam! thousands of submission on first two.
Also, sheesh what is this difficulty curve!?
Just check the questions from the other division before starting to solve..It would give you idea of which questions are easier!
I have to say that the problemset was really nice (atleast IMO).
But in second problem my submission got several TLE beacuse array was of dimension
freq[100][2e5]
(this) and when i changed it tofreq[2e5][100]
(this) it got AC in 0.78s,This is because for each query you need to look at multiple values of freq[][] for at most 3 vertices, so the later version will benefit from the cache.
How to solve Escape One?
Here is the link to the editorial : here
How to solve GCD of the Submasks?
As $$$G(x)$$$ is actually equal to $$$2^k$$$ where $$$k$$$ is the least significant bit of $$$x$$$, we can rewrite the function as follows
In short, we are fixing the value of $G(x)$ and iterating on the values having that fixed value.
We can rewrite the equation as
So how to solve this? Let's split the sum into two parts.
Now to solve the left part we should notice that if we consider the power sum as a polynomial over $i$ then it will have degree $$$(2^k + 1)$$$. So we can use Lagrange interpolation to solve this part. And for the right part, we can use brute force.
To solve it for multiple queries notice that the polynomials for different $$$k$$$ don't change. So store the first $$$2^k+1$$$ values for each k up to $$$p$$$ and for each query use interpolation to find the left part. Total complexity will be $$$O(\sum\limits_{i=0}^{p}{2^i}) = O(2^{p+1})$$$. Notice that we are computing the Lagrange interpolation without having any $$$O(log\,mod)$$$ factor.
To solve the right part we can precompute the polynomial values for first $$$O(\frac{n-2^k}{2^{k+1}})$$$ values for each k from $$$p$$$ to $$$30$$$ and for each query use this information in $$$O(1)$$$.
The precomputation can be done in $$$O(\sum\limits_{k=p+1}^{30}{\frac{2^{30}}{2^{k+1}}}) = O(2^{29-p})$$$. Note that here we are speeding up by $$$O(log\,mod)$$$ factor using the following property: $$$O(z^{2^{k+1}} = z^{2^k}*z^{2^k})$$$. Even with the log factor we can AC this problem though.
So total complexity will be $$$O(2^{29-p} + T*2^{p+1})$$$. If we set the value of $$$p$$$ to $$$5$$$ then we will get a solution which is enough fast to get AC.
`
Hints for Absolute Min Max ?
Let's consider the fruitful subarrays starting at L.
There are 2 cases : either A[L] is maximum in the subarray or it's minimum in the subarray.
Solve both cases independently.
You can use stack to find next greater/next smaller element for every element.
Case 1: These subarrays must end before K, if A[K] is the next greater element from A[L]. To calculate these, you can make sparse tables over next smaller element array.
Case 2 can be solved similarly.
Don't forget to handle the case of duplicates!
Editorials out! :)
The editorials for all problems are posted and can be accessed via https://discuss.codechef.com/tag/ltime84
Hope you guys had a great contest!