Hello CodeForces Community!
It’s time to indulge in some appetizing problems which will be served in Lunchtime. So jot down the details, be there and leave your mark in this contest’s leader-board. Joining me on the problem setting panel, we have:
- Problem Setter: mgch (Misha Chorniy)
- Problem Tester: Alex_2oo8 (Alexey Zayakin)
- Problem Editorialist: adamant (Alexander Kulkov)
- Contest Admin: kingofnumbers (Hasan Jaddouh)
- Russian Translator: CherryTree (Sergey Kulik)
- Mandarin Translator: huzecong (Hu Zecong)
- Vietnamese Translator: Team VNOI
I hope you will enjoy solving them. Please give your feedback on the problem set in the comments below after the contest.
So, note down the details and be there when the contest starts:
Time: 25th November 2017 (1930 hrs) to (2230 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.
Details: https://www.codechef.com/LTIME54
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 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://www.codechef.com/laddu. (For those who have not yet got their previous winning, please send an email to [email protected])
Good Luck! Hope to see you participating!!
How to solve the 2nd, 3rd and the fourth question?
L-R queries: sqrt decomposition
Strange queries : I think can be solved by dp + segment tree.
Can someone confirm if the approach for strange queries is right??
L-R queries: (m-l)(r-m) = mr — lr -m^2 + lm = m(r + l — m) — lr so we have to maximize m(r + l -m). To maximize this we would want the absolute difference between (r+l)/2 and m to be minimum.
To find a number m closest to (r+l)/2, we can keep a segment tree where each node contains a multiset of the values in the segments.
To maximize m(r + l -m), the absolute difference between (r+l)/2 and m should be minimum. Why?
I got it. Thanks!
Shuffling: General idea is to back track the 2 numbers from the last step to the first step. While going back each step, calculate where the 2 indexes have moved.
Can you give a more detailed approach?
Hints/solution for B (LRQUER).
Try to bring the given expression to an easier form.
(AM - AL) * (AR - AM) = (AR + AL) * AM - AM2 - AL * AR. The last term is constant, so it doesn't matter. You are looking for maximum of (AR + AL) * AM - AM2 thus minimum of AM2 - (AR + AL) * AM. You can notice, that
. The second term is constant, so it doesn't matter. Thus you are looking for minimum of 
which is the same as minimum of 
, so you need to find the element with minimum absolute difference from 
.
Try using a segment tree.
In a node store all the array numbers in a multiset, which are below the node.
This segment tree has
space complexity, which fits in ML for N ≤ 105. Building the segment tree can be done as usually, you have to merge the two children's sets in a node.
When updating, you can erase the old value from the set, and insert the new one. It takes
to update a node, and you have to update 
nodes, so overall updating is 
.
When querying, you can go through the
nodes which contains the values of the segment. At each node, you can do a lower_bound on the set for 
, and thus check the elements closest to it. It takes 
, so overall query is 
.
This results in
time complexity.
For L - R queries, I have a proof of the maxima being the number closest to (A[L] + A[R]) / 2 based on differentiation.
The function (A[M] - A[L]) * (A[R] - A[M]) i.e. (x - a) * (b - x) = x * (a + b) - x2 - ab. Now, let (a + b) = y. So, the function becomes (xy - x2 - ab). ( - ab is a constant ).
Now, this function can be differentiated as it is continuous, and the extremum for functions that can be differentiated occurs at points having derivative equal to 0.
Now,
= y - 2x. This function will achieve derivative 0 at x = y / 2. And we also know this function is continuous, so this will achieve maximum value among integers given in array at element closest to y / 2 (Intermediate Value Theorem) .
Try both numbers, the greatest number ≤ y / 2 and the smallest number ≥ y / 2, print the max. Do the last part using a segment tree with vectors.
When will the problems be moved to the practice section? The fact that it isn't done immediately degrades the habit of upsolving.. :/
They are by now.
Hints for 3rd and 4th question please.
Although the official editorials are still not out, unofficial editorials for all the four questions are there in the link. Hope it helps!
Official editorial are out. https://discuss.codechef.com/tags/ltime54/