### Alex_2oo8's blog

By Alex_2oo8, history, 12 months ago, ,

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)
• 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 winners@codechef.com)

Good Luck! Hope to see you participating!!

•
• +24
•

 » 12 months ago, # |   +2 How to solve the 2nd, 3rd and the fourth question?
•  » » 12 months ago, # ^ |   0 L-R queries: sqrt decompositionStrange queries : I think can be solved by dp + segment tree.Can someone confirm if the approach for strange queries is right??
•  » » » 12 months ago, # ^ |   0 ya me two thinking the same
•  » » 12 months ago, # ^ |   +3 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.
•  » » » 12 months ago, # ^ |   0 To maximize m(r + l -m), the absolute difference between (r+l)/2 and m should be minimum. Why?
•  » » » » 12 months ago, # ^ |   0 I got it. Thanks!
•  » » 12 months ago, # ^ |   0 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.
•  » » » 12 months ago, # ^ |   0 Can you give a more detailed approach?
•  » » 12 months ago, # ^ | ← Rev. 2 →   +15 Hints/solution for B (LRQUER). Hint 1Try to bring the given expression to an easier form. Solution of hint 1(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 . Hint 2Try using a segment tree. Solution of hint 2In a node store all the array numbers in a multiset, which are below the node. Full solutionThis 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.
 » 12 months ago, # | ← Rev. 3 →   +8 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.
 » 12 months ago, # |   +3 When will the problems be moved to the practice section? The fact that it isn't done immediately degrades the habit of upsolving.. :/
•  » » 12 months ago, # ^ |   +9 They are by now.
 » 12 months ago, # |   0 Hints for 3rd and 4th question please.
 » 12 months ago, # |   0 Although the official editorials are still not out, unofficial editorials for all the four questions are there in the link. Hope it helps!
•  » » 12 months ago, # ^ |   0 Official editorial are out. https://discuss.codechef.com/tags/ltime54/