ARC-105 - Codeforces

#	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
5	-is-this-fft-	158
6	adamant	157
6	awoo	157
8	TheScrasse	154
8	nor	154
10	djm03178	153

I wanted to do a runtime analysis of B. It got AC even though I doubted it as it looked worst case O(n^2). Basically I just simulated what was asked. It is also mentioned in the editorial that simulation would take too much time. I am now really interested in the runtime of my code.

ARC-105_B

//Think simple yet elegant.
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define REP(i,n) for(int i=0;i<n;i++)
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
const ll maxn=100005;
const ll mod=1e9+7;


int main(){
    fast;
	ll n,i,j,k;
	cin >> n;
	vector<ll> a(n);
	set<ll> hsh;
	for(i=0;i<n;i++){
		cin >> a[i];
		hsh.insert(a[i]);
	}
	sort(all(a));

	ll mx = a[n-1];
	ll mn = a[0];
	ll t;
	while(hsh.size()>1){
		hsh.erase(mx);
		hsh.insert(mx-mn);
		t = min(mx-mn,mn);
		auto it = hsh.end();
		--it;
		mx = *it;
		mn=t;
	}
	cout<<*hsh.begin();
}

Also any ideas on D?

Comments (3)

Show archived | Write comment?

AdHocMan

4 years ago, # |

← Rev. 3 →

-10

Edit: For this test case: 1 2 10e9 your code will run $$$10^9$$$ loops. The test cases were so weak. In those test cases there was not any test case where $$$max\space element - min\space element > 10^5$$$ (or something more) appeared.

→ Reply

Codeforcer

4 years ago, # ^ |

I dont think so..as the size of the hashset remains constant for quite a time before reducing by 1. Also it doesnt explain the statement in the editorial.

Ok. Try this test case: 1 2 10000000. It executes in around $$$2$$$ seconds for your code. May be the test cases were weak. My solution is also like you which will give TLE in some cases.

My code

int n;
    cin >> n;

    set<int> s;

    while(n--){
        int a;
        cin >> a;

        s.insert(a);
    }

    while(sz(s) > 1){

        auto it = s.end();
        it--;

        s.insert(*it - *s.begin());
        s.erase(it);
    }

    cout << *s.begin();

Codeforcer's blog