Codeforces Education Round 84 E

Can somebody please explain to me what this problem means. Here is the link to the problem:

We write down all numbers from 00000- 99999. We make sure the length of it’s string form is n by adding leading 0. A number like 00233 is split into 3 blocks β€˜2’,β€˜33’,β€˜00’. One block of length 1 and 2 blocks of length 2. find the total number of blocks of size i in all the numbers, for all possible i. I really don’t know how it can be explained better than this.

1 Like

This will be solved with a formula ,can anyone say me how can the formula be constructed?
Is the formula constructed on the basis of pattern?

Alright thanks.

No. Combinatorics. My submission.
The main point is there can be n-i+1 positions for a block of size i blocks. Two of them will be at the edge, and n-i-1 will be in the middle. For the ones that are at the edges The number adjacent to it must be different. Therefore, the number of ways is 10(The block can have any number) * 9 (the number adjacent should be different), and 10^{n-i-1} for the rest of the numbers. there can be two ways that the block is at the edge, so the answer for this comes out to 18*10^{n-i}
there are n-i-1 blocks that are not at the edge. For them, both the numbers that are not adjacent have to be different so we get 10(The number in the block) * 9^2(both the adjacent numbers have to be different) * 10^{n-i-2} *(n-i-1)(The number of possible positions)
So finally we get
81\times 10^{n-i-1} \times (n-i-1) + 9\times 10^{n-i} \times 2
So we add the 2. For the answer for block of size i.

1 Like