Newspapers - Binary Search / Advanced

https://algo.monster/problems/newspapers_split

why high is 1000000001?

1 <= newspapers.length <= 10^5

We need more examples in the problem description. Most of the problems I have seen so far have only 1 example each.

Solution should talk about reducing this problem to “Capacity to Ship Packages Within D Days”. The general idea is the same, 1) time to read → weight of package, 2) # of workers → # of days, 3) output min time to read → output min capacity to rent.
We should first map newspapers array to range of possible read times, [max(newspapers), sum(newspapers)], same as in Capacity problem. Then perform binary search on that range, with a helper function to check read_time satisfies input coworkers. This is the same line of reasoning as in Capacity problem, and in the end we reduce to Finding Boundary, to find first read_time with <= input coworkers.

yeah definitely, that problem is the exact same time! thank you for this insight. unfortunately, the solutions are written differently! interesting question nevertheless.

because max newspaper value = 10^4, and max newspaper list length = 10^5, so the max sum = 10^9, adding 1 for bisecting

Can you add JS answers?

As per Test #3, the max size of each list item is 100_000, not 10_000.

Thank you for pointing out. We’ve fixed it.

Regarding the variable “high”
This can be as below, but I guess it’s initialized to default large number for avoiding unnecessary calculation.

    int high = 0;        
    for(int v : newspapers){
      high += v;
    }

Similar way low can be as below.

    int low = Collections.max(newspapers);

Yes,

Replacing this
public static boolean check(List newspapers, int coworkers, int val) {
to would make it work
public static boolean feasible(List weights, int d,int maxWeight) {
int reqDays = 1;
int capacity = maxWeight;
int i = 0, n = weights.size();
while (i < n) {
if (weights.get(i) <= capacity) {
capacity -= weights.get(i);
i++;
} else {
reqDays++;
capacity = maxWeight;
}
}
return reqDays <= d;
}

Maybe need a test case to illustrate this. If you just use 10^5 as the upper bound, all of the tests still pass.

Could anyone explain why we have to add 1 to the result at the end? All of the other code is commented except for that portion. Why does the method always have a delta of 1 and requires it to be added in at the end?

lines 26-27: if it is possible to read newspapers in “mid” time, then high is decreased to mid - 1, (equivalently: mid = high + 1). High is not set in any other place. Hence, at the end, high + 1 corresponds to the shortest time in which it is possible to read all newspapers.

Ah - makes sense. Thank you.

Almost similar to Capacity Problem

from typing import List

def newspapers_split(newspapers: List[int], coworkers: int) → int:
# WRITE YOUR BRILLIANT CODE HERE
def condition(time_req) → bool:
curr_time = 0
worker = 1
for n in newspapers:
curr_time+=n
if curr_time > time_req:
worker += 1
curr_time = n
return worker > coworkers

mint = max(newspapers)
maxt = sum(newspapers)

low = mint
high = maxt
boundary = mint
while low <= high:
    mid = (low + high) // 2
    if condition(mid):
        low = mid + 1
    else:
        boundary = mid
        high = mid - 1
return boundary

if name == ‘main’:
newspapers = [int(x) for x in input().split()]
coworkers = int(input())
res = newspapers_split(newspapers, coworkers)
print(res)

int low = 0, high = 0x3f3f3f3f;

Why can’t we set low= max(newspapers) and high = sum(newspapers)

  • sum of newspapers array is the maximum time that they can spend to read thru all the newspapers, even if they have 100 co-workers, the amount of time they need to spend to read them is the same, isn’t it?
  • low is obviously the max of newspaper array