radoslav11's blog

Invitation to CodeChef May Lunchtime 2020
By radoslav11, history, 4 years ago, In English

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!

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

Comments Comments (17)
| Write comment?
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

What kind of food will there be for lunch?

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

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!?

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

    Just check the questions from the other division before starting to solve..It would give you idea of which questions are easier!

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

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 to freq[2e5][100](this) it got AC in 0.78s,

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

    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.

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

How to solve Escape One?

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

How to solve GCD of the Submasks?

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

    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

    $$$F(n) = \sum\limits_{k = 0}^{30}{\sum\limits_{i=0}^{\frac{n - 2^k}{2^{k+1}}}({2^k + i * 2^{k+1})^{2^k}}}$$$

    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

    $$$F(n) = \sum\limits_{k = 0}^{30}{{2^k}^{2^k}\sum\limits_{i=0}^{\frac{n-2^k}{2^{k+1}}}({1 + 2 * i)^{2^k}}}$$$

    So how to solve this? Let's split the sum into two parts.

    $$$F(n) = \sum\limits_{k = 0}^{p}{{2^k}^{2^k}\sum\limits_{i=0}^{\frac{n-2^k}{2^{k+1}}}({1 + 2 * i)^{2^k}}} + \sum\limits_{k = p+1}^{30}{{2^k}^{2^k}\sum\limits_{i=0}^{\frac{n-2^k}{2^{k+1}}}({1 + 2 * i)^{2^k}}}$$$

    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.

    Setter's Solution
    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hints for Absolute Min Max ?

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

    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!

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

Editorials out! :)

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

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!

→ Reply