NICEARRAY - Editorial

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')
1 Like

I was getting runtime error can anyone please explain why

fun main() {
    val n = readln().toInt() // T
    val result = mutableListOf<String>()

    var b : Long = 0
    var negativeNums = 0
    var positiveNums = 0

    for (k in 0 until  n) {
        val m = readln().split(' ') // m[1]
        val a = readln().split(' ') // N

        for(i in 0 until a.size) {
            b = b + (a[i].toLong()/m[1].toLong())

            if(a[i].toLong() % m[1].toLong() != 0.toLong()) {
                if(a[i].toLong() < 0.toLong())
                    negativeNums = negativeNums + 1
                else
                    positiveNums = positiveNums + 1
            }
        }
        if(b == 0.toLong())
            result.add("YES")
        else if(b < 0.toLong() && (positiveNums + b) >= 0.toLong()) {
            result.add("YES")
        } else if(b > 0.toLong() && (b - negativeNums) <= 0.toLong()) {
            result.add("YES")
        } else
            result.add("NO")

        b = 0
        negativeNums = 0
        positiveNums = 0
    }

    for (i in result)
        println(i)
}