Convenient For Everybody (CF 464 Div2C)

Problem: https://codeforces.com/problemset/problem/939/C

Quite a confusing problem… Can you explain any test case in detail.

There are n timezones, and you need to find maximum number of participants in between s and f.
1st case:
3
1 2 3
1 3

We have 1 participant in 1st timezone, 2 participants in 2nd and 3 in 3rd.
Now we need to maximize number of participants between 1 and 3rd hour.

You see, when we choose 1 hour for contest: between 1 to 3, there are (1+2=3) participants.
if we choose 2nd hour: Now, remember, we are taking about the 1st timezone. that means all others are moving as well.
For 2nd: 1st–>2nd, 2nd–>3rd, 3rd–>1st. Now participants between 1 and 3 hours(3+1=4)

for 3rd: 1st–>3, 2nd–>1, 3rd–>2. Now participants between 1 and 3 (3+2=5).
hence, 3rd hour is the time to start the contest.
I guess you can work out the 2nd example yourself.

1 Like

btw, why did you wrote DP problem in the title?

Saw it on youtube (vplanet) under the title dynamic programming…

oh ok. just solved it without DP, actually the problem was way more easier than the way it’s worded.

Can you share your solution?

https://codeforces.com/contest/939/submission/56440707

1 Like