October Lunchtime 2020 , COPAR , solution [LTIME89]

general
, ,
1

Brute force Python solution (65 marks) : Click Here

Optimised C++ solution using smallest prime factor (100 marks ) : Click Here

Prerequisite: “Prime Factorization using Sieve O(log n) for multiple queries - GeeksforGeeks”

EDIT : For all those who are saying why my brute force c++ (store product and check) , gives WA , this is bcz of overflow of long long int too (for ex take numbers from 1 to 50 means 50! not possible to store)

3 Likes
2

What is wrong with my solution, kindly help me out.

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

void solve(){
int n;
scanf("%d",&n);
long long arr[n];
for(int i =0;i<n;i++)
cin>>arr[i];
long long pro1 = 1,pro2 = arr[0];
for(int i = 1;i<n;i++)
pro1 *= arr[i];
for(int i = 1;i<n;i++){
if(__gcd(pro2, pro1) == 1){
cout<<i<<endl;
return;
}
pro2 *= arr[i];
pro1 /= arr[i];
}
}

int main() {
int t;
scanf("%d",&t);
while(t–){
solve();
}
return 0;
}

3

over flow , take 12 prime numbers.

a = [2,3,5,7,11,13,17,19,23,29,31,37] and it will overflow in C++.

4

What’s worng in this code?

your code goes here

import math
t=int(input())
for x in range(0,t):
n=int(input())
a=[]
v = map(int, input().split())
v=list(v)
a.append(v[0])
for i in range(1,n):
a.append(a[i-1]*v[i])
z=a[n-1]
for i in range(0,n):
if math.gcd(a[i],int(z/a[i])) ==1:
print(i+1)
break

6

Can you please tell, whats wrong with this code even for partial points.
My approach-

  1. For every ith index, store the product of elements to the left to it in left[] and to the right of it in right[]. In other words, calculating the prefix and suffix product for each i.
  2. Traversing both arrays, and checking which index the elements are coprime.
Code 
       ll n;
	cin>>n;
	ll arr[n],brr[n];
	ll i;
	for(i=0;i<n;i++){
		cin>>arr[i];
		brr[i]=arr[i];
	}
	reverse(brr,brr+n);
	 ll left[n-1],right[n-1];
	 for(i=0;i<n-1;i++){
              left[i]=1;
             right[i]=1;
          }
     left[0]=arr[0];
     right[0]=brr[0];
     for(i=1;i<n-1;i++){
            left[i]=left[i-1]*arr[i];
     }
     for(i=1;i<n-1;i++){
            right[i]=right[i-1]*brr[i];
     }
     reverse(right,right+n-1);
     /*for(i=0;i<n-1;i++){
		 cout<<left[i]<<" ";
     }
     cout<<endl;
     for(i=0;i<n-1;i++){
		 cout<<right[i]<<" ";
     }*/
     for(i=0;i<n-1;i++){
		 if(__gcd(left[i],right[i])==1){
			cout<<i+1<<endl;
			 return;
		 }
	 }
      ```

P.S.- ll is long long int

7

explanation of this CodeChef: Practical coding for everyone
or CodeChef: Practical coding for everyone
why do they not pass third subtask?

8

bro overflow , take 100 numbers c++ long long int not able to store that number.

9

Shit, such a silly mistake🤦‍♂️. Thanks though.

1 Like
10

Oh , u did same thing i did before 100 marks solution , u store for each index i there is a map in which the prime factorisation stores of all the prime factors of all previous values and current values similarly from reverse side right ?

See mine : “CodeChef: Practical coding for everyone” (65 marks c++)

But this is wrong obviously it will give tle , to push whole map into each index , costly operation.

11

Just brute force
https://www.codechef.com/viewsolution/39219258

12

This is not brute force , btw your code takes 4 times more time than mine.

13

So, I have written brute force. I have done no optimization.

14

bro brute force method is we have to product the values and all , u submitted in one go this doesn’t mean it is not optimized.