Google Kickstart Round-F Problem-A - ATM QUEUE

1

Can someone please help me figure out, what i did wrong in kickstart round f problem A
Here is a link to the problem.

My Source Code:

#include<bits/stdc++.h>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<math.h>
#include<sstream>
#include<string.h>
using namespace std;
#define MOD 1000000007
#define endl "\n"
#define lli long long int
bool func(pair<int,int> a,pair<int,int> b){
	return a.first<b.first;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin>>T;
	for(int q=1;q<=T;q++){
		int n,x;
		cin>>n>>x;
		vector<pair<int,int>> pos;
		for(int i=0;i<n;i++){
			int temp;
			cin>>temp;
			pos.push_back(make_pair(ceil((double)temp/x),i+1));
		}
		sort(pos.begin(),pos.end(),func);
		cout<<"Case #"<<q<<": ";
		for(int i=0;i<n;i++){
			cout<<pos[i].second<<" ";
		}
		cout<<endl;
	}
	return 0;
}
2

please Ignore Mistake in printing Case number, the program was clearing the sample test

3

try using stable_sort as sort may not guarantee relative ordering for same values.

4

stable sorting was needed

5

I guess I figured out the mistake (though I am not proficient in CPP).

In the function you used to sort the vector, I guess it should be <=, instead of <.
Try it.

6

Compare function should not return true for equality!

1 Like
7

I checked for stability and it did gave me stable results when i tested it.

8

Actually <= makes it unstable, i checked for that

9

Are you saying that sort function is ambiguous and may or may not give stable results? if that is true can you please elaborate and tell me about it.

10

Thank you everyone, The code is working After i changed sort to stable_sort, apparently sort does not guarantee stable ordering of elements.

11

the comparator is wrong

my code:
bool comp(pair<int, int> a , pair<int , int > b) {
if (a.first == b.first) {
return a.second < b.second ;
}

return a.first < b.first ;

}

void atmqueueOPT(int c) {
int n, x ;
cin >> n >> x ;

vector<int> arr(n) ;

vector<pair<int , int > > res ;

for (int i = 0 ; i < n ; i++) {
	cin >> arr[i] ;
	if (arr[i] % x == 0) {
		res.push_back(make_pair(arr[i] / x , i + 1 ) ) ;
	} else {
		res.push_back(make_pair((arr[i] / x ) + 1  , i + 1) ) ;
	}
}

sort(res.begin() , res.end() , comp) ;

for (int i = 0 ; i < n ; i++) {
	cout << res[i].second << " " ;
} cout << endl ;

}
100% accepted

12

sort() uses algorithms that may not preserve relative ordering of equivalent key values i. e. if a number comes before another with same value in an array then it may not come before another in sorted array too, while stable_sort() uses algorithms that do preserve the relative ordering.
See Stability in Sorting Algorithms and sort() vs stable_sort() .

13

Thanks brother, i see where i was wrong…

14

Thanks vaibhav I learnt a very important concept from you today, thanks for the help

15

I wrote Coding Blocks IDE this code, but it’s giving TLE. Can anybody help?

16

you are just bruteforcing the queue and it is bound to get tle in test case 2, but it should pass test set1, am i right

17

Hi there , you are getting TLE because you are doing an absolute brute force .
You are complexity is dependent on arr[i] .
You should try to visualize it in a mathematical way.

19

You should have gone for maps or vector of vectors that way sorting would not have been required. However in this case I feel stable sort would solve your issue.

21

I think the problem is long long , i don’t know why, but thats the only difference between our codes
and mine give AC on both the test cases

my code

#include <bits/stdc++.h>
using namespace std ;

#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define eb emplace_back
#define mp make_pair
#define f first 
#define s second
#define endl "\n"

typedef long long int ll ;

ll x ;

bool greater (pair<ll ,ll> a , pair<ll , ll> b) {
    return a.f <= b.f ;
}

void solve(){
    int n ;
    cin >> n >> x ;
    vector<pair<ll , ll>> a ;
    ll temp ;
    for (int i = 0 ; i < n ; i++) { 
    	cin >> temp ;
        a.eb(mp(ceil((double)temp / x) , i + 1)) ;
    }
    sort(a.begin() , a.end()) ;
    for (int i = 0 ; i < n ; i++) {
        cout << a[i].s << ' ' ;
    }
    cout << endl ;
}

int main(){
    ios ;

    int T ;
    cin >> T ;
    for (int i = 1 ; i <= T ; ++i) {
        cout << "Case #"<< i << ": " ;
        solve() ;
    }
    return 0 ;
}

and changing my greater function to < also passes both the test cases

22

why is my code working then (i have commented it).
I’ve used the same sort function as urs
sort() isn’t the problem i think