Some problems I dreamt of and now need solutions for

general
#1

Here we go:
1.Chef believes that a subset R of \{1, 2, \cdots, n\} is ripe if for any distinct numbers a, b \in R we have |a-b| > 3. You will be given a positive integer n. Find the number of ripe subsets of \{1, 2, \cdots, n\} modulo 10^4.Assume 1 \le n \le 10^5.

2.In this problem you will be given a positive integer n and a positive integer m. Count the number of solutions to the equation k_1k_2\cdots k_m = n in integers modulo 10^9 + 7.
Assume 1 \le n \le 10^4 and 2 \leq m \le 100.
\newline
3.You will be given a string S of lower case english letters.Chef wants to partition this string into substrings so that each part contains at least one vowel(i.e. \text{a, e, i, o, u}). Find the number of ways in which Chef can do this modulo 10^9 + 7. For example when S = chefu we have the following partitions possible: chefu, che|fu, chef|u and so the respective answer in this case is 3.You can also check that the answer for S = zkzz is 0 because there are no vowels. Assume that 0 < |S| < 10^4.

Hope you enjoy the problems… :slight_smile: :wink: (let me know if there is some error in any of the problem explanations)

2 Likes
#2

Problem 1
Let T(n) denote the number of ripe subsets of {1,2,....n}
Then T(n)= T(n-1) + T(n-3) + 1 . Can be solved in O(n) easily, or faster if necessary.
Base case: T(1)=1, T(2)=2, T(3)=3

Explanation: Start from n. 3 cases arise:

  1. N is included and nothing else (singleton set)
  2. N is included. Then T(n-3) solutions can arise as N-1 and N-2 can’t be selected
  3. N is excluded. Then T(n-1) solutions can arise.

By the way, you have wonderful dreams :grinning:

2 Likes
#3

P1: It can be solved using the equation: (n-4)(n-3)/2

#4

You could have submitted these problems on codechef for Long challenge. You could have earned a few bucks too😛. Btw very good problems

1 Like
#5

Problem 3
This can be solved using a basic combinatorial argument. Between each pair of vowels, assume there are k consonants. (k can be 0). Then we can insert a partition splitter at k+1 locations (or not insert it at all), for a total of k+2 cases.
The answer will simply be product \prod (K_j+2) where K_j denotes the number of consonants between the jth and (j+1)th vowel.

2 Likes
#6

Problem 2

First, let us get the prime factorization of n, n = \prod p_i ^ {G_i} .
Now for each prime number, we find the number of ways to divide its exponent among m numbers. This is given by m+G_i-1 \choose G_i .
So multiplying this quantity over all factors should give us the answer.

2 Likes
#7

Actually I was also thinking of including the empty set in the answer so the dp would actually be just T(n)= T(n - 1) + T(n - 3). Thanks I get dreams like this one rarely so I decided to share it…

1 Like
#8

That is nice except for the teeny tiny point you missed about the question. It says integer solutions NOT positive integer solutions. So you actually need to do more to find the answer. Think about it…

1 Like
#9

Exactly the the solution I was going for. Nice idea

1 Like
#10

Oh right! I did not pay enough attention.
Building on top of the current solution. first m-1 factors are independent so each can take -1 or 1 as the sign in 2 ways. The sign of the last factor depends on these m-1 so there is only choice for this.
So multiplying the answer by 2^{m-1} should give the answer.

#11

You got the mystery factor!!
Another way to see why 2^{m - 1} is the factor, is that we essentially are choosing an even number of numbers and flipping their signs so it is like
{m\choose 0} + {m \choose 2} + \cdots, which is pretty much the same thing so yeah.

1 Like