Hey guys, just wanna share my approach and wanna know your way of doing them!
Quite a famous puzzle, sorting the array and the traveller with min element always takes others to other end.
lets say probability is x (p/100), for the n-1 lines, total prob. is x^(n-1) and lets say we have y as the increased prob. so y^n = x^(n-1) => y = x^(1-1/n). So our increase is p — y*100. (Use doubles)
Problem D1: Line of Delivery (Part 1)
As each of the stone can replace next stone and pass on the energy, the final positions will be the same as input energies. If 0 to i stones are thrown, the resulting positions will be sorted energies of 0 to i. So just sorting the array and indexing 1 from end works. Taking the upper or lower key with min difference for each G outputs ans.
Problem D2: Line of Delivery (Part 2)
If you guys solved problem C & D2, please let me know your approaches.
C: Suppose you know that "a lot" of points are on one line (let's say, over half). Can you find a simple way of finding that line?
D2: The same observation as for D1 — we just need to find the final positions of the balls, because we know they will be in sorted order. Now suppose we already launched $$$k$$$ balls, and they have positions $$$a_1, \ldots, a_k$$$. A new ball comes in with energy $$$x$$$ — how does that affect the sequence? My hint is instead of looking at $$$a_i$$$, look at $$$b_i := a_i - i$$$ (assuming $$$a_i$$$ is sorted).
Zixiang Zhou (duality) solved d2 in interesting way, 2nd position on scoreboard, very short and simple, but I don't understand idea
It looks similar to my solution, the idea is that the sequence $$$a_i - i$$$ happens to be very easy to update.
I try to understand the "meaning" of this value ai-I, looks like after that transformation the bricks are moving 1 step further, if not collided.
For D2, I have an idea that is slightly different from the Official Solution.
Instead of keeping track of where the stones are, I keep track of where the spaces are.
Initially there are infinitely many spaces, from
0to+inf. When a stone is thrown with energyE. The coordinate of the left mostE + 1 + ispaces (iis the index of the stone, 0-based) will decrease by1. For example, after a stone of energy4was thrown, the spaces are now at-1, 0, 1, 2, 3, 5, 6, 7, 8, .... If we again throw a new stone with energy6, then the spaces are now at-2, -1, 0, 1, 2, 4, 5, 6, 8, 9, ....Decreasing a prefix of the array can be time consuming, but we can transform this array into a new array that represent the difference between adjacent elements.
For example,
-1, 0, 1, 2, 3, 5, 6, 7, 8, ...becomes-1, 1, 1, 1, 1, 2, 1, 1, 1, ...and
-2, -1, 0, 1, 2, 4, 5, 6, 8, 9, ...becomes-2, 1, 1, 1, 1, 2, 1, 1, 2, 1, ...Decreaseing a prefix of the array becomes $$$O(1)$$$. Also, most of the entries have value
1, so we can only keep track of the positions where value isn't1.After we finish processing the spaces, we can easily reconstruct the position of these stones.
Here's a video where I explain my solutions, for anyone interested.
Long explanation, but good explanation of "nature" of the task.