Would you please give me a hint for solving the following problem:

http://sharif.ir/~acmicpc/acmicpc00/G.doc

## A regional contest problem

**Moderator:** Board moderators

### A regional contest problem

Last edited by autoldboy on Thu Sep 11, 2014 1:35 am, edited 2 times in total.

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

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.

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

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.