We are doing LeetRooms with friends. This is semi competitive thing, when we select 4 problems and solve with leaderboard, etc

Let's also check the problems during stream really quickly they are not some bullshit, but pretty simple and cover couple of basic leetcode patterns to revise

Naive solution:
add the probabilities of all sequences that lead to score <= k.
For that try every possible choice (it has probability {1/ numofchoices} * subproblem's probability.

Dp optimization:
Top-down and bottom up DP is pretty simple, it will optimize Complexity from O(maxPts ^ k) to O(k ^ maxPts). BUT FOR THIS FUCKING MIDDLE IT IS NOT ENOUGH

Sliding window optimization:
You clearly see that at each iteration of score, we are recalculating contiguous subproblems score+1, score + 2, score + 3, ... score + maxPts
The optimization would be to remove this summing, and just use precalculated window of sums (tbh was not able to figure it out on my own)

A bit of punching bag this day, cause it was not the greatest day tbh

The solution is straight forward:
- detect zeros subarray
- count number of contiguous subarrays for this zeros subarray
- add it to answer

To count the number of contiguous subarrays in array - you can apply recursion or come up with the formula (if you play enough you will understand it is arithmetic progression: 5 + 4 + 3 + 2 +1 => n + n-1 + n-2 + n-3 ... => n(n+1)/2

Another way is to inline the arithmetic progression while you go