11269  Setting Problems
Moderator: Board moderators
11269  Setting Problems
Hi could you give me some hints on how to solve this problem efficiently.
I solved it by means of the obvious dp on subsets.
I solved it by means of the obvious dp on subsets.
Sorting the tasks greedily works. Just have to modify the compare function of sorting.
The comparison is similar to this problem http://acm.uva.es/p/v109/10905.html
The problemsetter might wanted to pass the DP solutions, so the limit was kept only 20.
The comparison is similar to this problem http://acm.uva.es/p/v109/10905.html
The problemsetter might wanted to pass the DP solutions, so the limit was kept only 20.
use optimal sorting for O(n) instead of O(nlogn).
Use optimal sorting to get O(n) solution.
Or use backet sort... DP is a crime here ... since that would
be exponential.
Or use backet sort... DP is a crime here ... since that would
be exponential.
Re: use optimal sorting for O(n) instead of O(nlogn).
DP is intuitive.baodog wrote:Use optimal sorting to get O(n) solution.
Or use backet sort... DP is a crime here ... since that would
be exponential.

 Experienced poster
 Posts: 154
 Joined: Sat Apr 17, 2004 9:34 am
 Location: EEE, BUET
Ya, the problem was set as an easy dp problem. So, the constraint is set so that the obvious state dp solution can pass the time limit. If you have any question about that then well, no one is stopping you from getting it accepted by using the greedy solution. So, there shouldn't be any problem.
You should never take more than you give in the circle of life.
A bit of a spoiler...
Hi,
This is a bit of a spoiler...
Suppose there are only 2 problems, with times (a,b), and (t.a,t.b).
Just consider the two possible ordering and calculate
the total time !!!
First Ordering:
a+max(t.a,b)+t.b
Second Ordering:
t.a+max(a,t.b)+b;
Take the smaller one! This is your comparator.
This is a bit of a spoiler...
Suppose there are only 2 problems, with times (a,b), and (t.a,t.b).
Just consider the two possible ordering and calculate
the total time !!!
First Ordering:
a+max(t.a,b)+t.b
Second Ordering:
t.a+max(a,t.b)+b;
Take the smaller one! This is your comparator.
Johnson's other algorithm ...
For some reason Johnson's all shortest paths is not taught in school...
It's O(V E log V), much better than FloydWarshall on sparse graphs.
It's O(V E log V), much better than FloydWarshall on sparse graphs.
greedy algorithm
I using greedy algorithm.
if a[] present the time the first people use to set each problem and b[] for second.
if min(ai,aj,bi,bj)==ai or ==bj, then set the ith problem before the jth.
Furthermore if min(a1,b1...an,bn)==ak let k be the first one to be solved,
or if min(a1,b1...an,bn)==bk let k be the last one.
if a[] present the time the first people use to set each problem and b[] for second.
if min(ai,aj,bi,bj)==ai or ==bj, then set the ith problem before the jth.
Furthermore if min(a1,b1...an,bn)==ak let k be the first one to be solved,
or if min(a1,b1...an,bn)==bk let k be the last one.
Re: Johnson's other algorithm ...
The Johnson's algorithm that is relevant here is Johnson's algorithm for scheduling, which is different from all shortest paths.baodog wrote:For some reason Johnson's all shortest paths is not taught in school...
It's O(V E log V), much better than FloydWarshall on sparse graphs.
There are many things not taught in schools.
It depends on schools, and professors.
Probably the reason that it is not taught is because it is not in CLRS.
Re: greedy algorithm
This is precisely Johnson's algorithmwudanzy wrote:I using greedy algorithm.
if a[] present the time the first people use to set each problem and b[] for second.
if min(ai,aj,bi,bj)==ai or ==bj, then set the ith problem before the jth.
Furthermore if min(a1,b1...an,bn)==ak let k be the first one to be solved,
or if min(a1,b1...an,bn)==bk let k be the last one.