Hello, everyone!
I was solving the problem 2057B - Gorilla and the Exam from the Hello 2025 round and I encountered some weird compiler-level issues.
Problematic Code in C++17
void solve() {
ll n,k;
cin>>n>>k;
vector<ll>v(n);
map<ll,ll>m;
for(ll i=0; i<n; i++){
cin>>v[i];
m[v[i]]++;
}
vector<ll>counts;
for(auto&i:m) counts.pb(i.ss);
sort(all(counts));
ll cnt=0;
ll sz=0;
for(ll i=0; i<n; i++){
cnt+=counts[i];
if(cnt <= k) sz++;
else break;
}
if(k==n) cout<<1<<endl;
else cout<<m.size()-sz<<endl;
return;
}
In this code, I encountered a Runtime Error on Test 24 when I used C++17. However, the same code worked perfectly fine in both C++20 and C++23.
Modified Code that worked in C++17
Surprisingly, this also worked in C++17 when I changed some ll to int, as shown below.
void solve() {
ll n,k;
cin>>n>>k;
vector<ll>v(n);
map<ll,ll>m;
for(ll i=0; i<n; i++){
cin>>v[i];
m[v[i]]++;
}
vector<int>counts; //changed ll to int in this line
for(auto&i:m) counts.pb(i.ss);
sort(all(counts));
ll cnt=0;
ll sz=0;
for(int i=0; i<n; i++){
//changed ll to int in the line above
cnt+=counts[i];
if(cnt <= k) sz++;
else break;
}
if(k==n) cout<<1<<endl;
else cout<<m.size()-sz<<endl;
return;
}
Can anyone explain what's happening here? Why does the first code give a Runtime Error when using C++17, and how does it magically work when I change some ll to int?
Have you tried running it on random/whatever tests with sanitizer?
No. But I am able to figure out that I should've iterated from
0tocounts.size()instead of0ton. That must have been the possible reason of encountering a Runtime Error. But I'm unable to understand that why is it working when I changelltoint, even though I'm still iterating from0ton.Accessing outside of the allocated memory is undefined behavior, which basically means anything can happen afterwards. Nothing is guaranteed, so the program may or may not crash, and even if it continues to run, it is not guaranteed to return a consistent result.
Practically, the behavior of out-of-bounds access heavily depends on the location of the memory being accessed. In the OS level, the address space of a program is managed in units called pages. Typically each page is 4096 bytes long, and memory protection (that's what causes segmentation faults) is controlled in the granularity of pages, so your program may or may not access the protected area depending on where your memory is allocated. That's why you see the difference in behavior when you change the size of memory you allocate. But again, nothing is guaranteed, and you shouldn't rely on the behavior of a program that does out-of-bounds access.
If you use GCC or Clang to compile your program, try AddressSanitizer (ASan) to detect out-of-bounds memory access in your program.
The runtime error could be due to you iterating from 1 to n on the counts array when its size is not always equal to n.
Dont know why it works when u change ll to int tho.
Yes, I figured out that mistake. But I'm unable to figure out how it worked when I changed
lltoint. Also, it works fine in both C++20 and C++23 withlltoo.When
n == kyour code reads past the end of the array, which is undefined behavior. Small changes to the code like changing the size of a variable will cause the compiler to output different instructions.