Immoral Experiments
Limits: 2 sec., 256 MiB
This statement was translated automatically from Ukrainian.
To develop an effective vaccine against the burdock virus, it is necessary to understand how fast it spreads. Leading Ukrainian scientists — Zenik and Marichka — are conducting various experiments to better understand the patterns of virus propagation.
This time, they seated \(n\) people around a round table. For each person, it is known whether they are infected at the beginning of the experiment. Zenik assumes that if a person is sick, in exactly one minute they infect the people sitting next to them at the table.
If Zenik’s assumption is correct, how much time will pass until all people at the table are infected?
Input
The first line contains an integer \(n\) — the number of people participating in the experiment.
In the second line, \(n\) numbers 0 or 1 are given. 1 means that the corresponding participant is infected at the beginning of the experiment, 0 — healthy.
Output
In a single line, print an integer — the minimum time after which all participants will become sick, if Zenik’s assumption is correct.
Constraints
\(1 \le n \le 10^5\),
at the beginning of the experiment, there is at least one infected participant.
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 7 1 0 0 0 1 0 1 | 2 |
Notes
After the first minute, only the third participant will be healthy, after the second — everyone is infected.
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
Immoral Experiments - Editorial
All people at the table can be split into segments (here a segment is a set of people sitting next to each other) such that each segment is either fully infected or fully healthy. Note that since the table is round, the first participant is a neighbor of the last one. For example, a table of eight participants {0 1 1 0 0 0 1 0} splits into 4 segments:
a healthy segment of length 2 including the first and the last participants,
an infected segment of length 2 including the second and the third participants,
a healthy segment of length 3 including the participants from the fourth to the sixth,
an infected segment of length one including only the seventh participant.
.
Clearly, every healthy segment gets shorter by two every minute, since its two end participants get infected by their infected neighbors. That is, a segment of length \(k\) gets fully infected in \(\lceil \frac{k}{2} \rceil\) minutes. All participants at the table get sick as soon as the longest healthy segment is fully infected.
So all we need is to find the length of the longest healthy segment at the round table. One way to do this: repeat the initial array twice and simply find the length of the longest healthy segment as if the participants sat in a row rather than at a round table.
Complexity: \(O(n)\).
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|