Alex_2oo8's blog

Invitation to CodeChef November Lunchtime 2017!
By Alex_2oo8, history, 7 years 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

Comments Comments (14)
| Write comment?
»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years 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??

    → Reply
  • »
    »
    7 years 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.

    → Reply
    • »
      »
      »
      7 years 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?

      → Reply
  • »
    »
    7 years 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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you give a more detailed approach?

      → Reply
  • »
    »
    7 years 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
    → Reply
»
7 years 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.

→ Reply
»
7 years 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.. :/

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hints for 3rd and 4th question please.

→ Reply
»
7 years 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!

→ Reply