Question 256449 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – Is there is a more efficient and faster solution from my solution and what did I miss?

Office’s biscuits

Task condition

  • Time limit,s => 1
  • Memory Limit,MB => 64

Task

Developer Fyodor loves biscuits in the office very much, and he knows exactly
all the N places where they can be found, as well as the exact number of Cn
biscuits in each place. Today Fyodor is especially hungry, he has finished a big
task, and decides to allocate himself M hours to eat all the biscuits in the
office.

Fyodor calculated the minimum number of biscuits K that he needs to eat within
an hour so that in the end he has time to eat all the biscuits in the office in
the allotted time or earlier.

At any hour, he can visit any one place with biscuits and eat K biscuits
in this place, he will spend an hour on it, even if there are less than K
biscuits left in this place, because he will discuss tasks and plans with
colleagues. Fyodor may not visit places without biscuits.

Colleagues, out of respect for Fyodor, never touch his favorite biscuits.

Input data (received in the standard input stream)

The first line is integers N and M separated by a space
(1≤N≤100 000, 1≤M≤200 000)

Then there are N lines, on each of which there is one integer Cn
(0≤Cn≤10,000)

All the input data of our tests always comply with the specified parameters, no
additional checks are required.

Output data (expected in the standard output stream)

One integer, the minimum possible K. Either 0 if there are no biscuits in
the office, or if Fyodor does not have time to eat all the biscuits in the
allotted time.

Example:

exp 1

input:

  • 3 6
  • 4
  • 4
  • 4

output:

  • 2

A simple example to familiarize yourself with the input and output data

exp 2

input:

  • 3 6
  • 4
  • 4
  • 5

output:

  • 3

There is a similar situation here, but by eating 2 biscuits, Fyodor will not have
time to eat the last one

exp 3

input:

  • 3 3
  • 4
  • 4
  • 8

output:

  • 8

Boundary situation at N = M

Notes:

It is possible to use only standard language libraries, installation and use of
additional libraries are not possible.

how did I solve this problem(linear search):

1 => takes the placesCount(N) and the timesCount(M)
from the first line

2 => calculate the sum(totalCookies) of the biscuits
line by line and at the same time save
the value of each line in a list

3 => call the function solve()

4 => In fn solve first sort the list

5 => defined the placesList, delete all the 0

6 => check if placesCount(N) more than timesCount(M)
return 0, that means that he can not visit all the places
because in one place he takes an hour. or if totalCookies 0
that means there are no biscuits in the office so we
return also 0

7 => if placesCount(N) the same us timesCount(m) return
the max Cn because he will visit every place just one time

8 => calculate the min num of K(k = sum / m), and
the max (k = cnMax)

9 => Call the fun isHighEnough(), then check how much time he takes
for one place then subtract it from m, then return m >=0,tell min==max,
and return k

the code:

const readline = require('readline').createInterface(process.stdin, process.stdout);

let placesCount = null;
let timesCount = null;
let list = [];
let totalCookies = 0;
let linesCount = 0;

const isHighEnough = (k,placesList) => {
  let m = timesCount;
  for( cookieCount of placesList ) {
      m -= Math.ceil(cookieCount/k);
  }
  return m >= 0;
}

const solve = () => {
  let sort = list.sort((a,b) => a-b)
  let placesList = list.length == 1 ? [list[0]] : sort.slice(sort.findIndex(e => e > 0))

  if (placesCount > timesCount || totalCookies == 0) {
    return 0;
  }
  if(placesCount == timesCount){
    return placesList[placesList.length - 1]
  }

  let minCookie = totalCookies < timesCount ? 1 : Math.floor(totalCookies / timesCount);
  let maxCookie = placesList[placesList.length - 1];
  while (minCookie < maxCookie) {
    const testk = Math.floor(minCookie + (maxCookie-minCookie)*0.5);

    if (isHighEnough(testk,placesList)) {
      maxCookie = testk;
    } else {
      minCookie = testk+1;
    }
  }
  return minCookie
};

readline.on('line', (line) => {
  if (linesCount === 0) {
    [placesCount, timesCount] = line.split(' ').map(Number);
  } else {
    totalCookies += Number(line);
    list.push(Number(line));
  }
  if (linesCount++ === placesCount) {
    console.log(solve());
    readline.close();
  }
}).on('close', () => process.exit(0));

My question:

the result of the test is "not true",can you tell me what did I miss, please?

Tags:

2

Answers


  1. Chosen as BEST ANSWER
    0 
    const readline = require('readline').createInterface(process.stdin, process.stdout);

let placesCount = null;
let timesCount = null;
let list = [];
let totalCookies = 0;
let linesCount = 0;

const isHighEnough = (k,placesList) => {
  let m = timesCount;
  for( cookieCount of placesList ) {
    m -= Math.ceil(cookieCount/k);
  }

  return m >= 0;
}

const solve = () => {
  let sort = list.sort((a,b) => a-b)
  let placesList = list.length == 1 ? [list[0]] : sort.slice(sort.findIndex(e => e > 0))

  if (placesList.length > timesCount || totalCookies == 0) {
    return 0;
  }
  if(placesList.length == timesCount){
    return placesList[placesList.length - 1]
  }

  let minCookie = totalCookies < timesCount ? 1 : Math.floor(totalCookies / timesCount);
  let maxCookie = placesList[placesList.length - 1];
  while (minCookie < maxCookie) {
    const testk = Math.floor((minCookie + maxCookie) / 2);

    if (isHighEnough(testk,placesList)) {
      maxCookie = testk;
    } else {
      minCookie = testk+1;
    }
  }
  return minCookie
};

readline.on('line', (line) => {
  if (linesCount === 0) {
    [placesCount, timesCount] = line.split(' ').map(Number);
  } else {
    totalCookies += Number(line);
    list.push(Number(line));
  }
  if (linesCount++ === placesCount) {
    console.log(solve());
    readline.close();
  }
}).on('close', () => process.exit(0));

  2. 0

    To solve this problem with binary search, you need:

    • A minimum possible K. ceil(total_cookies/M) works.
    • A maximum possible K. max_cookies_in_one_place works, or there is no solution. Validate that this number works.
    • a function to check a candidate K to see if it’s high enough.

    Then the binary search is easy, but you have to be careful. You should write it in this order:

    1. The loop
    2. The test. There are different kinds of tests you might have when writing a binary search. We have an "is it high enough test".
    3. The implications of the test results. A "high enough" test means that we’ll either set maxk = testk (testk is high enough) or mink = testk+1 (testk is not high enough)
    4. The midpoint calculation. It must ensure that either choice in (3) will shrink the range and stay within bounds, so we need testk < maxk.
    // find the smallest k that's high enough
// iterate until the answer is determined
while (mink < maxk) {
    // guaranteed mink <= testk < maxk
    const testk = Math.floor(mink + (maxk-mink)*0.5);
    if (isHighEnough(testk)) {
        maxk = testk;
    } else {
        mink = testk+1;
    }
}
// now maxk == mink, and that's the answer

    To check to see if a candidate K is high enough, you can do this:

    const isHighEnough = (k) => {
    let m=M;
    for( cookieCount of placesList ) {
        m -= Math.ceil(cookieCount/k);
    }
    return m >= 0;
}
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search