#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
4	adamant	160
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
8	Dominater069	154
8	nor	154

1622C - Присвоить или уменьшить

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 - Присвоить или уменьшить