OJ Board

Would you please give me a hint for solving the following problem:
http://sharif.ir/~acmicpc/acmicpc00/G.doc

If I remember it correctly I solved it by a greedy approach.

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

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

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.

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

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.