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