urusant's blog

By urusant, history, 5 years ago, ,

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

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

• +24

 » 5 years ago, # |   0 Can anybody share their solution of D, I and J?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +9 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
•  » » » 5 years ago, # ^ |   0 Thanks a lot for your solution.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +16 Hi! I'm writer of problem I! Thanks for your solving!
•  » » 5 years ago, # ^ |   +16 Hi, I'm the writer of the problem C and H. How was the problems?I posted the solution of the problem D here.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Hi, can you show me your code for problem H? I always get TL on test 25. My codeUPD I found your code
•  » » » » 5 years ago, # ^ |   +5 Some of testers use min-cost-flow, and I used Hungarian method. My solution takes 180ms in worst case.You can show my codes for all problems from here.
•  » » 5 years ago, # ^ |   0 I'm the writer of the problem J. I posted my brief editorial for this problem as a blog entry.