PROBLEM LINK:
Setter: Hasan Jaddouh
Tester: Misha Chorniy
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy
PREREQUISITES:
Prefix sums or anything similar.
PROBLEM:
Given a group of N people. At day 0, only person 1 knows about Snackdown. Array A is given, A[i] means the number of people ith person will inform. This means, that if at day t, ith person knows about snackdown, exactly A[i] more people will know about Snackdown on day t+1. Find minimum number of days to make sure all N people know about Snackdown.
People spread information in increasing order of position. i.e. If person at position p doesn’t know about Snackdown, all people after position p also won’t know.
SUPER QUICK EXPLANATION
- Make prefix sum array, call it pre. If x people know about Snackdown on day T, then pre[x] more people will know about Snackdown on day T+1.
EXPLANATION
First of all, I am explaining a brute force solution, then we’ll optimise it using prefix arrays.
Let us consider naive solution. On day 0, only 1 person knows about snackdown. Next day, X = 1+A[1] people will know. Next day, X = X+A[1]+A[2] + \dots +A[X] people will know. So, we can just increase X by A[1]+A[2]+A[3]+ \dots +A[X]. This process continues till X < N. Let call S = A[1]+A[2]+ \dots +A[X]. Every time, we can calculate S by iterating from index 1 to X.
This process leads to an O(N^2) algorithm.
Now, The thing to speed up above is that, we can calculate S faster than O(N) time by noticing that S is just sum of First X numbers. We can precalculate prefix sum array of given array A, let’s call it pre and Notice that S is just pre[x], thus, computing S in O(1) time, which results in overall O(N) time, which easily fit the time limit.
Also, In case you are not in mood to compute prefix array, it can also be solved by a sum variable, the idea of which is left as an exercize for readers.
BONUS
- Problem statement states A[1] \geq 1. What happens if A[1] ==0.
- Solve a modified problem. People are not notified in increasing order of position. People who know, can tell anyone. Find minimum as well as maximum number of days it takes for all N people to know about Snackdown.
Time Complexity
Since We iterate over all elements once, as well as prefix array construction takes linear time, Time complexity is O(N).
Memory complexity is O(N).
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 