MULTHREE - Editorial

editorial
, , , , ,
64

Consider the test input:

1                                                                       
99999999997 1 0
1 Like
65

done. shows no error and the output is NO.

66

The answer should be YES.

1 Like
67

Thanks for your help! It finally accepted the solution

1 Like
68

This is my solution in C++ :

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef vector v;

#define ar(length) array<long, length>

#define rep(i, a, b) for (long i = a; i <= b; i++)

#define rrep(i, a, b) for (long i = a; i >= b; i–)

void solve(ll k, ll d0, ll d1)

{

ll count = 2;

ll allsum = d0 + d1;

while (count < k)

{

    ll newdigit = allsum % 10;

    allsum += newdigit;

    if(newdigit==0)

    break;

    if (newdigit == 8)

    {

        ll rem = (k - count - 1) % 4;

        ll quo = (k - count - 1) / 4;

        allsum += (20 * quo);

        if (rem == 1)

            allsum += 6;

        else if (rem == 2)

            allsum += 8;

        else if (rem == 3)

            allsum += 12;

        break;

    }

    count++;

}

if (allsum % 3 == 0)

    cout<<"YES\n";

else

    cout<<"NO\n";

}

int main()

{

ios_base::sync_with_stdio(false);

long t;

cin >> t;

while (t--)

{

    ll k, d0, d1;

    cin>>k>>d0>>d1;

    solve(k, d0, d1);

}

return 0;

}

Explanation:

If you print out 20 digits of N then you will find a pattern of 4 numbers ‘6’ ‘2’ ‘4’ ‘8’ gets repeated. The answer to making the algo O(1) lies in stopping the loop as soon as we find this pattern (in this case I stop the loop when I find ‘8’) and just multiply the sum of the nos (6+2+4+8) = 20 by the number of times that pattern is repeated hence forth.

The number of times the pattern repeats can be found simply by (k-1-count) / 4. k-1 is the number of terms needed and count is the current iteration we are in.

However there remains a chance that the pattern ends without all 4 digits being included, in that case we will have some remainder( (k-1-count)%4 = 1 , 2 or 3 ). If remainder is 1 then ‘6’ is the left out digit which we will add with the rest, similarly if remainder is 2 then ‘6’ and ‘2’ are remaining digits whose sum 6+2=8 we will add to the total sum and so on.

All this while making sure we don’t encounter ‘0’ as a digit in between, because if that happens then the pattern will not form and after that only 0 will be obtained as newdigit in each successive iterations. So as soon as we encounter ‘0’, we halt and check for the sum of numbers we have uptill now. P.S. Not doing this check for ‘0’ is the reason why I was repeatedly getting TLE even though my algo was O(1) and it made me frustrated, make sure to apply this check. :sweat_smile:

What’s left now is just to check if total sum of digits is divisible by 3 or not and we’re done!

NOTE: Make sure to use long long for this program or you will get errors as the numbers are huge.

1 Like