YCCE Code Ladder Editorials

editorial
, , , , , , ,
1

Pre-requisites

Contest Link: Contest Page | CodeChef
(Please Use this link to read the problem statements till the following links start working)

1. Rainbow (RNBOW)

Problem Link: Practice

Tutorial

Problem: Given a string of arbitrary length, print “Yes” (without quotes) if it is “VIBGYOR”, else print “No” on a separate line. Do this for T testcases.

Solution:
Simply read the number of testcases, T.

Then for T times, read an integer N, then read a string containing N characters.

Compare the sting with “VIBGYOR”, if both are same then display “Yes”, else display “No” followed by a newline character (‘\n’)

C Solution 
#include<stdio.h>
#include<string.h>
int main()
{
    int T,N;
    char S[8];
    scanf("%d",&T);                 //Input T
    while(T--)                      //Repeat T times
    {
        scanf("%d",&N);             //Input N
        scanf("%s",S);              //Input String

        //Compare & print result (don't forget to add '\n' at the end)
        if(strcmp(S,"VIBGYOR")==0) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}
C++ Solution 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int T,N;
    string S;
    cin>>T;                      //input T
    while(T--)                   //repeat T times
    {
        cin>>N;                  //input N
        cin>>S;                  //input string

        //Compare & print result (don't forget to add '\n' at the end)
        cout<< (S=="VIBGYOR"?"Yes":"No") << "\n";
    }
    return 0;
}
Python 3 Solution 
for _ in range(int(input())):
    input()
    s=input()
    print("Yes" if s=="VIBGYOR" else "No")

2. Mina and Her Smart Sister (MINASIS)

Problem Link: Practice

Tutorial

Problem: You’ll be given T queries of form A\ B\ C, where A and B are integers and C is a character \text{(+ or -)}, if C is ‘+’ then print the value of A+B else if C is ‘-’ then print the value of A-B, on a separate line.

Solution
Read the number of testcases, T.

Then for each testcase, read the values of 2 integers A and B, and a character C from a single line. Keep in mind that these are separated by a single space.

Finally if C is ’+’ then display the value of A+B else, display the value of A-B. (Make sure that you print a newline character (‘\n’) after displaying each value.)

C Solution 
#include<stdio.h>
int main()
{
    int T,A,B;
    char C;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d %c",&A,&B,&C);
        printf("%d\n",C=='+'?A+B:A-B);
    }
    return 0;
}
C++ Solution 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int T,A,B;
    char C;
    cin>>T;
    while(T--)
    {
        cin>>A>>B>>C;
        cout<<(C=='+'?A+B:A-B)<<"\n";
    }
    return 0;
}
Python 3 Solution 
for _ in range(int(input())):
    a,b,c=input().split()
    print(int(a)+int(b) if c=='+' else int(a)-int(b))

3. Is It Gaurav, or Muhfaad? (GMF)

Problem Link: Practice

Tutorial

Wondering what this problem is about? Check this out. Don’t forget to get back here!

Okay! Let’s get straight to the solution now.

  1. Sort “GAURAV”, sort “MUHFAAD”.
  2. Sort and compare the input string with above strings. If it matches, then print the name accordingly, else, print “YE KAUNSA JAWAAB HUA”.

Note: Write the exact spellings as mentioned in the problem statement.

C++ Solution 
#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
using namespace std;
int main()
{
    int T;
    string g="GAURAV", m="MUHFAAD", s;
    sort(all(g));
    sort(all(m));
    cin>>T;
    while(T--)
    {
        cin>>s;
        sort(all(s));
        if(s==g) cout<<"GAURAV\n";
        else if(s==m) cout<<"MUHFAAD\n";
        else cout<<"YE KAUNSA JAWAAB HUA\n";
    }
    return 0;
}
Python 3 Solution 
for _ in range(int(input())):
    t=input()
    if len(t)!=6 and len(t)!=7: t="A"   #to avoid sorting & comparison operations on invalid strings
    t=''.join(sorted(t))                #sort & create string
    print("GAURAV" if t=="AAGRUV" else ("MUHFAAD" if t=="AADFHMU" else "YE KAUNSA JAWAAB HUA"))

4. Mujoor CR (MUJCR)

Problem Link: Practice

Tutorial

Problem: Meme Version
Solution:
Input data is large and reading whole input will surely lead to TLE (Time Limit Exceed), but you already that whatever the input be, it doesn’t matter, the output should always be “idontcare” (without quotes). So just read T, and print T lines, each line should contain the string “idontcare” (without quotes). You don’t have to take any other input.

C++ Solution 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--) cout<<"idontcare\n";
    return 0;
}
Python 3 Solution 
print("idontcare\n"*int(input()))

5. The Swaragi Bill (SWGBIL)

Problem Link: Practice

Tutorial

This problem is very straight forward, direct simulation of the given procedure can be done to solve this problem. “With straight forward problem, comes not so straight forward error.”
Here are some common errors that coders can make in this problem:

For WA submissions:

  • Check if you’ve handled the given costs for all 16 items properly. (Most suitable way would be to create an array and use item number as index)
  • int will overflow, so use long long int or unsigned long long instead of int.
  • Also, there might be precision error while calculating the discounted price, to avoid this, you can keep the datatype of bill as long long, and do typecast while applying the discount, i.e. you can do bill = 0.9*(double) bill. This will give the exact value asked in the problem.

For Runtime Error submissions:
This error is most likely to occur in Python. You are possibly reading an extra line in the case when K=0. If K=0, you don’t have to read the line for the number of plates ordered. So, make sure you input the number of plates if and only if K ≠ 0.

C++ Solution 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll T,n,k,item,p;
    
    //create an array of costs such that cost[i] denotes cost of i-th item
    ll cost[17]={0,10,10,5,40,50,40,35,25,25,40,80,100,70,20,15,35};
    cin>>T;
    while(T--)
    {
        cin>>n>>k;
        
        ll cost_per_set=0;   //initially 0
        while(n--)
        {
            cin>>item;
            cost_per_set+=cost[item];
        }

        ll total_sets=1;    //1 for the first yearite herself
        while(k--)
        {
            cin>>p;
            total_sets+=p;
        }

        ll bill=total_sets * cost_per_set;

        //check and apply discount
        if(bill > 1000) bill = 0.9 * (double) bill;

        cout<<bill<<"\n";    //print bill amount
        
    }
    return 0;
}
Python 3 Solution 
#create an array of costs such that cost[i] denotes cost of i-th item
cost=[0,10,10,5,40,50,40,35,25,25,40,80,100,70,20,15,35]

for _ in range(int(input())):

    #first line: n & k
    n,k=map(int,input().split())

    #second line: items array
    cost_per_set = sum(cost[item] for item in map(int,input().split()))

    #third line: P array (Handle K=0 case, don't read this line if k=0)
    total_sets = 1 + (sum(map(int,input().split())) if k else 0)

    bill = cost_per_set * total_sets        #caculate total bill
    if bill>1000: bill = int(0.9*bill)      #apply discount
    print(bill)                             #display final bill amount

6. Is it Segment Tree? (SEGT)

Problem Link: Practice

Expected Time Complexity

O(N+Q) per testcase

Tutorial

Let’s uncover the truth first, it’s not Segment Tree :stuck_out_tongue:

It’s just a typical Prefix Sum problem. Let’s say pref[i] denotes the sum of populations of all slides from 0 to i. You can start with pf[0]=0 (i.e. use 1-based indexing), then simply do

pref[i] = p[i] + pref[i-1]\ \text{for}\ i=1\ \text{to}\ N

Now, for any query asking for the sum of populations in range [Sf,Sl] the answer will be

pref[Sl] - pref[Sf-1]

Note: If you are using 0-based indexing, then your solution will lead to negative indexing for the queries where Sf=0, causing abnormal behaviour at runtime. You can handle the Sf=0 case explicitly like:

if(Sf==0) answer=pref[Sl];
else answer=pref[Sl]-pref[Sf-1];

Fast Input Output:

  • C++
  • Python (Often submitting the same Python code without fast IO in PyPy might work)
  • Java: Blog 1, Blog 2

It’s good if you always use fast input output for competitive programming (except for interactive problems).

C++ Solution 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    //fast input/output
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll T, N, Q, i, Sf, Sl;
    cin>>T;
    while(T--)
    {
        cin>>N>>Q;
        ll pref[N+1]={0};                   //You can avoid using extra p[] array
        for(i=1;i<=N;++i)
        {
            cin>>pref[i];                       //input population on i-th slide
            pref[i]+=pref[i-1];                 //update prefix sum
        }

        while(Q--)                              //process queries
        {
            cin>>Sf>>Sl;
            cout<<pref[Sl]-pref[Sf-1]<<"\n";    //use prefix sums to calculate result
        }
    }
    return 0;
}
Python 3 Solution 
for _ in range(int(input())):
    n,q=map(int,input().split())
    pref=[0] + list(map(int,input().split()))

    #compute prefix sums
    for i in range(1,n+1):
        pref[i]+=pref[i-1]
    
    #process queries
    for _ in range(q):
        Sf,Sl=map(int,input().split())
        print(pref[Sl]-pref[Sf-1])

7. Guess the number (LFTR)

Problem Link: Practice

Expected Time Complexity

O(N \log \log N + T), where N=10^7

Tutorial

Problem: Given a number N, find the largest factor of N other than itself. Do this for T testcases.

Solution:
We know that the the largest factor of any number N will be

\frac{N}{\text{(Smallest prime factor of N)}}

The only problem is to answer the queries faster than O(\sqrt{N}).

You can modify the Sieve of Eratosthenes to do this. You have to save the smallest prime factor of all numbers from 1 to 10^7.

In Sieve of Eratosthenes, we mark all the factors of a prime number as non prime using Boolean variables. For this problem, you can mark a number as non-prime by storing the current prime number instead of the Boolean value. You can read this article for reference: Least prime factor of numbers till n

Still Getting TLE or any Runtime Error?
  • Instead of doing this process for each test case, you’ve to pre-process this array before answering the testcases. Now you can answer each testcase in O(1).
  • Also, use fast input & output methods since the test data is large.
  • Since N can be large, you should prefer using a global array(or vector).
C++ Solution 
#include<bits/stdc++.h>
using namespace std;

const int maxN=1e7+1;
int spf[maxN];
/*
    -> use global array because the size of array is very large
    -> spf[] is global array, hence all elements will be initialized to 0
    -> after pre-processing, spf[i] will contain smallest prime factor of i
*/

int main()
{
    //fast input output
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T, N, i, j;

    //Pre-Processing
    //Sieve of Eratosthenes
    for(i=2; i<maxN; ++i) if(spf[i] == 0)           //if spf[i]=0 then i is prime
    {
        spf[i] = i;     //since i is prime, i's smallest prime factor is i itself

        //now iterate over all multiples of i < maxN
        for(j=2*i; j<maxN; j+=i)
        {
            //j's smallest prime factor is i if spf[j]=0, else it has already been marked
            if(spf[j] == 0) spf[j]=i;
        }
    }

    //Handle Testcases
    cin>>T;
    while(T--)
    {
        cin>>N;
        cout<<(N/spf[N])<<"\n";
        //print the largest factor, use \n instead of endl to avoid unnecssary flushing
    }
    return 0;
}
Python 3 Solution 
N=10**7+1

#pre-processing | Sieve of Eratosthenes
spf=[1 if i&1 else 2 for i in range(N)]
'''
-> mark all numbers odd from 1 to N as prime by setting spf[i]=1 for all i
-> mark smallest factor as 2 for all even numbers
-> after preprocessing, spf[i] will denote smallest prime factor of i
'''
 
for i in range(3,N,2):              #loop over odd numbers only to reduce the number of iterations
    if spf[i]==1:                   #spf[i]=1 iff i is prime
        spf[i]=i                    #if i is prime then i is smallest prime factor of itself
        i2=2*i

        #Now loop over all off multiples of i and mark spf as i if not marked already
        for j in range(i*i,N,i2):   #increment by 2i to skip even multiples of i
            if spf[j]==1:           #spf[j] will be 1 only if it hasn't already been marked
                spf[j]=i            #mark spf[j] as i in this cases, as j is a multiple of i

#Process testcases now
from sys import stdin,stdout
for _ in range(int(stdin.readline())):
    N=int(stdin.readline())
    stdout.write(str(N//spf[N])+'\n')
    #make sure use use integer division(//) and not float division(/)

8. Karen took the kids (KAREN01)

Problem Link: Practice

Expected Time Complexity

O(\log_{\ 2r}{n}) per testcase

Tutorial

This problem is based on the concept of backtracking.

You can start with n, and keep on dividing it. You know that whoever played the last move, had the option to multiply the score at most by r. And the loser must have tried to minimise in this case, and must have multiplied by 2. So, the new value of n becomes

\bigg\lceil\frac{\big\lceil\ n/r \big\rceil}{2}\bigg\rceil

Now continue the same process with this value. If at some point n = 1, then you already know that this was said by Karen, so Karen is the winner, and if at some point n \leq r, then Mascot is the winner.

C++ Iterative Solution 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t,n,r;
    cin>>t;
    while(t--)
    {
        cin>>n>>r;
        while(n>1)
        {
            if(n<=r) break;             //break if Mascot is found winner
            n=ceil((float)n/(float)r);  //divide by r
            n=ceil((float)n/2.0);       //divide by 2
        }
        cout<<(n==1?"K":"M")<<"\n";
    }
    return 0;
}
C++ Recursive Solution (with some implementation hacks) 
#include<bits/stdc++.h>
using namespace std;
bool backtrack(int n,int r)
{
    //base cases
    if(n==1) return 0;              //return 0 if Karen is winner
    if(n<=r) return 1;              //return 1 if Mascot is winner

    n = ( (n+r-1)/r + 1 ) / 2;      //update n
    /*Hack 1: Avoid typecasting for ceil division
        (a+b-1)/b gives same result as ceil((float)a/b)
        You can try to prove this :)
    */

    return backtrack(n,r);          //backtrack with new value of n
}
int main()
{
    int t,n,r;
    string ans[]={"K\n","M\n"};     //Hack 2: Use array indices to avoid comparison

    cin>>t;
    while(t--)
    {
        cin>>n>>r;
        cout<<ans[backtrack(n,r)];  //Print ans stored at returned index (Hack 2)
    }
    return 0;
}
Python 3 Solution 
for _ in range(int(input())):
    n,r=map(int,input().split())

    winner="K"
    while n>1:
        if n<=r: winner="M"
        n=((n+r-1)//r + 1)//2       #Doubt? Check C++ Recursive Solution
    
    print(winner)

9. Pro Gamer (OPK)

Problem Link: Practice

Expected Time Complexity

O(N) per game

Tutorial

This is an easy version of Tunnel or Road. The editorial for Tunnel and Road is already available here, you can read it for reference.

The number of polluted rivers will be at most 2.

Why ?

You can get all the available players on any of the islands numbered 0,1 or 2 based upon their current position (i.e. a player at island i can go to island i \mod 3 using his jumping ability), without polluting any river.

Now, you just need to move all the players on the same island but at the same time, you want to minimize the number of players to be moved via river. Of Course, the strategy should be to move all players on the island that has the highest population currently.

Notice that any player will use at most 1 river.

Why ?

If required island is 2 islands away say i+2 (or i-2), then he player can jump to island i+3 (or i-3) and use only one river to get to the required island.

Hence, total pollution will be:

N - \text{maximum number of players on any island}

Hidden Trap

Negative Remainders

Make sure you calculate the remainder correctly in case of negative numbers. (Try to print the value of -7 \mod 3 in the language that you are using for submission, the correct answer should be 2, check if you are getting a negative result). To handle negative remainders, you can use any of the following 3 ways:

1. Add 3 to remainder if remainder is negative:

rem = island % 3;
if(rem < 0) rem+=3;

2. Add any large multiple of 3 to island number such that the sum will definitely be positive, then calculate the remainder of this sum:

rem = (island + (long long)3e15) % 3;

3. Add 3 to remainder and again calculate remainder:

rem = (island % 3 + 3) % 3;
C++ Solution 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll C,N,island,i;
    cin>>C;
    while(C--)
    {
        cin>>N;
        ll cnt[3]={0,0,0};
        for(i=0;i<N;++i)
        {
            cin>>island;
            ++cnt[(island + (ll)3e15) % 3];  //handle negative remainder
        }
        ll used=-1, max_players=0;          //total number of polluted rivers = total used islands - 1
        for(i=0;i<3;++i)
        {
            used+=cnt[i]>0;
            max_players=max(max_players,cnt[i]);
        }
        cout<<N-max_players<<" "<<used<<"\n";       //print the required parameters
    }
    return 0;
}
Python 3 Solution 
for _ in range(int(input())):
    n=int(input())
    cnt=[0,0,0]
    for island in map(int,input().split()):
        cnt[island % 3] += 1
    print(n-max(cnt),2-cnt.count(0))

10. Planet Vegeta v1 (CITIES)

Problem Link: Practice

Expected Time Complexity

O(N+M + N\log N) per testcase

Tutorial

This is a typical Depth First Search (DFS) / Disjoint Set Union (DSU) problem based on finding the connected components in a Graph.

DFS approach

For every unexplored city, visit all explorable cities and keep track of the maximum numbered city in this component. You will also need to calculate the sum of populations of all explorable cities. Now, you can maintain a container of these <capital, population> pairs and finally sort it according to the capital and print the required output.

DSU approach

DSU approach: Union the cities based on the edges using the DSU algorithm. While doing the union operation, you can also update the capital and population of the country of representative element. Identify the representative elements of each component, and print the required output based upon the information stored for representative elements.

DFS Solution (C++) 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector <ll> vll;
#define pb push_back

vector <vll> G;
vll p;
vector <bool> visited;

void dfs(ll current_city, ll &capital, ll &population)
{
    visited[current_city] = true;                       //mark current city as visited
    capital=max(capital,current_city);                  //update capital
    population+=p[current_city];                        //update population

    for(ll city:G[current_city]) if(!visited[city])
    {
        dfs(city,capital,population);                   //visit all unvisited neighbours
    }
}

int main()
{
    ll t, n, m, i, j, capital, population;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;                      //input N and M

        //initialization
        p.resize(n+1);
        G.assign(n+1,vll());
        visited.assign(n+1,false);
        vector < pair <ll,ll> > pairs;  //to store <capital,population> pairs

        for(i=1;i<=n;++i) cin>>p[i];    //input population of each city

        //input edges and update adjavency lists
        while(m--)
        {
            cin>>i>>j;
            G[i].pb(j);
            G[j].pb(i);
        }
        
        //if i-th city is not visited then it belongs to a different, unexplored country 
        for(i=1;i<=n;++i) if(!visited[i])
        {
            capital=i;
            population=0;
            dfs(i,capital,population);
            pairs.pb({capital,population});     //add <capital,population> pair to pairs
        }

        sort(pairs.begin(), pairs.end());       //sort array of <capital,population> pairs

        cout<<pairs.size()<<"\n";               //total number of pairs = total countries

        for(auto p:pairs) cout<<p.first<<" ";   //print capitals
        cout<<"\n";
        for(auto p:pairs) cout<<p.second<<" ";  //print populations 
        cout<<"\n";
    }
    return 0;
}
DSU Solution (C++) 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

vector <ll> par, rnk, capital, population;
ll root(ll v)
{
    if(par[v]==v) return v;
    return par[v]=root(par[v]);
}
bool join(ll u,ll v)                        //return true when two components are merged
{
    u=root(u), v=root(v);
    if(u==v) return false;                  //return false if u and v are already in same component
    if(rnk[v]<rnk[u]) swap(u,v);
    if(rnk[u]==rnk[v]) ++rnk[v];
    par[u]=v;
    capital[v]=max(capital[v],capital[u]);  //update capital for new reprsenetative
    population[v]+=population[u];           //update population for new representative
    return true;
}

int main()
{
    ll t,n,m,i,j,v;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;

        //DSU initialization
        par.resize(n+1);
        capital.resize(n+1);
        population.resize(n+1);
        rnk.assign(n+1,0);
        v = n;                              //consider each city as different country initially

        for(i=1;i<=n;++i)
        {
            cin>>population[i];             //input population of each city
            par[i]=capital[i]=i;            //initailize capital & parent
        }
        while(m--)                          //input edges (bidirectional roads)
        {
            cin>>i>>j;
            v-=join(i,j);               
            //if different components are merged then decrement the number of components by 1
        }

        cout<<v<<"\n";                      //print the number of components
        
        vector <pair<ll,ll>> ans;
        //identify capital and population for all the representatives
        for(i=1;i<=n;++i) if(par[i]==i) ans.push_back({capital[i],population[i]});

        //sort and print capital and population for all the representatives
        sort(ans.begin(),ans.end());
        for(auto p:ans) cout<<p.first<<" "; cout<<"\n";
        for(auto p:ans) cout<<p.second<<" "; cout<<"\n";
    }
    return 0;
}

11. Modular Arithmetic Queries 1 (MODQUERY)

Problem Link: Practice

Expected Time Complexity
  • O(1) for +, - , * and ** queries.
  • O(\log B) for ^ queries.
Tutorial

Here are the answers for each type of query, for detailed explanation you can refer Modular Arithmetic Section in summary of CP Session on Basic Maths in CP, conducted by CodeChef YCCE Chapter.

  • Note: Use long long int, since int will overflow in most of the cases.

  • For + queries, answer will be ( A + B ) \mod M
  • For * queries, answer will be (A * B) \mod M
  • For - queries, answer will be \big((A \mod M ) - (B \mod M) + M\big) \mod M
  • For ** queries, answer will be \big((A*B) \mod M) * C\big ) \mod M
  • For ^ queries use O(\log M) Modular Exponentiation.
C++ Solution 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll pow(ll a,ll b, ll m)                                 //returns (a^b) mod m
{
    ll res=1;
    a%=m;
    while(b)
    {
        if(b&1) res=(res*a) % m;
        a=(a*a)%m;
        b/=2;
    }
    return res;
}
int main()
{
    ll Q,A,B,C,M;
    string op;
    cin>>Q;
    while(Q--)
    {
        cin>>op;
        if(op=="**")                                    //** query
        {
            cin>>A>>B>>C>>M;
            cout<< ((A*B)%M * C)%M;
        }
        else
        {
            cin>>A>>B>>M;
            if(op=="+") cout<<(A+B)%M;                  //+ query
            else if(op=="*") cout<<(A*B)%M;             //- query
            else if(op=="-") cout<<(A%M - B%M + M)%M;   //* query
            else cout<<pow(A,B,M);                      //^ query
        }
        cout<<"\n";
    }
    return 0;
}

12. Modular Arithmetic Queries 2 (MODQ2)

Problem Link: Practice

Expected Time Complexity
  • O\big(\log(\max(A,M))\big) for inv queries.
  • O\big(\log(\max(B,M)) + \log M \big) for / queries.
Tutorial

Both inv and / operations are explained in the Modular Arithmetic Section in summary of CP Session on Basic Maths in CP, conducted by CodeChef YCCE Chapter. This should be enough for solving this problem.

Still getting WA?
  • Fermat’s little theorem will only work for prime M. You’ll have to use the Extended Euclidean Algorithm to find the Modular Multiplicative Inverse.
  • For inv queries, answer will not exist only when A and M are not co-primes.
  • For / queries, first you’ve to make A and B co-primes by dividing both A and B by \gcd(A,B). After dividing by gcd, if B and M are not co-primes, then answer will not exist for this query.
C++ Solution 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll inverse(ll a,ll m)
{
    if(m==1) return 0;
    ll x=1, y=0, q, tmp, M=m;
    while(m)
    {
        q=a/m;                  //quotient

        //update a and m
        tmp=m;
        m=a%m, a=tmp;

        //update x and y
        tmp=y;
        y=x-q*y, x=tmp;
    }
    if(a==1) return (x+M)%M;    //gcd is 1
    return -1;                  //gcd is not 1
}
int main()
{
    ll Q,A,B,M;
    string op;
    cin>>Q;
    while(Q--)
    {
        cin>>op>>A;
        if(op=="inv")           //"inv" operation
        {
            cin>>M;
            cout<<inverse(A,M)<<"\n";
        }
        else                    // "/" operation
        {
            cin>>B>>M;
            ll gcd=__gcd(A,B);
            A/=gcd, B/=gcd;
            ll inv = inverse(B,M);
            cout<<(inv==-1? -1: (A*inv)%M)<<"\n";
        }
    }
    return 0;
}

13. Modular Arithmetic Queries 3 (MODQ3)

Problem Link: Practice

Expected Time Complexity
  • O(|A|+|B|) for +,- and * queries.
  • O(|A|+|B|+\log M) for / and ^ queries.
Tutorial

In this problem, the values of A and B are very large and will definitely not fit in long long int, hence you’ll have to consider them as string. But the value of modulus M is fairly small so you can use long long int for M.

Hint 1

Use the following facts:

  • (A+B)\mod M = \big( (A \mod M) + (B \mod M) \big) \mod M
  • (A-B)\mod M = \big( (A \mod M) - (B \mod M) + M\big) \mod M
  • (A*\ B)\mod M = \big( (A \mod M) * (B \mod M) \big) \mod M
Hint 2

Given a large number n in form of a string, and the value of modulus m you can easily calculate the value of a\mod m as:

long long get(string n, long long m)
{
    ll res = 0;
    for(char c:n) res = (res*10 + c-'0') % m;
    return res;
}
Why it works?

Suppose you only had to make an integer from the given string n, then you can do:

int res=0;
for(char c:n) res=res*10 + c-'0';
//c is in ASCII so c-'0' will give the value of c as integer

Here you iterate string from left to right and add current number at the end of res, for example if n=“768”:

  • Initially, res=0
  • 1^{st} iteration (c='7')\ : res = 0\ *10 + ( '7' - '0') = 0\ \ \ +\ 7\ = 7
  • 2^{nd} iteration (c='6'): res=7\ *10+('6'-'0')=70\ \ +6\ =76
  • 3^{rd} iteration (c='8'): res=76*10+('8'-'0')=760+8\ =768

Hence, after the last iteration, the value of res becomes 768.

In the \text{get()} function we’re applying \mod m at every step, hence instead of the actual value of n, we will have the value of n \mod m in res.

Hint 3

M is prime, so you can use Fermat’s little theorem to calculate the inverse in / queries. Also, it is given that M \nmid B, hence inverse will always exist.

Getting WA in subtask 5?

Hmm, maybe test data is wrong for this testcase. :slightly_smiling_face:

BTW, what made you think A^B \mod M = (A \mod m) ^ {(B \mod M)} \mod M? Can you prove this? :upside_down_face:

Ok, enough trolling, actual result will be:

A^B \mod M=(A \mod M) ^ {(B \mod (M-1))}\mod M

For proof, refer Exponentiation for very large power under prime modulus given in Modular Arithmetic Section in summary of CP Session on Basic Maths in CP, conducted by CodeChef YCCE Chapter.

C++ Solution 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll get(string n, ll m)                                      //refer editorial for explanation
{
    ll res = 0;
    for(char c:n) res = (res*10ll + c-'0') % m;
    return res;
}
ll pow(ll a, ll b, ll m)                                    //modular exponentiation
{
    ll res=1;
    a%=m;
    while(b)
    {
        if(b&1) res = (res*a)%m;
        a=(a*a)%m;
        b>>=1;
    }
    return res;
}
int main()
{
    //fast input output
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll Q,M,a,b;
    string A,B;
    char op;
    cin>>Q;
    while(Q--)
    {
        cin>>op>>A>>B>>M;
        a=get(A,M), b=get(B,M);
        if(op=='+') cout<<(a+b)%M<<"\n";                    // + query
        else if(op=='-') cout<<(a-b+M)%M<<"\n";             // - query
        else if(op=='*') cout<<(a*b)%M<<"\n";               // * query
        else if(op=='/') cout<<(a*pow(b,M-2ll,M))%M<<"\n";  // / query
        else                                                // ^ query
        {
            b=get(B,M-1ll);                                 //doubt? refer editorial!
            cout<<pow(a,b,M)<<"\n";
        } 
    }
    return 0;
}
1 Like