urusant's blog

Opencup: GP of Japan
By urusant, history, 9 years ago, In Russian

Только что прошел очередной этап opencup-а. Предлагаю обсудить задачи здесь.

В частности, хотелось бы узнать решения H и J.

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody share their solution of D, I and J?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    I: Firstly, if we will use songs with numbered songi1, songi2, ..., songik, then the total satisfaction will be maximized, if fi1 ≤ fi2 ≤ ... ≤ fik or fi1 ≥ fi2 ≥ ... ≥ fik. We wil sort of fi. Let's dp(i,j) — first i songs assigned and j total length of songs.

    dp(i, j) = max{dp(k, j - ti) + pi - (fi - fk)2} = max{dp(k, j - ti) - fk2 + 2fkfi} + pi - fi2 Then we can use convex hull trick optimization. Code

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Hi, I'm the writer of the problem C and H. How was the problems?

    I posted the solution of the problem D here.

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

    I'm the writer of the problem J. I posted my brief editorial for this problem as a blog entry.

    → Reply