#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

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

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;
    }
}

Rev.	By	When	Δ	Comment
en5	Leeisateam	2021-12-28 04:13:59	6	Tiny change: ' 10^9 * 104 = 10^13 ' -> ' 10^9 10^4 = 10^13 '
en4	Leeisateam	2021-12-27 23:02:56	1255	Tiny change: '99999\n...\n~~~~~\n\' -> '99999\n... (this is repeated 10000 times)\n~~~~~\n\' (published)
en3	Leeisateam	2021-12-27 22:49:23	85
en2	Leeisateam	2021-12-27 22:30:53	470
en1	Leeisateam	2021-12-27 22:16:03	3578	Initial revision (saved to drafts)

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

History