×

Tester: Misha Chorniy
Editorialist: Taranpreet Singh

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:

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)

This question is marked "community wiki".

3.9k2895
accept rate: 22%

19.8k350498541

 0 "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 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×3,768
×651
×214
×29
×5

question asked: 13 Oct '18, 15:51

question was seen: 1,722 times

last updated: 18 Oct '18, 14:29