Min Sum Construction#12262

Min Sum Construction (Editorial)

Problem Author:	Hasan Saleh (MathModel)
Prepared by:	Hasan Saleh (MathModel)
Edited by:	Hasan Saleh (MathModel)

Solution

We are asked to construct an array $A$ of length $n$ such that $1 \leq A_{i} \leq n$ 1 \le A_i \le n, $\sum_{i = 1}^{n} A_{i} = a$ \sum_{i=1}^n A_i = a and $\sum_{i = 1}^{n} min (A_{i}, b) = c$ \sum_{i=1}^n \min(A_i,b) = c. The condition with the minimum is the restrictive one, so we first make this sum correct, then we fix the real sum.

Note that we never need to start from a value bigger than $min (b, n)$ , because values are capped by $n$ anyway and any value $> b$ gives the same contribution $b$ to the capped sum. Let $B = min (b, n)$ B = \min(b,n) If we set

A_{i} = B for all i = 1, \dots, n,

A_i = B \quad \text{for all } i=1,\dots,n,

then we currently have

i = 1 \sum n min (A_{i}, b) = i = 1 \sum n B = n \cdot B,

\sum_{i=1}^n \min(A_i,b) = \sum_{i=1}^n B = n \cdot B,

and also

i = 1 \sum n A_{i} = n \cdot B .

\sum_{i=1}^n A_i = n \cdot B.

Call this current capped sum $tot = n \cdot B$ \text{tot} = n \cdot B.

We want the capped sum to become exactly $c$ . Since right now every $A_{i} \leq B \leq b$ A_i \le B \le b, decreasing $A_{i}$ A_i by $1$ will decrease $min (A_{i}, b)$ \min(A_i,b) by $1$ as well. So we walk from $i = 1$ i=1 to $n$ and while $tot > c$ \text{tot} > c we try to lower $A_{i}$ A_i. For a fixed position $i$ we cannot lower more than what is still extra, and we cannot go below $1$ , so we take

v = min {tot - c, A_{i} - 1, B - 1}

v = \min\{\, \text{tot} - c,\; A_i - 1,\; B - 1 \,\}

and do

A_{i} \leftarrow A_{i} - v, tot \leftarrow tot - v .

A_i \gets A_i - v,\quad \text{tot} \gets \text{tot} - v.

After one pass the equality

i = 1 \sum n min (A_{i}, b) = c

\sum_{i=1}^n \min(A_i,b) = c

holds, because each unit we subtracted from some $A_{i} \leq b$ A_i \le b reduced the capped sum by exactly $1$ .

Now we check the real sum $\sum A_{i}$ \sum A_i. If $b \geq n$ b \ge n, then $B = n$ B = n and $min (A_{i}, b) = A_{i}$ \min(A_i,b) = A_i for all $i$ , so once the capped sum is $c$ we already have $\sum A_{i} = c$ \sum A_i = c, and since the statement guarantees that a solution exists we must have $a = c$ a=c and we are done.

If $b \leq n$ b \le n, then after the decreasing phase we have the capped sum right but maybe

i = 1 \sum n A_{i} < a .

\sum_{i=1}^n A_i < a.

To increase the real sum without changing the capped sum we only touch positions with $A_{i} = b$ A_i = b. If we increase such an $A_{i}$ A_i to $b + δ$ b + \delta with $δ \leq n - b$ \delta \le n-b, then

min (A_{i}, b) = b (unchanged),

\min(A_i,b) = b \quad \text{(unchanged)},

but the real sum increases by $δ$ . So we scan again and whenever $A_{i} = b$ A_i = b and the current sum is still $< a$ , we add

δ = min (a - sum, n - b)

\delta = \min(a - \text{sum},\; n - b)

to $A_{i}$ A_i. Because the problem promises that a solution exists, we will find enough such positions to reach the exact sum $a$ . We never violate $A_{i} \leq n$ A_i \le n because we only ever raise from $b$ up to at most $n$ .

The construction is therefore:

set everything to $B = min (b, n)$ B = \min(b,n);
decrease from the front to make the capped sum equal to $c$ ;
if $b \leq n$ b \le n, raise only the positions currently equal to $b$ to make the real sum equal to $a$ .

Complexity is $O (\sum n)$ \mathcal{O}(\sum n).

for _ in range(int(input())):
    n,a,b,c=map(int,input().split())
    base=min(b,n)
    res=[base]*n
    tot=n*base
    i=0
    while i<n and tot>c:
        v=min(tot-c,res[i]-1,base-1)
        if v>0:
            res[i]-=v
            tot-=v
        i+=1
    if b<=n:
        i=0
        while i<n and tot<a:
            if res[i]==b:
                v=min(a-tot,n-b)
                if v>0:
                    res[i]+=v
                    tot+=v
            i+=1
    print(*res)

Python