dualthread's blog

Hacker Cup- Practice round?
By dualthread, history, 6 weeks ago, In English

Hey guys, just wanna share my approach and wanna know your way of doing them!

Problem A: Walk the Line

Quite a famous puzzle, sorting the array and the traveller with min element always takes others to other end.

Problem B: Line by Line

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 C: Fall in Line

Problem D2: Line of Delivery (Part 2)

If you guys solved problem C & D2, please let me know your approaches.

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Zixiang Zhou (duality) solved d2 in interesting way, 2nd position on scoreboard, very short and simple, but I don't understand idea

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It looks similar to my solution, the idea is that the sequence $$$a_i - i$$$ happens to be very easy to update.

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
6 weeks ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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 0 to +inf. When a stone is thrown with energy E. The coordinate of the left most E + 1 + i spaces (i is the index of the stone, 0-based) will decrease by 1. For example, after a stone of energy 4 was thrown, the spaces are now at -1, 0, 1, 2, 3, 5, 6, 7, 8, .... If we again throw a new stone with energy 6, 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't 1.

After we finish processing the spaces, we can easily reconstruct the position of these stones. See the following Python3 code for more details.

T = int(input())

for cas in range(1, T + 1):
    N, G = map(int, input().split())

    spaces = {}
    spaces[0] = 0
    for i in range(N):
        E = int(input())
        spaces[0] -= 1
        if E + i + 1 not in spaces:
            spaces[E + i + 1] = 2
        else:
            spaces[E + i + 1] += 1

    diff = sorted(spaces.items())

    stones = []
    pos = diff[0][1]
    for i in range(1, len(diff)):
        leftpos = pos + diff[i][0] - diff[i - 1][0]
        pos = leftpos + diff[i][1] - 1
        stones += list(range(leftpos, pos))

    stones = [(abs(stones[i] - G), N - i) for i in range(N)]
    dist, index = min(stones)
    print(f"Case #{cas}: {index} {dist}")
→ Reply
»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Here's a video where I explain my solutions, for anyone interested.

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Long explanation, but good explanation of "nature" of the task.

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For C, I just followed a randomised approach. I chose 2 distinct points at random (600, 300, 100) times and then ran a checker to maximize my answer.

(600, 300, 100) I.e. I submitted 100 iters one first (was scared of the 6m TL) but then I had enough window to submit the 300 iters output, and then 600 iters output as well.

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

is C duplicate? Feels like I've seen it almost exactly before

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution for D2 was somewhat different from the official solution. Each time you throw a ball with power $$$E_i$$$, it ends up at the $$$E_i^{th}$$$ empty position, and all the balls within this range will become shifted to the left. You can represent the number line as a binary array of length $$$N$$$, and maintain it as $$$\sqrt{N}$$$ blocks of size $$$\sqrt{N}$$$ each, with each block represented by a queue. When a ball completely passes over a block (remaining power $$$>$$$ num zeroes), you can shift the balls by popping the front of the queue, and pushing 0 to the back. If a ball stops in the middle of a block, you can manually calculate the resulting state in $$$O(\sqrt{N})$$$ time. Each query runs in $$$O(\sqrt{N})$$$ time, and the total time for all queries is $$$O(Q \sqrt{N})$$$ time, which is good enough to pass.

→ Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I solved C, I shuffled the array of given points then the if the answer is $$$n/2$$$ or more then the answer is quite easy as you can just output n. But if the answer is lesser than $$$n/2$$$ then the probability of a point not belonging in the line that minimices m is $$$<0.5$$$.

So i look for the first $$$40$$$ random points and save the best m they could achieve giving a prob of $$$0.5^{40}$$$ which is fairly small.

→ Reply