pabloskimg's blog

[North America Championship 2020] Probability of placing blocks over a line?
By pabloskimg, 3 years ago, In English

There is a line of length $$$T$$$ ($$$1 \leq T \leq 10^8$$$), divided into $$$T$$$ consecutive empty slots of length 1. There are N blocks ($$$1 \leq N \leq 10^5$$$). The i-th block has length $$$x_i$$$ ($$$1 \leq x_i \leq 10^3$$$). The sum of all block lengths is not greater than $$$T$$$. The $$$N$$$ blocks have to be placed over the line. This is done sequentially and randomly, and there is a chance that the process may fail: for the i-th block, we choose one of the $$$T$$$ slots uniformly, and then we find the first empty slot from there to the right. If no empty slot is found, we fail. If we find an empty slot, then we check if we can place the block (we need at least $$$x_i$$$ consecutive empty slots starting from the empty slot we just found). If there is not enough space to place the block, we fail. Otherwise, we place the block, move on to the next and repeat. If we never fail and manage to place all the blocks, we succeed. What is the probability of succeeding? (link to original problem from NAC 2020: https://open.kattis.com/problems/allkill)

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by pabloskimg (previous revision, new revision, compare).

→ Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

2020 ICPC NAC Solution Video: Problem D

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks. I understood everything he said up to the reduction of the problem as placing blocks over a line. However, from 2:24 onward I'm a bit lost. He says that we can rethink the problem as placing blocks on a circle with an extra empty slot (T+1 slots if I understand correctly), and then he talks about dividing the circle into N sections instead of T+1 and kind of forgetting about the sizes of the blocks. I would appreciate some help to understand that part.

    → Reply