Hi, this is just an editorial for the contest hosted by NIT Durgapur recently, named SIMPLEX.
This editorial follows Codeforces Editorial format. I didn’t solve two questions, so can’t give solutions for them.
PokeEggs (SMP161)
This is basically a distribution problem, where you have to divide n identical balls into m distinct boxes with atmost c balls in each box.
Using multinomial theorem, it will be equal to
Co-efficient\ of\ x^n\ in\ (1+x+x^2.....x^c)^m\\ Co-efficient\ of\ x^n\ in\ (1-x^{c+1})^m *(1-x)^{-m}\\ Which\ is\ \sum_{i=0} (-1)^i{m \choose i}{m+n-i*c-i-1 \choose m-1}\\ The\ first\ term\ is\ for\ power\ of\ i*(c+1)\ in\ (1-x^{c+1})^m\\ The\ second\ term\ is\ for\ power\ of\ n-i*(c+1)\ in\ (1-x)^{-m}
You can precompute the factorials for calculating {n \choose r} as the value is <= 10^5
Time Complexity-O(m)
Evolution number (SMP162)
First notice that if n is odd then ans=0 as then the middle term of the number remains the same and no integer added to itself gives 9
For even number, the first term can vary from 1-9 and the remaining terms can vary from 0-9. And its mirror term from other end has to be 9-current_term.
if n%2 == 1 ans = 0 else ans = 9 * pow(10,(n/2)-1)
Time complexity - O(log n)
Snorlax and Puzzle (SMP163)
We have to calculate the number of s*s blocks where sum = 0.
We write 1 for all (xi,yi) in an m*n matrix and then precompute the cumulative sum in a matrix such that sum[i][j] = sum of the values in the block with ends (0,0) and (i,j)
Then we iterate to find the s*s blocks whose sum is 0 which can be done by
val[i][j] = value of s*s block ending at (i,j) = sum[i][j]-sum[i-s][j]-sum[i][j-s]+sum[i-s][j-s]
And count the number of values where val[i][j] == 0
Time Complexity - O(m*n)
Bulbasaur On Trip (SMP164)
Couldn’t solve
PokeBlocks (SMP165)
This was the easiest question of the contest. To find the minimum number of elements such that sum is greater than remaining half, we just sort the elements and add each element from the end, and break when the current sum > total sum - current sum
Time Complexity-O(n log n)
Poke Association (SMP166)
Couldn’t solve