PROBLEM LINK:Setter: Hasan Jaddouh 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
EXPLANATIONFirst 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
Time ComplexitySince 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 Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 13 Oct '18, 15:51

"AccessDeniedAccess Denied7177C0A2399E3ED5lGPRT7br9D2AQ5hB3rN8GTtl+OlB9dustBosTrYFWGRF5AKA/nC0oChrs5n74cJmxykiwPdp/fg=" on trying to download solutions of any question given in the editorial section of snackdown19 . answered 18 Oct '18, 14:29
