CMX1P02 - Tripartite String - Code Mates x1 Editorial

PROBLEM LINK:

Contest
Practice

Setter: Uttkarsh Bawankar
Tester: Mayuresh Patle
Editorialist: Uttkarsh Bawankar

DIFFICULTY:

Cakewalk

PREREQUISITES:

Basic Maths, Modulo Arithmetic, LCM

PROBLEM:

Given possibilities of different number of people coming to party, you need to calculate the minimum number of candies to buy so that each person at the party get equal number of candies (≥ 1) and after distributing them, there are always R candies remaining.

QUICK EXPLANATION:

  • We have to find a number which leaves the same remainder when divided by all the possibilities.
  • Answer = lcm( P[0], P[1], P[2], ..... , P[n]) + R

EXPLANATION:

  • Lets start by building our logic from 1 possibility. Let’s say 3 people are coming and we need to save 2 candies at the end. So, in order to distribute equal candies we will buy 1 for each and then 2 extra, in total 5.
  • But now suppose that there are 2 possibilities, 3 and 2. You have to save 1 candy at the end. Now if you buy 1 candy for each and 1 extra according to 3, then you will have to buy 3+1 = 4 candies. But this will fail in 2nd case.
  • So in conclusion, we just have to find a number which leaves the same remainder when divided by all the possibilities.
  • i.e. the Answer = lcm( P[0], P[1], P[2], ..... , P[n]) + R

SOLUTIONS:

Setter's Solution
import math
import sys
t= int(input())
for _ in range(t):
    n = int(input())
    l = list(map(int, input().split()))
    r = int(input())
    ans = l[0]
    for i in range(1, len(l)):
        d = math.gcd(int(ans), int(l[i]))
        ans *= l[i]
        ans /= d
        ans = int(ans)
    ans += r
    print(ans) 
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int T,n,r,gcd,lcm,people;
    cin>>T;
    while(T--)
    {
        cin>>n;
 
        //initially, lcm = first element in list
        cin>>lcm;
        --n;                        //decrement count
 
        while(n--)
        {
            cin>>people;
            gcd=__gcd(lcm,people);
            lcm=(lcm*people)/gcd;   //update lcm
        }
 
        cin>>r;
        cout<<lcm+r<<"\n";          //answer is lcm + r
    }
    return 0;
}
1 Like

Can anyone please explain why this didn’t work?

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> ip;
typedef vector vi;
typedef vector vll;
typedef vector vip;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t;cin>>t;
while(t--){
    int n;cin>>n;
    vi a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    
    int m = a[0];

    for(int i=1;i<n;i++){
        m = (m*a[i])/__gcd(m,a[i]);
    }
    
    int r;cin>>r;
    cout<<(m)+r<<endl;
}
return 0;

}

Integer overflow is happening for the lcm m that you have defined.
Consider changing the data type of vector and m from int to long int.

You are right. Thanks man!!