Help with "Convoluted Intervals " 2021 Dec. Silver

#1

I would like to ask for help with my following solution (based on USACO posted solution, I just do it myself for practice) to "Convoluted Intervals " 2021 Dec. Silver.

Below is my code.

  1. When I submit it, all cases are correct except it got an X (wrong answer) on case 20;

  2. when I change the line “vector aFreq, bFreq, ans;” to “vector aFreq, bFreq, ans;”: case 20 is correct. However, it got an ! (runtime error or memory exceeded) on case 2, 6, 8, and 16.

Any help is highly appreciated!

#include
#include <bits/stdc++.h>

using namespace std;

int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);

int N, M;
int a, b;
long long num = 0;

vector<int> aFreq, bFreq, ans;

cin >> N >> M;

aFreq.assign(M + 1, 0);
bFreq.assign(M + 1, 0);
ans.assign(2 * M + 1, 0);

for(int i = 0; i < N; i++) {
    cin >> a >> b;
    aFreq[a]++;
    bFreq[b]++;
}

for(int i = 0; i <= M; i++) {
    for(int j = 0; j <= M; j++) {
        ans[i + j] += aFreq[i] * aFreq[j];
        ans[i + j + 1] -= bFreq[i] * bFreq[j];
    }
}

for(int i = 0; i < 2 * M + 1; i++) {
    num += ans[i];

    cout << num << endl;
}

return 0;

}

#2

Sorry, there is an error in my posted question (I think it is caused by some automatic formatting). it should be:

  1. when I change the line “vector aFreq, bFreq, ans;” to “vector aFreq, bFreq, ans;”: case 20 is correct. However, it got an ! (runtime error or memory exceeded) on case 2, 6, 8, and 16.
#3

I don’t see any difference in the lines you changed.

#4

Sorry, I do not why it is not displayed correctly. I think the system automatically removes something from my input.

I change “int” to “long long” for aFreq, bFreq, and ans;

case 20 is correct. However, it got an ! (runtime error or memory exceeded) on case 2, 6, 8, and 16.

Thanks a lot!

#5

Seems to be pretty clear.
For case 20, if you use ints, integer overflow occurs.
However, if you use long longs, which take twice as much memory as ints, the grader runs out of memory.
EDIT: This is wrong, see below post.

#6

Actually, the solution is failing due to accessing an out-of-bounds index. You can find some suggestions for dealing with that here: How To Debug.

Also, please format your code as described here: How to ask for help on a problem

```cpp
code here
```
`inline code`

code here

inline code

#7

Hi Ben,

Thanks for your reply. It works when we change "
ans.assign(2 * M + 1, 0);" to “ans.assign(2 * M + 2, 0);”

Thanks a lot,

1 Like