urusant's blog

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

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

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

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

Comments Comments (8)
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    I: Firstly, if we will use songs with numbered song i1, song i2, ..., song ik, then the total satisfaction will be maximized, if f i1 ≤ f i2 ≤ ... ≤ f ik or f i1 ≥ f i2 ≥ ... ≥ f ik. We wil sort of f i. Let's dp(i,j) — first i songs assigned and j total length of songs.

    dp(i, j) = max{dp(k, j - t i) + p i - (f i - f k)2} = max{dp(k, j - t i) - f k 2 + 2f k f i} + p i - f i 2 Then we can use convex hull trick optimization. Code

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