TCO Marathon OR1 and OR2 has finished today, which consume my thoughts for two weeks.
To OR1, I got 1309.01 at submission phase and 4990.66 at end, final rank 67/532. See the problem here(need login), which is a really interesting and challenge game. As my solution, the image could be considered as a onion, the target of this prob is to peel the onionskin. So, here is the steps of my algorithm:
1. Generate the rays, those rays will be the easy calculating ones. (Attention, generate rays does not mean call the measure() method.)
2. Pick out the rays that just cross one unit('x' unit), and store them in a queue.
3 Iterate the selected rays, calculate the density of that unit(call measure() here), and then mark the unit as calculated.
4 Repeat step 2, but the more repetition we used, the more precision we will lost. It should be a bound to control the precision before we start this algorithm.
As to step one, the rays should be selected meet the condition that they will be easy to calculate, otherwise, it will be a great amount work of calculation and simulation. As I considered, each ray will start from one of the four corners of the unit, and the ray should cross exactly n row unit while it crossed 1 col unit, and vice versa. The main reason I ensure this condition is that every length of the row unit( according to my example) that the ray would cross is the same, and that would lower the complexity of the ray calculation. As a result, when n is greater than 30(I forget the exactly number, but 30 is enough), every unit will be covered.
As to step four, the repetition times is a hard decision. The performs of different repetition times would result in a normal distribution, and the peak of the distribution is the one we desired. I choose the repetition according to a great amount of test.
No comments:
Post a Comment