Editorialist: Harshit Kumar
PREREQUISITES:
- Basic Arithmetic
PROBLEM LINK:
PROBLEM IN SHORT:
Given a sequence of N non-zero positive numbers, find the number of ways of expressing T as the sum of four elements of S.
SOLUTION:
● At first, we will make a table of every unique number and its frequency.
● Now Imagine you have 4 boxes, A, B, C, D. we will fill these boxes with numbers such that A>=B>=C>=D.
● Try filling the boxes with numbers such that the above condition is satisfied, and they add up to the required sum. When a valid combination if found, use the frequency table to find the count.
● After adding up the numbers there could only be three possibilities, 1) Sum>T: we’ll change the least significant number that can be reduced (not minimum) with
the highest number in the sequence that is less than the given number. 2) Sum<T: we’ll change the most significant number with the highest number in the sequence that is less than the given number and maximize the other numbers under given conditions(A>=B>=C>=D). 3) Sum=T: Find the count using frequency table.
Example: Let’s take subtask 1: S = (2, 1, 1, 1, 2, 1, 2, 2, 1) and T = 6
Frequency Table:
1 → Count=5
2 → Count=4
Now fill the boxes:
2,2,2,2 → exceed sum
2,2,2,1 ->exceed sum
2,2,1,1 → possible! Number of ways=5C2 * 4C2 = 60 (number of ways of choosing 2 items out of 5 items * number of ways of choosing 2 items out of 4 items).
2,1,1,1 → less than sum
1,1,1,1 → less than sum
No other possibility
Answer = 60.
Since the array only consists of 1s and 2s you can also do this question by observation.
there is only 1 way: using two 2s and two 1s. thus, the number of ways =
4C2 * 5C2 = 60.
Example: Let’s take subtask 3: S = (1, 3, 2, 1, 1, 3, 4, 2, 2) and T = 8
Frequency Table:
1 → Count=3
2 → Count=3
3 → Count=2
4 → Count=1
4,3,3,_ → exceeds sum.
4,3,2,_ → exceeds sum.
4,3,1,1 → exceed sum.
4,2,2,2 → exceed sum.
4,2,2,1 → exceed sum.
4,2,1,1-> possible! Number of ways=1C1 * 3C1 * 3C2 = 9.
4,1,1,1-> less than sum.
3,3,2,2 → exceeds sum.
3,3,2,1 → exceeds sum.
3,3,1,1 → possible! Number of ways=2C2 * 3C2 = 3.
3,2,2,2 → exceeds sum.
3,2,2,1 → possible! Number of ways=2C1 * 3C2 * 3C1 = 18.
3,2,1,1 - > less than sum.
2,2,2,1 → less than sum.
Answer = 9 + 3 +18 = 30
Bonus: Do the 2nd part yourself.
Hope that helped.