Newspapers - Binary Search / Advanced

Problems
1

https://algo.monster/problems/newspapers_split

2

why high is 1000000001?

3

1 <= newspapers.length <= 10^5

4

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

5

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.

6

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

7

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

8

Can you add JS answers?

11

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;
    }
12

Similar way low can be as below.

    int low = Collections.max(newspapers);
13

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;
}

14

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

15

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?

16

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.

17

Ah - makes sense. Thank you.

18

Almost similar to Capacity Problem

19

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)

20

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
21

Here is my work:

import java.util.Arrays;
import java.util.List;
import java.util.*;
import java.util.Scanner;
import java.util.stream.Collectors;

class Solution {
public static int newspapersSplit(List newspapers, int coworkers) {
int left = Collections.max(newspapers);
int right = sum(newspapers);
int boundary = -1;

    while(left <= right){
        int mid = (left + right) / 2;
        if(isFeasible(newspapers, mid, coworkers)){
            boundary = mid; 
            right = mid - 1;
        }else{
            left = mid + 1;
        }   
    }
    
    return boundary;
}

public static int sum(List<Integer> list) {
 int sum = 0; 

 for (int i : list)
     sum = sum + i;

 return sum;
}

public static boolean isFeasible(List<Integer> newspapers, int value, int maxWorkers){
    if(newspapers.size() == 0){
        return false;
    }
    
    
    int sum = 0;
    int countWorker = 1;
    for(int newspaper : newspapers){
        if(newspaper > value){
            return false;
        }
        
        if(sum + newspaper <= value){
            sum += newspaper;
        }else{
            sum = newspaper;
            countWorker++;
        }
    }
    
    return countWorker <= maxWorkers;
}

public static List<String> splitWords(String s) {
    return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
}

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    List<Integer> newspapers = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
    int coworkers = Integer.parseInt(scanner.nextLine());
    scanner.close();
    int res = newspapersSplit(newspapers, coworkers);
    System.out.println(res);
}

}

22

dsfdsfds