HackerEarth Watching Video problem solution

In this HackerEarth Watching, Video problem solution Assume you are watching a video on Youtube. Consider the following hypothetical model of how video buffering takes place.

The video renders d KB of data per second, if watched in decent quality. Since you have a 2G Net pack, the bandwidth is fluctuating and does not support smooth video buffer. Also, the data packets send by server each second are fluctuating. The browser accumulates the data packets in cache, and once it gathers at least d KB data, it will play one second of video and remove that data from cache. In case it does not have enough data in cache, it will pause video and wait for enough data packets to start rendering again.

Since you do not want to watch video with such breaks, you pause the video initially and wait for browser to get enough data so that you can watch video smoothly, till the end of video i.e with no breaks. Also, you don’t have much time to spare, so you want to watch video as soon as possible.

There are N data packets in total, received at an interval of 1 second. Your browser receives Xi KB data in ith data packet. It takes 1 second to receive 1 data packet. Your job, now, is to decide the earliest possible time, from which you should start playing the video (i.e hit play button), so that you can enjoy it without any breaks, with decent quality.

Assume you can only play video in integral seconds of time i.e if cache has d / 2 KB data does not mean you can play 0.5 second video. Also, the total data sent by server will be an integral multiple of d.

HackerEarth Watching Video problem solution.

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 100005;
const int M = 100000;
const int X = 1000000;

int a[N], d, n;

bool func(int T) {
   LL res = 0;
   for (int i = 1; i <= n; ++i) {
      res += a[i];
      if (i >= T) res -= d;
      if (res < 0) return false;
   }
   return true;
}

int bsearch(int L, int R) {
   int mid;
   while (R - L > 1) {
      mid = (L + R) >> 1;
      if (func(mid)) {
         R = mid;
      } else {
         L = mid;
      }
   }
   return R;
}

int main() {
   freopen("input.in", "r", stdin);
   freopen("output.out", "w", stdout);
   scanf("%d %d", &n, &d);
   assert(n <= M && d <= M);
   for (int i = 1; i <= n; ++i) {
      scanf("%d", a + i);
      assert(a[i] <= X);
   }
   int ans = bsearch(0, n);
   printf("%d", ans);
   assert(func(ans) == true);
   return 0;
}

coding problems solutions