Блог пользователя Alex_2oo8

Автор Alex_2oo8, история, 7 лет назад, По-английски

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

  • Проголосовать: нравится
  • +24
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 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.

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

    Hints/solution for B (LRQUER).

    Hint 1
    Solution of hint 1
    Hint 2
    Solution of hint 2
    Full solution
»
7 лет назад, # |
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.

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hints for 3rd and 4th question please.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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