- Forum
- General C++ Programming
- Optimization of O(n^2) algorithm
Optimization of O(n^2) algorithm
Hi,
I have a problem which involves n people that walk around a circle in a clockwise direction, which has n-1 chairs around it. If they reach an unoccupied chair, they sit down and never stand up again. The IDs of the people are from 1 to n, in the order they appear in the input. The question requires the ID of the person who doesn't get a chair, and the ID of the person who sits in the first chair that is given in the input.
For example, the chairs are at locations 2, 5 and 8, and the people start at positions 3, 4, 6 and 8.
At time t=1, the person at position 3 moves to position 4, and the one at 4 moves to 5. The person at position 6 moves to 7, and the person at position 8 sits down.
At time t=2, the person who started at 3 moves to position 5, and the one at 5 sits down. The person who started at 6 moves to position 8.
Even though the people who started at 3 and 6 are at a chair, they cannot sit down because the chair is already occupied.
In the end, the person who started at 6 sits down at 2, leaving the person who started at 3 with no chair.
The ID of the person with no chair is 1, and the ID of the person at the first chair in the input (at 2) has ID 3.
I have
1. tried a simulation solution that is O(n^2) which is too slow with the constraints.
2. another observation is that for a person to have the opportunity to reach a chair, there must be at most k-1 people between him and the chair, where the chair is the kth one away from him. This solution is also O(n^2), but most likely, this can be optimised for a better solution.
Can you please give me a few hints or a better solution? Thanks in advance.
--hermitcrab
I have a problem which involves n people that walk around a circle in a clockwise direction, which has n-1 chairs around it. If they reach an unoccupied chair, they sit down and never stand up again. The IDs of the people are from 1 to n, in the order they appear in the input. The question requires the ID of the person who doesn't get a chair, and the ID of the person who sits in the first chair that is given in the input.
For example, the chairs are at locations 2, 5 and 8, and the people start at positions 3, 4, 6 and 8.
At time t=1, the person at position 3 moves to position 4, and the one at 4 moves to 5. The person at position 6 moves to 7, and the person at position 8 sits down.
At time t=2, the person who started at 3 moves to position 5, and the one at 5 sits down. The person who started at 6 moves to position 8.
Even though the people who started at 3 and 6 are at a chair, they cannot sit down because the chair is already occupied.
In the end, the person who started at 6 sits down at 2, leaving the person who started at 3 with no chair.
The ID of the person with no chair is 1, and the ID of the person at the first chair in the input (at 2) has ID 3.
I have
1. tried a simulation solution that is O(n^2) which is too slow with the constraints.
2. another observation is that for a person to have the opportunity to reach a chair, there must be at most k-1 people between him and the chair, where the chair is the kth one away from him. This solution is also O(n^2), but most likely, this can be optimised for a better solution.
Can you please give me a few hints or a better solution? Thanks in advance.
--hermitcrab
Last edited on
How about this?
For the sake of simplicity, let's say that people move to the right.
1. Simulate until there's one person in front of a chair (O(n*m) over the number of positions and the number of people).
2. Remove the person and the chair (O(1)).
3. If there are no more chairs (O(1)), terminate.
4. Find the first chair to the left of the one you just removed (O(1)).
5. If this is the last chair, find the first person to its left (O(1)) and remove them and the chair, then terminate.
6. Let's call the position of this chair b, and the position of the first chair to its left, a.
7. The next person to sit at b should be the first one to the left in (a;b]. O(1).
8. If there's no such person, set the chair at a as the current chair and go to step 6.
9. Remove the chair at b and the person.
10. Set the chair at a as the current chair and go to step 6.
Step 1 is the weak link in the algorithm. Suppose you have people at positions 2, 3, and 4, and chairs at positions 1 and 2^64-1.
I believe there's an O(n) solution over the number of chairs. I'll leave that one up to you.
There's also one edge case where this algorithm as it is performs poorly:
I think there's a simple fix, which I'll also leave to you.
For the sake of simplicity, let's say that people move to the right.
1. Simulate until there's one person in front of a chair (O(n*m) over the number of positions and the number of people).
2. Remove the person and the chair (O(1)).
3. If there are no more chairs (O(1)), terminate.
4. Find the first chair to the left of the one you just removed (O(1)).
5. If this is the last chair, find the first person to its left (O(1)) and remove them and the chair, then terminate.
6. Let's call the position of this chair b, and the position of the first chair to its left, a.
7. The next person to sit at b should be the first one to the left in (a;b]. O(1).
8. If there's no such person, set the chair at a as the current chair and go to step 6.
9. Remove the chair at b and the person.
10. Set the chair at a as the current chair and go to step 6.
Step 1 is the weak link in the algorithm. Suppose you have people at positions 2, 3, and 4, and chairs at positions 1 and 2^64-1.
I believe there's an O(n) solution over the number of chairs. I'll leave that one up to you.
There's also one edge case where this algorithm as it is performs poorly:
|
|
Have you thought about using a ring data structure? It is like a linked list, but the last one has link to the first one - making a ring.
I will leave it up to you to figure out what functions you will need.
Hop all goes well.
I will leave it up to you to figure out what functions you will need.
Hop all goes well.
Persons are '(', chairs are ')'. The problem results the same as to match the parenthesis
In your example will be: )(()(()
So, walk and stacking for a O(n) algorithm.
In your example will be: )(()(()
So, walk and stacking for a O(n) algorithm.
@helios
Thanks for your help. My solution has improved by 80%, but is still 30% away from the target. I think this is because my implementation made the algorithm O(n lg n), which is the best I can make right now. I believe that O(N) will be perfect. The O(n lg n) part comes from step 7, as I am using binary search to find this. More hints also can help :)
@TheIdeasMan
@ne555
@DeXecipher
I will think about your hints and I will get back to you once I have any feel on it.
--hermitcrab
Thanks for your help. My solution has improved by 80%, but is still 30% away from the target. I think this is because my implementation made the algorithm O(n lg n), which is the best I can make right now. I believe that O(N) will be perfect. The O(n lg n) part comes from step 7, as I am using binary search to find this. More hints also can help :)
@TheIdeasMan
@ne555
@DeXecipher
I will think about your hints and I will get back to you once I have any feel on it.
--hermitcrab
If you used two linked lists of positions, step 7 should only take constant time.
Last edited on
Hi, thanks for all the help.
@helios
Thanks for the support. I have found the linked list a bit difficult to implement, so finally I gave up.
@ne555
Stacks are easier for me to work with, and it got home.
Thanks again.
--hermitcrab
@helios
Thanks for the support. I have found the linked list a bit difficult to implement, so finally I gave up.
@ne555
Stacks are easier for me to work with, and it got home.
Thanks again.
--hermitcrab
Topic archived. No new replies allowed.