You are not logged in. Please login at www.codechef.com to post your questions!

×

SPREAD2 - EDITORIAL

PROBLEM LINK:

Practice
Contest

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. :)

This question is marked "community wiki".

asked 13 Oct '18, 15:51

taran_1407's gravatar image

6★taran_1407
3.9k2895
accept rate: 22%

edited 17 Oct '18, 21:31

admin's gravatar image

0★admin ♦♦
19.8k350498541


"AccessDeniedAccess Denied7177C0A2399E3ED5lGPRT7br9D2AQ5hB3rN8GTtl+OlB9dustBosTrYFWGRF5AKA/nC0oChrs5n74cJmxykiwPdp/fg=" on trying to download solutions of any question given in the editorial section of snackdown19 .

link

answered 18 Oct '18, 14:29

sushantjsr13's gravatar image

2★sushantjsr13
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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