Official Analysis (C++)

Explanation

Firstly, notice that we can binary search on the answer, or $X$ in this case. For each $X$, we must check if it is valid, and update the binary search accordingly. We can binary search on $X$ because, for smaller values of $X$, we are giving more gallons of milk. Therefore, if it is possible for one $X$ value to meet the requirement, it is possible for all of the values less than that $X$ to do so as well.

To efficiently determine whether a given $X$ value is valid, we can simulate the process. However, we process all states where $Y$, the number of gallons Bessie pays back, does not change all at once.

Additionally, notice that if Bessie gives more than $\sqrt{2N}$ distinct values of $Y$, then she will have definitely paid off the debt, since $1 + 2 + \ldots + \sqrt{2N} \ge N$, which means that the upper bound of the number of operations we must make is $\sqrt{2N}$, satisfying our time constraints.

Therefore, we can validate a given value of $X$ in $\mathcal{O} (\sqrt{N})$ time, and the entire solution runs in $\mathcal{O}(\sqrt{N}\cdot \log {N})$.

Implementation

Time Complexity: $\mathcal{O}(\sqrt{N} \cdot \log{N})$

Copy
#include <algorithm>
#include <fstream>
#include <iostream>

using std::cout;
using std::endl;

/**
 * @return whether Farmer John gives Bessie at least N (numGallons)
 * gallons of milk within withinDays with the given X value

Copy
import java.io.*;
import java.util.*;

public class Loan {
	/**
	 * @return whether Farmer John gives Bessie at least N (numGallons)
	 * gallons of milk within withinDays with the given X value
	 */
	static boolean canRepay(long numGallons, long withinDays, long atLeast, long xVal) {
		long g = 0;

Copy
def can_repay(num_gallons: int, within_days: int, at_least: int, x_val: int) -> bool:
	"""
	:return: whether Farmer John gives Bessie at least N (num_gallons)
	gallons of milk within within_days with the given X value
	"""
	g = 0
	while within_days > 0 and g < num_gallons:
		y = (num_gallons - g) // x_val
		if y < at_least:
			leftover = (num_gallons - g + at_least - 1) // at_least