## A regional contest problem

Let's talk about algorithms!

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
Location: Calgary, Canada
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
Location: Calgary, Canada
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
Location: Edmonton AB Canada
This problem can be done as a linear minimisation (so using the simplex algorithm).

You do need to be careful about how you define the problem, since there is at least one wrong way (runs too slow) and one right way

Any greedy approach that I came up with didn't work, so I'm not sure that it is the way to do it.