ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1203. Scientific Conference

What is DP solution? Thx
Posted by Dmitriy 21 Sep 2016 13:50
Hi. I wonder, how can I solve it with dp? I thinked a whole day and cant find the solution less than O(N*T). Give me please some hint.
Re: What is DP solution? Thx
Posted by Oleg Baskakov 21 Sep 2016 14:39
Just sort by endtime and use greedy. It's that easy.
Re: What is DP solution? Thx
Posted by Dmitriy 22 Sep 2016 05:41
Why does it work? Can you prove that approach? I don't understand why it does work :(.
Re: What is DP solution? Thx
Posted by Egor 14 Nov 2016 14:08
Re: What is DP solution? Thx
Posted by Aashir 1 Jan 2017 22:35
O(N * T)? What is 'T'?

This can be solved using greedy, but the O(N^2) DP solution is as follows:
1) Sort by start times

dp[i]: maximum events that can be attended

iterate from j = 0 to i-1, if end time of j-th conference is less than start time of i-th and dp[j] + 1 > dp[i] then dp[i] = dp[j] + 1

answer is max of all elements of dp array
Re: What is DP solution? Thx
Posted by silverfox 30 Apr 2022 18:16
You should save dp[max(end_time)];

remember that for each end time there maybe different start times so that (end - start) are different.

Save these segments, mp[end].push_back(end-start + 1);

now check from 1 to max(end_time) and for each i,

if i is end time? then check this segments sizes,

for each such segment  dp[i] = 1 + dp[i - s]; where s is saved segment sizes for end time 'i'.


https://pastebin.com/C3dagNL2

Edited by author 30.04.2022 18:18