Hi all,

Programming club, Indian Institute of Technology, Mandi is hosting Dementia '18 as part of our cultural-cum-technical fest Exodia. The contest will take place on 12th April,2018 at 20:00 IST(14:30 UTC). The contest features 6 delectable problems of varying difficulty and you'll get 2.5 hours for solving them. The problem setters and testers for the contest are me(avi224) and hitesh_r. The contest is rated for division II on codechef(below 1800 rating). However, division I can participate out of competition.

There are prizes worth Rs 5K for the top participants(from both divisions) from India.

What if someone gets into division 1 after this contest? Will he participate in long as division 1? He might already have solved problems in division 2.

Fine problems :)

Can someone elaborate solution for the hardest task ? I tried binary search + several wrong greedy strategies for picking optimal plants. I believe I can solve it on a little harder way (always is optimal to water smallest plant — it can be simulated somehow). But I believe there is some easier solution.

P.S. Can you share standings for unofficial participants ?

Thanks :)

So the greedy approach would be to choose the smallest ai plants on i'th day and water them. Then you can apply binary search over days and find the ans.

There is one other approach using segment tree. The idea is to first sort the heights of tree and then keep it sorted after every day. For eg 1 1 1 2 3 3 3 3 3 5 5 5 5 are the heights on some day and you have to water 6 plants, then you go to 6th index and find value ‘h’ and find first and last occurrence of ‘h’. Then increment all the numbers before the first occurrence and some of the numbers with height same as ‘h’, as needed. So the heights will become 2 2 2 3 3 3 3 4 4 5 5 5 5. So the array is still sorted.

Editorial will be out soon which would give more clear idea about the binary search solution.

Combined ranklist will be out soon as well.

I tried to find the lower bound and upper bound of value of h using binary search and then tried to update their heights by increasing them by 1 so that I need not sort the array d times. The complexity will be O(max(nlogn,nd)).I am getting TLE. What is the intended complexity?

Still waiting for combined ranklist

This is the reply we got from CodeChef:

"The combined ranklist cannot be shown publicly now. That will take some time.

For you privately, yes, sorry for the delay. I'll remind the concerned person again to get the combined ranklist. It takes some work because this is the first time we're doing it and some DB scipt needs to be written."

I've put the link to the combined ranklist in the blog. Congrats!

This problem seems somewhat similar to the "Halum and Candies " link: (http://codeforces.com/gym/101353/attachments) the editorial page describes the solution http://codeforces.com/blog/entry/51642

when the problem is add in practice.

Problems are automatically sent to practice now after the contest. You can submit from the problem page itself :)

today it is not working. now it fixed.

When will the ratings be updated,before ending long or after it??

after long is finished.

What is the intended solution to the problem where each query is of the form [Left, Right, x]

And the answer to the query is sum( ceil(A[i]/x) ).

I'm seeing many solutions which solved the problem by just going from Left to Right and summing over ceil(A[i]/x). O(NQ)

Is this the intended solution ?

No, it was using binary search and/or merge sort tree. O(NQ) passed as we didn't expect 5*10^8 operations to pass in 1 s. The observation is that we have to count the frequency of O(sqrt(x)) numbers only for each query. I'll put a detailed editorial soon.

Can also be done using MO's algorithm + Binary Indexed Tree

Kindly elaborate Lakh and avi224. Please post the editorial link on here when it is released !