PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
None
PROBLEM:
You’re given N, A, B, C.
For a tuple (X, Y, Z) you can:
- Start at 1.
- Every second, move at most X units either left or right.
- Then place an interval of length Y starting at your current position.
This interval lasts for Z seconds.
Find the minimum possible value of AX + BY + CZ such that it’s possible to simultaneously cover all of [1, N] with alive intervals.
EXPLANATION:
Let’s forget the costs A, B, C to begin with, and try to understand which values of (X, Y, Z) can allow us to cover [1, N].
We start at 1 and can move left/right by X units.
Since we want to cover everything, there’s no point in ever moving left - we can just repeatedly move right and place intervals.
If we’re unable to cover [1, N] in time by doing this, moving backwards isn’t going to help either.
In particular, since each interval lasts for Z seconds, we only need to place (at most) Z intervals; since after placing the Z-th one if [1, N] is not covered then we’re in trouble since the first one will disappear.
The first interval must be placed at 1, and has length Y.
What about the second interval?
Well, ideally we want to place it to start at Y+1 since that’s the next uncovered point.
However, whether we can do this or not depends on our movement: if X \ge Y we can move enough; and if not we can move only X steps so the next interval must be placed at X+1 instead.
Now, note that having “too much” movement is pointless: if X \gt Y then we’re limited in moving upto Y anyway since otherwise we’ll skip points; so there’s no point paying more for movement beyond Y.
Thus, an optimal solution will have X \le Y.
With X \le Y, we can assume that we’ll always move X units.
This also means all the intervals we create will be ‘connected’, i.e. we aren’t skipping any points.
So, we only need to know the furthest point that will be covered - everything before it will be covered as well.
This is not too hard to compute: we start at 1, and will move right by X steps for a total of (Z-1) times (i.e. every second other than the first.)
Thus, we’ll end up at position 1 + X\cdot (Z-1).
Starting here we’ll place an interval of length Y, which will cover points upto
The only way this can cover [1, N] completely, is if this quantity is \ge N.
Thus, we want Y + X\cdot (Z-1) \ge N to hold; along with X \le Y.
Our goal is now to minimize AX+BY+CZ across all (X, Y, Z) satisfying this condition.
To do this, let’s try to fix the value of Z in [1, N+1].
(Note that with Z = N+1, simply choosing X=Y=1 makes the expression equal N already; so larger Z are pointless.)
After fixing Z, the product X\cdot (Z-1) must not exceed N, which means that X itself cannot be too large - indeed, X cannot exceed \frac{N}{Z-1}.
(The only exception is Z = 1 in which case the product is always 0; but in that case it’s optimal to choose X = 1 and Y = N, so handle that separately.)
If we further fix X to be some integer in [1, \frac{N}{Z-1}], then the minimal valid Y must satisfy both X \le Y and also Y + X\cdot (Z-1) \ge N, and so is uniquely determined to be \max(X, N - X\cdot (Z-1)), so the corresponding cost can be computed in constant time.
Simply trying all pairs of (X, Z) this way is indeed fast enough, because the overall complexity is
(See harmonic series for why.)
It’s also possible to solve the problem in \mathcal{O}(\sqrt N) time by noting that at least one of X and Z-1 must be \le \sqrt N, though this was not needed for the given constraints.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, a, b, c = map(int, input().split())
ans = a + n*b + c
for z in range(2, n+2):
for x in range(1, n//(z-1) + 4):
if x*(z-1) >= n: break
y = max(x, n - x*(z-1))
ans = min(ans, a*x + b*y + c*z)
print(ans)