Faster solution to Educational Round 167 E :O

Правка en2, от ilovefsy, 2024-06-29 14:29:22

I came up with a solution in $$$O(N+K^2)$$$ but idk if it can be even faster. pls tell in comments if you manage to find smt faster bc my math not very good. <3

I'll just talk about the big idea some details will be left out.

The key observation is that the array $$$b$$$ is uniquely determined by the placement of 1s inside the array.

Furthermore, in order for a $$$b$$$ to have a corresponding $$$a$$$, it is sufficient and necessary that the array $$$b$$$ contains no "alone" 1s, i.e each block of 1s must have a length of at least 2.

First, we count the number of possible such $$$b$$$ by doing simple dp(your state is length of $$$b$$$, and whether last element is 1 or not).

Now we need to handle the condition of being able to fit $$$K$$$ integers.

Consider our blocks of 1s in the array. We realize that the number of integers we can fit is at most (number of 1s)-(number of blocks).

Hence, we can brute for the number of 1s and number of blocks and do some combinatorics(how many ways to distribute the ones into the blocks multiplied by the number of ways to place the blocks such that they are not adjacent to each other) to find the number of bs that can fit less than $$$K$$$ integers

We subtract those away and we get our answer.

Here is my sub, 267980941. (i was lazy and used oeis for the first part of counting number of $$$b$$$ XD)

Thanks for reading :)

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский ilovefsy 2024-06-29 14:29:22 67
en1 Английский ilovefsy 2024-06-29 13:36:59 1396 Initial revision (published)