PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: mathmodel
Tester: mexomerf
Editorialist: iceknight1093
DIFFICULTY:
cakewalk
PREREQUISITES:
None
PROBLEM:
You’re given an array A of length N, and an integer K.
A is said to be nice if there exists an array B of length N satisfying:
- B_i = \left\lfloor \frac{A_i}{k}\right\rfloor or B_i = \left\lceil \frac{A_i}{k}\right\rceil
- The sum of B equals 0.
Check if A is nice or not.
EXPLANATION:
Let’s look at the array B.
Each B_i must be either \left\lfloor \frac{A_i}{k}\right\rfloor or \left\lceil \frac{A_i}{k}\right\rceil.
So, the minimum possible sum of B that can be achieved is by choosing B_i = \left\lfloor \frac{A_i}{k}\right\rfloor for all i, while the maximum possible sum is by choosing B_i = \left\lceil \frac{A_i}{k}\right\rceil for all i.
Let L denote this minimum sum, and R denote the maximum sum.
We want the sum of B to be 0, so if L \gt 0 or R \lt 0 this is certainly impossible to achieve.
This leaves us with the case where L \leq 0 \leq R.
In this case, it’s always possible to make the sum of B exactly equal to 0, so A is indeed nice.
Proof
Let’s start with B_i = \left\lfloor \frac{A_i}{k}\right\rfloor for all i, with a sum of L.
The important observation is that for any i, 0 \leq \left\lceil \frac{A_i}{k}\right\rceil - \left\lfloor \frac{A_i}{k}\right\rfloor \leq 1.
So, if we change some B_i to \left\lceil \frac{A_i}{k}\right\rceil instead, it’ll increase the sum of B by either 0 or 1.This means we can simply go in order of i = 1, 2, 3, \ldots, N, and if the sum is \lt 0, change B_i to the ceiling instead of the floor.
Since R\geq 0, we know that once we’ve done this for all indices the final sum will be \geq 0 (since it’ll equal R, after all).The sum started out being \leq 0, increased in steps of 0 or 1, and ended up being \geq 0.
This means, at some point in the middle, it must have been exactly equal to 0 - so we can just stop the iteration at this point and we’ll have a valid array B.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (Python)
from math import *
for _ in range(int(input())):
n,k=map(int,input().split())
a=list(map(int,input().split()))
s2=0
c=0
for i in a:
s2+=max(floor(i/k),ceil(i/k))
if(i%k!=0):c+=1
if(s2>=0 and (s2<=c)):
print("YES")
else:
print("NO")
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, k = map(int, input().split())
a = list(map(int, input().split()))
import math
L = sum(math.floor(x / k) for x in a)
R = sum(math.ceil(x / k) for x in a)
print('Yes' if L <= 0 <= R else 'No')