OJ Board

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.

this problem can be solved only by a sorting

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.

Use optimal sorting to get O(n) solution.
Or use backet sort... DP is a crime here ... since that would
be exponential.

baodog wrote:Use optimal sorting to get O(n) solution.
Or use backet sort... DP is a crime here ... since that would
be exponential.

DP is intuitive.

Well, in fact, when I saw the constraints of the problem (n<=20) DP is the first thing that came into my mind to pass the timelimit.

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.

I take the element with maximum Gi and minimum Si first, but I'm getting WA with the greedy approach.

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.

What you need for this problem is the well-known Johnson's algorithm for scheduling. It's always give this optimal ordering.

I managed to derive johnson's algorithm before I knew about it.

For some reason Johnson's all shortest paths is not taught in school...
It's O(V E log V), much better than Floyd-Warshall on sparse graphs.

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.

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 Floyd-Warshall on sparse graphs.

The Johnson's algorithm that is relevant here is Johnson's algorithm for scheduling, which is different from all shortest paths.

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.

wudanzy 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.

This is precisely Johnson's algorithm