Alex_2oo8's blog

By Alex_2oo8, history, 2 weeks ago, In English,

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

Good Luck! Hope to see you participating!!

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

»
2 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

How to solve the 2nd, 3rd and the fourth question?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      To maximize m(r + l -m), the absolute difference between (r+l)/2 and m should be minimum. Why?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you give a more detailed approach?

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it +15 Vote: I do not like it

    Hints/solution for B (LRQUER).

    Hint 1
    Solution of hint 1
    Hint 2
    Solution of hint 2
    Full solution
»
2 weeks ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

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.

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

When will the problems be moved to the practice section? The fact that it isn't done immediately degrades the habit of upsolving.. :/

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hints for 3rd and 4th question please.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Although the official editorials are still not out, unofficial editorials for all the four questions are there in the link. Hope it helps!