[CDCR2015] - Jimmy and NITT WiFi - Editorial

Problem Link :


Difficulty : Cakewalk

Problem :

Jimmy decides to watch his favorite TV show online. But NITT WiFi is slow and the video hangs if enough data is not
buffered. He wants to watch the video without any such interruptions. If he waits for some T seconds, some part of
the video will be download. After T seconds, he can start watching. He does’nt have to wait for the
whole video to download as the video can download after the starts watching.

Let the whole video be N seconds long. Jimmy has to wait T seconds before he can start watching.
Please note that at any moment of time, the data downloaded must not be less than what is required to watch
that second of the video.

Jimmy is impatient and wants to wait as little as possible. Being is friend, you have to tell him how many
seconds he has to wait to watch the video without interruption.

Explanation :

Jimmy can start watching the video after the whole video is downloaded, but that is not optimal.
The key to solving this question is that the optimal wait time is when the whole video is downloaded
when he is watching the last minute of the video.

Let t be the wait time.

x - kB required to watch 1 second of the video

y - Download speed in kB/s

z - Duration of the video in seconds

t + z = x * z / y
t = (x * z) / y - z
  = z * (x / y - 1)
  = (z * (x - y) )/y