## A regional contest problem

Moderator: Board moderators

autoldboy
New poster
Posts: 1
Joined: Sun Aug 14, 2005 2:57 pm

### A regional contest problem

Would you please give me a hint for solving the following problem:
http://sharif.ir/~acmicpc/acmicpc00/G.doc
Last edited by autoldboy on Thu Sep 11, 2014 1:35 am, edited 2 times in total.

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:
If I remember it correctly I solved it by a greedy approach.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Hm, what kind of greedy approach? I tried it a few times, I tried one covering the most, then one spanning the most, but none of those worked.

Darko

kryptolus
New poster
Posts: 16
Joined: Sun Mar 19, 2006 9:36 am
Location: New York
I've never done this problem but it doesn't seem like a greedy algorithm would work. You might have to try all the permutations. You can limit the amount of permutations you need to do by establishing a bound with the greedy algorithm. I didn't put a lot of thought into it so I could very well be wrong.

On a second thought, a greedy algorithm might indeed work with the given restrictions...

kryptolus
New poster
Posts: 16
Joined: Sun Mar 19, 2006 9:36 am
Location: New York
Hmm..

Let's say you need one cashier for every hour between 0-10 and you can hire the following cashiers:
Cashier 1 works 2-10
Cashier 2 works 0-8
Cashier 3 works 1-9

If you use a greedy algorithm, you have to be careful about which cashier you pick. If you pick Cashier 1 as the first one, you will not have the most optimal solution.
Last edited by kryptolus on Wed Apr 12, 2006 7:53 pm, edited 1 time in total.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Your cashiers work 9-hour shifts, is that legal?

Anyway, here's the case:
1 0 1 1 1 1 1 1 1 1 0 1 0 ...
0
2
4

I pick one that covers the most - that's the case you described, instead of two, I get three.

So, I tried the one that spans the most (in above case all three span 8, "span" from the first needed to the last in one's shift) - but because it is circular, it won't work, just change it into:
1 1 1 1 1 1 1 1 0 1 0 ... 0 1 0

I would really like to know what "you have to be careful" means. I really have no idea how to do it greedily (and I think it can be done, so I have a problem solving it - I never thought about any other approach).

Darko

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am