#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

1622C - Set or Decrease

A few others and I had solutions for this problem that passed the system tests but had a bad time complexity of O(aᵢ * t). The problem has aᵢ <= 10^9 and t <= 10^4 so aᵢ * t can be up to 10^13, which could take over an hour for the code to run, and would obviously give the "Time Limit Exceeded" verdict.

For any step, if you choose set, it is optimal to set the greatest element (that hasn't been set yet) equal to the smallest element, because this decreases the sum the most.

If you choose decrease, it is optimal to decrease the smallest element.

It's optimal to do all the decreases before all the sets, because this way the largest elements can be set to an even lower number, compared to if any set step is done before a decrease step.

My initial approach to this problem (with the wrong time complexity) was to simulate the steps one by one, on each step choosing greedily whether to set or decrease based on which would decrease the sum the most, until the sum is at most k.

The issue with this approach is that the simulation takes too long for the test case 1 1 1000000000. In this hack test case, the initial sum is 1 billion and has to be decreased 999,999,999 times until the sum is 1.

C++20 code with bad time complexity

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll t; cin>>t;
    for(ll i=0;i<t;i++){
        ll n; cin>>n;
        ll k; cin>>k;
        ll a[n];
        ll steps=0;
        ll sum=0; // sum of integer array "a"
        ll d=0; // d is the number of times the minimum element is decreased
        ll next=n-1; // u is the next biggest element to set
        
        for(ll j=0;j<n;j++){
            cin>>a[j];
            sum+=a[j];
        }
        sort(a,a+n); // sort the array in increasing order
        
        // Problematic code: O(a_i) time complexity
        // This while loop may take up to ~10^9 loops since a_i <= 10^9
        while(sum>k){
            // Greedy algorithm: Choose to set or decrease
            // based on which decreases the sum more
            // It's optimal for "decrease"s to be done before the "set"s
            if(next>0 and a[next]-a[0]+d>n-next){
                // choose a_i to be the largest integer that hasn't yet been set
                // choose a_j to be the smallest integer in the array
                // set a_i equal to be a_j
                // thus the sum is decreased by the difference between a_i and a_j 
                sum-=a[next]-(a[0]-d);
                next-=1;
            }
            else{
                // decrease the smallest element in the array by 1
                sum-=n-next; 
                d++;
            }
            steps++;
        }
        cout<<steps<<endl;
    }
}
 
/*
 
Hack test case:
 
10000
1 1
1000000000
1 1
1000000000
1 1
1000000000
1 1
1000000000
... (repeat this t=10000 times)
 
In this hack test case, my code will start at sum = 1 billion
and slowly decreases the sum by 1 for each iteration in the
while loop until the sum reaches 1.
 
estimated number of operations needed for my code to solve this test case:
a_i * t = 10^9 * 10^4 = 10^13 (takes > 1 hour)
 
*/

Generator for a test case that hacks the above code with "Time Limit Exceeded" verdict:

(Language: Python 3)

print(10000)
for i in range(10000):
    print("1 1")
    print("1000000000")

Answer for this test case:

999999999
999999999
999999999
999999999
... (this is repeated for 10000 lines)

Some submissions that were hacked by this test case: 140789980 140802718 140824115

If all the other elements are already going to be set to the smallest element, the optimal move is always to choose decrease. With this insight, we can break out of the while loop early in this situation, which happens in the 1 1 1000000000 test case.

C++20 code with correct time complexity

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll t; cin>>t;
    for(ll i=0;i<t;i++){
        ll n; cin>>n;
        ll k; cin>>k;
        ll a[n];
        ll steps=0;
        ll sum=0;
        ll d=0;
        ll next=n-1;
        
        for(ll j=0;j<n;j++){
            cin>>a[j];
            sum+=a[j];
        }
        sort(a,a+n);
        while(sum>k){
            if(next==0){ // This change improves the code's time complexity.
                steps+=ceil((double)(sum-k)/n);
                sum=k-1;
            }
            
            else if(next>0 and a[next]-a[0]+d>n-next){
                sum-=a[next]-(a[0]-d);
                next-=1;
                steps++;
            }
            
            else{
                sum-=n-next; 
                d++;
                steps++;
            }
        }
        cout<<steps<<endl;
    }
}

Full text and comments »

Leeisateam's blog

1622C - Set or Decrease