11269 - Setting Problems

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11269 - Setting Problems

Post by jah » Mon Sep 03, 2007 8:02 am

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
Location: buet, dhaka, bangladesh

Post by ayon » Mon Sep 03, 2007 9:59 am

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

Post by sunny » Mon Sep 03, 2007 10:05 am

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

Post by baodog » Mon Sep 03, 2007 12:35 pm

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
Location: Bangladesh
Contact:

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

Post by DP » Mon Sep 03, 2007 3:11 pm

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

Post by jah » Mon Sep 03, 2007 3:45 pm

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.

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman » Mon Sep 03, 2007 9:59 pm

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
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Tue Sep 04, 2007 12:35 am

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

Post by baodog » Tue Sep 04, 2007 1:33 am

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

Post by goodwill » Tue Sep 04, 2007 1:48 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
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Tue Sep 04, 2007 7:17 am

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

Post by baodog » Tue Sep 04, 2007 7:39 am

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

Post by wudanzy » Wed Sep 05, 2007 3:57 pm

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
Location: Vancouver, BC, Canada
Contact:

Re: Johnson's other algorithm ...

Post by sclo » Wed Sep 05, 2007 8:05 pm

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
Location: Vancouver, BC, Canada
Contact:

Re: greedy algorithm

Post by sclo » Wed Sep 05, 2007 8:05 pm

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

Post Reply

Return to “Volume 112 (11200-11299)”