Hello !
I have been trying to solve a problem but I am not able to solve it.
Problem Statement : Find the number of strings of length “N” made up of only 3 characters – a, b, c such that “a” occurs at least “min_a” times and at most “max_a” times, “b” occurs at least “min_b” times and at most “max_b” times and “c” occurs at least “min_c” times and at most “max_c” times. Note that all permutations of same string count as 1, so “abc” is same as “bac”.
Constraints
1<=T<=1000 1<=N<=10^9 1<=min_a<= max_a<=10^9 1<=min_b<= max_b<=10^9 1<=min_c<= max_c<=10^9
Problem Link on spoj : LINK
Please provide some hints !
Thanks !
If I understand problem statement correct, you are asked to find number of integer solutions of equation a + b + c = n with limitations on a, b and.c.
First, let’s solve the problem when there are no upper limit for variables. We can transform equation to a1 + b1 + c1 = n1, where a1 = a - amin, a1 ≥ 0, b1 = b - bmin, b1 ≥ 0, c1 = c - cmin, c1 ≥ 0, n1 = n - amin - bmin - cmin. There are C(n1 + 2, 2) ways to choose nonnegative values for a1, b1, c1.
Now notice that you can solve original equation using inclusion-exlusion principle.