EDIT: dorijanlendvaj pointed out the issue. It seems to be due to Codeforces compilers being 32 bit unless the 64-bit version is selected.
Hi! While attempting Global Round 14, problem D, my solution was persistently giving RTE, on the sample test case (the one provided in the problem statement). The RTE was only when submitting. The solution ran fine on my system, GeeksForGeeks IDE, and Hackerrank. I submitted in C++11, 14 and 17 all without success. I am still not able to figure out what I have done wrong. I accept that my solution may not be correct for the problem, but I would still like to know why it's causing RTE so that it doesn't happen in a future round. Below is my code (I have commented out the many utility functions/macros I have in my template to keep it short), and below that the steps I took to try and diagnose the issue, and the confusing results. I'd appreciate if someone could help point out the problem. I apologise for this being much too long. I'd use spoilers if I knew how.
#include <bits/stdc++.h>
#define ll long long
#define inarray(a, n) for(int i = 0; i < n; i++) cin>>a[i];
#define all(a) a.begin(), a.end()
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--) {
ll n, l, r;
cin>>n>>l>>r;
vector<ll> sl(n+1, 0), sr(n+1, 0);
for(int i = 0; i < l; i++) {
ll x;
cin>>x;
sl[x]++;
}
for(int i = 0; i < r; i++) {
ll x;
cin>>x;
sr[x]++;
}
for(int i = 1; i <= n; i++) {
ll mn = min(sr[i], sl[i]);
sr[i] -= mn;
sl[i] -= mn;
}
vector<ll> fr, fl;
ll nr = 0, nl = 0;
for(int i = 1; i <= n; i++) {
if(sr[i] > 0) {
fr.push_back(sr[i]);
nr += sr[i];
}
if(sl[i] > 0) {
fl.push_back(sl[i]);
nl += sl[i];
}
}
ll i = fr.size()-1, j = fl.size()-1;
sort(all(fr));
sort(all(fl));
ll ans = 0;
while(i >= 0 && j >= 0) {
if(fr[i] == fl[j]) {
ans += fl[j];
i--;
j--;
}
else if(fr[i] < fl[j]) {
ans += fr[i];
fl[j] -= fr[i];
i--;
}
else {
ans += fl[j];
fr[i] -= fl[j];
j--;
}
}
if(i >= 0) {
ll ii = 0;
while(ii < i) {
if(fr[ii] == fr[i]) {
ans += 2*fr[ii];
ii++;
i--;
}
else if(fr[ii] < fr[i]) {
ans += 2*fr[ii];
fr[i] -= fr[ii];
ii++;
}
else {
ans += 2*fr[i];
fr[ii] -= fr[i];
i--;
}
}
if(fr[i] > 0) {
ans += fr[i] / 2;
}
}
if(j >= 0) {
ll ii = 0;
while(ii < j) {
if(fl[ii] == fl[j]) {
ans += 2*fl[ii];
ii++;
j--;
}
else if(fl[ii] < fl[j]) {
ans += 2*fl[ii];
fl[j] -= fl[ii];
ii++;
}
else {
ans += 2*fl[j];
fl[ii] -= fl[j];
j--;
}
}
if(fl[j] > 0) {
ans += fl[j] / 2;
}
}
cout<<ans<<'\n';
}
return 0;
}
My first step to locate the RTE was using the custom invocation option on Codeforces. Commenting out the while(i >= 0 && j >= 0) loop and everything below it ran. However, when I only commented everything below the loop, it errored out. It appears as if the issue is with the loop. The code runs for the following (nonsensical, just testing) version of the loop:
while(i >= 0 && j >= 0) {
if(fr[i] == fl[j]) {
ans += fl[j];
i--;
j--;
}
else {
i--;
j--;
}
}
So the issue is not in the first if clause. The following version of the loop, however, doesn't run:
while(i >= 0 && j >= 0) {
if(fr[i] == fl[j]) {
ans += fl[j];
i--;
j--;
}
else if(fr[i] < fl[j]) {
ans += fr[i];
fl[j] -= fr[i];
i--;
}
else {
i--;
j--;
}
}
Further, commenting out the line fl[j] -= fr[i] removes the issue. I stepped through the code using GDB in Visual Studio Code monitored the variables. There isn't any case of array out of bounds (for the sample case that I could test on). Even if there was, it shouldn't only cause an issue on that specific line.
I'm unable to fix the issue, and as I said before I would really appreciate if someone can help figure out the problem so it doesn't happen again. If there's any more information I can provide, I'll do so. Thanks to anyone who puts their time into this.







