Hi! I'm pretty new to competitive programming and right now having some trouble with a pretty straight forward problem.
I just can't seem to grasp why my solution to the problem 1773E keeps getting time limit exceeded, I have already check the resolution and as far as I'm aware it is meant to be O(nlogn), did I made some mistake on the data structures used, or is it just way to slow of a solution ?
As far as I could tell the one that I had implemented was O(nlogn), but I could be way off.
code:
#include <bits/stdc++.h>
using namespace std;
int check_sorted(vector<int> tower, vector<int> nums, unordered_map<int, int> pos) {
int not_sorted = 0;
for(int i = 0; i < tower.size() - 1; i++){
int next_pos = pos[tower[i]] + 1;
if (tower[i + 1] != nums[next_pos]) { not_sorted++; }
}
return not_sorted;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<vector<int>> towers(n);
vector<int> nums;
for(int j = 0; j < n; j++) {
int k;
cin >> k;
for (int i = 0; i< k; i++){
int num;
cin >> num;
towers[j].push_back(num);
nums.push_back(num);
}
}
unordered_map<int, int> pos;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++){
pos[nums[i]] = i;
}
int not_sorted = 0;
for (int i = 0; i < n; i++){
not_sorted += check_sorted(towers[i], nums, pos);
}
int split = not_sorted;
int combine = n + not_sorted - 1;
cout << split << " " << combine << endl;
}
Your problem is that you're not passing the vectors and the map to your
check_sortedfunction by reference. This means that every time you call the function (which can be up to 10 000 times), the code is copying the vectors and all of their data into the function. And the vectors can be huge, up to 10 000 elements. This takes a lot of time (in fact, way too much time). By changing the function parameters to references, the code can access the data from where it already is in the memory and doesn't have to copy it. This makes the code much faster and you're able to easily pass the time limit on this problem.If you don't already know what references are or you don't know how to do them in c++, I would suggest watching a youtube video or reading about it on the internet. For now, all you have to know is that you need to add '&'-signs in front of the variable names in the funtion declaration like this:
You don't need to change anything else in the code, everything will work in exactly the same way.