Help needed!

https://codeforces.com/contest/682/problem/A
The naive solution is giving tle. I am unable to understand how to find better solution.

Iterate for either n or m and find value for each. Try some examples

Sol
for(int i=1;i<=n;i++){
    ans+=((m+(i%5))/5);
}

Thank you so much!
But how to come up with this? I mean how to think to come up with such a solution,so simple .

See the pattern with some examples (write brute force and see what are the pairs). Practice more these types of problems.

Firstly, we know that a number n is divisible by 5 if n \equiv 5\pmod{10} or n \equiv 0\pmod{10}.
As you can see, only the unit’s digit matters here, and that should be equal to either 0 or 5.
Now we only care about the remainders of all numbers in the range [1, \ n] \pmod{10}.
Let’s say n = 10x + y ,\ (x, \ y) \in \mathbb{Z}^0 and 0 \leq y < 10. That means we will have x occurences of all remainders along with one occurenence of the first y remainders starting from 1. Do the same for m and make a frequency array or map for the remainders of n and m when divided by 10. Then just add up the minimum frequencies of pairs that make the sum have a digit 5 or 0. For example, (1, \ 9), (1, \ 4), (7, \ 8), (5, \ 0), etc.

thank you !

okay thanks!

As far as I have seen, all Div 2 problem 'A’s have a constant running time solution. :stuck_out_tongue:

Code
    int n, m;
    cin >> n >> m;
    int x[5] = {}, y[5] = {}; 
    ll ans = 0;
    for(int i = 0; i < 5; i++)
    {   
        // x[i] stores the frequency of numbers, of the form number = 5*m + i
        x[i] = (n - i)/5, y[i] = (m - i)/5;
        // This is for adding the numbers (1,2,3,5) if they fall within range, as
        // the above formula does not account for 1,2,3,4,5
        if(i != 0 and n >= i) x[i]++;
        if(i != 0 and m >= i) y[i]++;
    }   
    for(int i = 0; i < 5; i++)
        ans += 1LL * x[i]*y[(5 - i) % 5]; 
    cout << ans << '\n';

Running Time: O(1)

1 Like

It is always a good idea to enclose expressions like this in brackets after operators like +=, -=, etc (although it isn’t required in this case) because some times the arithmetic operations get messed up (happened to me) and it that takes a lot of time to debug because you’ll assume that the above line is right.

1 Like

You mean like 1LL * (bla1 * bla2)? Thanks! Noted.

I’ve started using the gdb debugger! And it’s SICK! I’m able to debug stuff pretty quickly now :relieved:.

[EDIT]: Oh, you mean a += (expression). I think += has the least priority?

1 Like

Nope. The whole expression after ans +=.
Ideally, it should look like this:

ans += 1LL * x[i]*y[(5 - i) % 5];

I prefer not to use a debugger so I can improve but that cost me the whole day today because I used int instead of long long :sob:.

1 Like

Ohh nice. I’ll do that from next time.

Haha, that has happened to me like a million times. In codeforces they have the overflow flag on, so it’s easier there. Anyways after countless such overflow mistakes, now it’s muscle memory for me to use long long wherever necessary! So after such mistakes you come back stronger! :smile:

1 Like

@aneee004 Hey dude, in case you didnt notice, your profile has been detected by MOSS in the April Long Challenge.

How can I learn to use gdb debugger? Any resource for this?

@modifried Yeah I got a mail about it. One of my friends copied my code from my computer. Should’ve been safer. Not sure why the change hasn’t appeared yet.

@ashish_kaur Check this out. There are various other videos about gdb on YouTube. (gdb comes with installation of g++, you don’t have to install it separately).