# Help debugging AtCoder: Multiple of 2019

## My Work

``````//Atcoder: Multiple of 2019
//https://atcoder.jp/contests/abc164/tasks/abc164_d
//5 correct, 6 wrong answer. All within time limit.
#include<bits/stdc++.h>
using namespace std;
int main() {
string s1; cin>>s1;
int n=s1.size();

//Store the string S in a vector of integers, in reverse order
vector<int>s;
for(int j=n-1; j>=0; j--) {
s.push_back(s1[j]-48); //convert from char to int (ascii)
}

/*
Approach: input number=sum of s[i]*10^i for 0<=i<=n-1. Keep a prefix array where
prefix_s[k]=(s[0]*10^0+s[1]*10^1+...+s[k]*10^k)%2019.
(Essentially, the last k digits of the input number mod 2019.)
Also maintain a map where each value mod 2019 is mapped
to the number of times it appears in prefix_s.
Then use a variation on the cses_subarraysums2.cpp trick.

For (i,j) to work where i and j are as defined in the problem,
we must have (prefix_s[j-1]-prefix_s[i-1])%2019=0. This is because
the prefix_s[j-1]-prefix_s[i-1] will give the desired substring*10^x
for some x, and since 10^x cannot be congruent to 0 mod 2019, we must have
desired substring%2019=0. So, their difference only needs to be a multiple of
2019.

cses_subarraysums2: Traverse the array, adding to the sum as we pass each element.
As we pass each element, check if the sum is equal to x. Add the current
sum to a map containing all previous sums mapped to the number of times
they occurred. Add past_sums[current_sum] to answer.
*/

//Set up prefix array/vector
int prefix_s[n];
prefix_s[0]=s[0];
for(int j=1; j<n; j++) {
long long next=prefix_s[j-1]+s[j]*pow(10,j);
prefix_s[j]=(next)%2019;
}

int ans=0;
map<int,int> past_nums;
past_nums[0]=1;
for(int j=0; j<n; j++) {
ans+=past_nums[prefix_s[j]];
past_nums[prefix_s[j]]++;
}

cout << ans << "\n";

}
``````

I’m aware that my code is correct in terms of logic, and it also runs fast enough. However, it misses test cases 11-12 and 14-17 despite running well within the time limit. Initially I suspected that I needed to change some of the ints to long longs, but it still gives the same results. Can anyone help? Thanks!

You should try following the debugging tips mentioned here:

I’ve looked through that post, but the links to the debugging module don’t work–they give me a 404 error.

Thanks for noticing, should have been fixed by debugging redirects by bqi343 · Pull Request #3220 · cpinitiative/usaco-guide · GitHub.

I’ve followed all the steps on that page, but I’m still stuck. I don’t think it’s possible to download the test cases from AtCoder.

Actually, you can find their test cases at https://atcoder.jp/. But as the module mentions, you could always try generating your own test cases.

I’m looking through the testcases for that problem, and the only notable thing I can find about the ones I missed is that they are significantly larger than the ones I got correct. I changed all my ints to long longs to account for this, but I still have issues. When running testcases I generate by hand, the code gives the correct output.

Did you try writing a program to generate small test cases (as described in the module)?