SIMPLEX Editorial

editorial

#1

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)

contest
practice

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)

contest
practice

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)

contest
practice

We have to calculate the number of s*s blocks where sum = 0.

We write 1 for all (xi,yi) in an mn matrix and then precompute the cumulative sum in a matrix such that sum[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*[j] = value of ss block ending at (i,j) = sum[j]-sum[i-s][j]-sum*[j-s]+sum[i-s][j-s]

And count the number of values where val*[j] == 0

Time Complexity - O(m*n)

Bulbasaur On Trip (SMP164)

contest
practice

Couldn’t solve

PokeBlocks (SMP165)

contest
practice

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)

contest
practice

Couldn’t solve