Explaining Matches Numbers Problem - beecrowd 3008

Pedro Pancine — Wed, 14 Dec 2022 20:00:00 +0000

This problem is a special one to me because it was created by a professor who taught me in college.

Problem link: https://www.beecrowd.com.br/judge/en/problems/view/3008

Short Description

Given N number of sticks, how many different numbers can you create using all of them and following the image format?

Solution Link: https://github.com/pancine/coding-challenges/blob/master/URI/3008.py

Solution Explained

First, I created two arrays:

R contains all the numbers, including the ones with the leading 0's
T contains all the numbers, excluding the ones with leading 0's

R = [0] * 10001
T = [0] * 10001

The number 8 uses 7 sticks and is the one which uses more sticks, so I initialized R with 7 base cases:
0 sticks -> 0 numbers
1 sticks -> 0 numbers
2 sticks -> 1 number (1)
3 sticks -> 1 number (7)
4 sticks -> 2 numbers (4, 11)
5 sticks -> 5 numbers (2, 3, 5, 17, 71)
6 sticks -> 7 numbers (0, 6, 9, 14, 41, 77, 111)
7 sticks -> 12 numbers (8, 12, 13, 15, 21, 31, 47, 51, 74, 117, 171, 711)

R[0], R[1], R[2], R[3], R[4], R[5], R[6], R[7] = 0, 0, 1, 1, 2, 5, 7, 12

So, now that we have all the possible 1-digit numbers, we can use them to build every possible combination.
For example, if the input is 8:

1 stick numbers with 7 sticks numbers
- (no numbers)
2 sticks numbers with 6 sticks numbers (R[2] x R[6])
- (10, 01, 16, 61, 19, 91, 114, ~~114~~, 141, ~~141~~, 411, ~~411~~, 177, 717, 771, 1111) = 13
3 sticks numbers with 5 sticks numbers (R[3] x R[5])
- (72, 27, 73, 37, 75, 57, ~~717~~, ~~177~~, ~~177~~, ~~771~~, ~~771~~, ~~717~~) = 6
- As you can see, here we have some numbers already on the previous one. This happens because in the R[5] we have the combination R[2] x R[3] (17 and 71) and R[2] was used on the R[2] x R[6] step.
4 sticks numbers with itself
- (44, ~~411~~, ~~141~~, ~~114~~) = 1
- We have repeated numbers for the same reason since R[4] has the combination R[2] x R[2] and R[2] was used on the R[2] x R[6] step.

R[8] is the sum of all cases, which is 20. However, we have the number '01', which is not a possible solution since it has a leading 0, so we have to remove it.

Also, it's possible to apply this logic to any number after 7, leading to a formula:
R[n] = R[n-1] + R[n-2] + R[n-3] + R[n-4] + (3 * R[n-5]) + (3 * R[n-6]) + R[n-7]

Note that:

R[n-1] is always 0
R[n-5] and R[n-6] were multiplied by 3 because both R[5] and R[6] have 3 numbers with 1 digit

Now, for the final part, we need to remove the numbers that have leading zeros.
Looking at the base cases, you will see that the leading 0's are created in the 6 sticks case, so we need to remove this possibility, and to do it, we need to remove all the combinations.

Then, we will have T[n] = T[n] - T[n-6] and note that now we don't multiply by 3 because we don't want to remove 6 and 9.

DEV Community: Pedro Pancine

Explaining Matches Numbers Problem - beecrowd 3008

Short Description

Solution Explained