kefeilei87
BAN USERThe idea is to sort them and concatenate. The sorting function though, isn't the natural integer order, but a "lexi-concat" order, that is, a < b if a.b < b.a
- kefeilei87 September 09, 2016First, find out all pies with more slices than N. Each such pie will just add 1 to the final answer and the extra slices are of no use.
Then, you can just sum up the slices of the rest, divide that by N and that's how many slices each person can get off of those. Imagine people forming a line, grab a slice from the current pie and move to the back of the line. No one will get more than one slice from the same pie because none will last for N people.
This seems to be a trick question. As soon as you see the key point it's very obvious. (There's actually a more rigorous proof to step one for why those pies can't contribute more than 1 to the final answer, but I'm too tired to type.)
First of all, we need to cast this problem into a discrete one. We can calculate the pair-wise distances between sensor discs and find the smallest "gap". This should give a heuristics to how fine our grid should be. For instance, if there's only a narrow passage of 0.01 in the middle, guarded by two sensors, our agent needs to be able to move in delta of at most that size to maneuver through.
Once we put everything on a grid, we need a way to mark cells that are covered by sensors. One way is to just store this information in a bit array, but if the grid is very large this is inefficient both in time and space. Instead, we can store the coordinates of sensors in a kd-tree, and to know if a cell is covered we gather all sensors at most R away from the cell and test each one's coverage, where R is the largest radius of all sensors. This doesn't work well if sensors overlap a lot and have a rather disparaging radii. Again, this is a trade-off with the bit array method.
With this setup, the problem becomes a standard A* search.
Fun fact: These numbers are better known as "Taxicab Numbers" and the first one is 1729.
- kefeilei87 September 08, 2016First of all, we need to cast this problem into a discrete one. We can calculate the pair-wise distances between sensor discs and find the smallest "gap". This should give a heuristics to how fine our grid should be. For instance, if there's only a narrow passage of 0.01 in the middle, guarded by two sensors, our agent needs to be able to move in delta of at most that size to maneuver through.
Once we put everything on a grid, we need a way to mark cells that are covered by sensors. One way is to just store this information in a bit array, but if the grid is very large this is inefficient both in time and space. Instead, we can store the coordinates of sensors in a kd-tree, and to know if a cell is covered we gather all sensors at most R away from the cell and test each one's coverage, where R is the largest radius of all sensors. This doesn't work well if sensors overlap a lot and have a rather disparaging radii. Again, this is a trade-off with the bit array method.
With this setup, the problem becomes a standard A* search.
Q1 can be done in O(n) time. You don't have to sort the array. You only need to split it into two halves. First find the median, and then use that as a pivot to rearrange. Then alternate your picks among the two halves.
- kefeilei87 September 09, 2016