## 11269 - Setting Problems

Moderator: Board moderators

jah
New poster
Posts: 38
Joined: Wed Apr 20, 2005 12:23 am

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

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
this problem can be solved only by a sorting
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET
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.

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

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

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Contact:

### Re: use optimal sorting for O(n) instead of O(nlogn).

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.

jah
New poster
Posts: 38
Joined: Wed Apr 20, 2005 12:23 am
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.

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.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
I take the element with maximum Gi and minimum Si first, but I'm getting WA with the greedy approach.

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

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

goodwill
New poster
Posts: 25
Joined: Mon Sep 03, 2007 10:54 am
What you need for this problem is the well-known Johnson's algorithm for scheduling. It's always give this optimal ordering.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
I managed to derive johnson's algorithm before I knew about it.

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

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

wudanzy
New poster
Posts: 4
Joined: Wed Sep 05, 2007 3:04 pm

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

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:

### Re: Johnson's other algorithm ...

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.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm