COPAR - Editorial

PROBLEM LINK:

Practice
Contest

Setter: Mohammed Ehab
Tester: Ramazan Rakhmatullin
Editorialist: Ishmeet Singh Saggu

DIFFICULTY:

Easy

PREREQUISITES:

Difference Array and Sieve of Eratosthenes

PROBLEM:

Given a sequence a_1, a_2, ..., a_N, you have to find the smallest index l such that the product of elements from index 1 to l and product of elements from index l+1 to N is coprime with each other.

EXPLANATION:

Two numbers x and y are said to be coprime if gcd(x, y) = 1.

let us make a list of all prime numbers P, such that for every prime number P_i, there exist at least one number in the sequence a which has P_i as its prime factor.

Now to satisfy the condition for the partition, we have to make sure that for every prime number P_i, the numbers in the sequence a which have P_i as a prime factor are one side of the partition. Why? because if they are present in both prefix and suffix, then when we multiply the numbers together in prefix and in the suffix, we will have at least P_i which is present in both numbers making their gcd \neq 1.

So using the sieve(using SPF, smallest prime factor) we will prime factorize all the numbers in the sequence a and make their list. For each prime number P_i, we will find out the minimum and maximum index of the number in the sequence a which has P_i as their prime factor. Suppose for a P_i it is L and R, then all the indexes from L to R-1 can’t be the answer (because then the prime number P_i will be present in both the partition). So all the indexes from L to R-1 are bad indexes and can’t be the answer. So we can mark these bad indexes for all prime numbers P_i efficiently using the difference array and after marking indexes for all prime number P_i we will find out the smallest index which is not marked and it will be our answer.

TIME COMPLEXITY:

  • We can precompute the SPF(smallest prime factor) for factorization.
  • Time complexity per test case is O(N * log(max(a_i))).

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define MX 100000
int f[MX+5],l[MX+5],cum[MX+5];
int main()
{
	int t;
	scanf("%d",&t);
	while (t--)
	{
		int n;
		scanf("%d",&n);
		for (int i=2;i<=MX;i++)
		{
			f[i]=0;
			l[i]=0;
		}
		for (int i=1;i<=n;i++)
		{
			int a;
			scanf("%d",&a);
			for (int j=2;j*j<=a;j++)
			{
				if (a%j==0)
				{
					if (!f[j])
					f[j]=i;
					l[j]=i;
					while (a%j==0)
					a/=j;
				}
			}
			if (a!=1)
			{
				if (!f[a])
				f[a]=i;
				l[a]=i;
			}
			cum[i]=0;
		}
		for (int i=2;i<=MX;i++)
		{
			cum[f[i]]++;
			cum[l[i]]--;
		}
		for (int i=1;i<n;i++)
		{
			cum[i]+=cum[i-1];
			if (!cum[i])
			{
				printf("%d\n",i);
				break;
			}
		}
	}
}
Tester's Solution
#include <bits/stdc++.h>
 
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wunused-const-variable"
#define popcnt(x) __builtin_popcount(x)
 
#define fr first
 
#define sc second
 
#define m_p make_pair
 
#define low_bo(a, x) lower_bound(a.begin(), a.end(), x) - a.begin()
 
#define up_bo(a, x) upper_bound(a.begin(), a.end(), x) - a.begin()
 
#define unique(a) a.resize(unique(a.begin(), a.end()) - a.begin())
 
#define popcnt(x) __builtin_popcount(x)
 
//#include <ext/pb_ds/assoc_container.hpp>
 
//using namespace __gnu_pbds;
 
//gp_hash_table<int, int> table;
 
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
//float __attribute__((aligned(32)))
 
/*char memory[(int)1e8];
char memorypos;
 
inline void * operator new(size_t n){
    char * ret = memory + memorypos;
    memorypos += n;
    return (void *)ret;
}
 
inline void operator delete(void *){}
*/
 
using namespace std;
 
typedef long long ll;
 
typedef unsigned long long ull;
 
typedef long double ld;
 
typedef unsigned int uint;
 
template<typename T>
class Modular {
public:
    using Type = typename decay<decltype(T::value)>::type;
 
    constexpr Modular() : value() {}
 
    template<typename U>
    Modular(const U &x) {
        value = normalize(x);
    }
 
    static Type inverse(Type a, Type mod) {
        Type b = mod, x = 0, y = 1;
        while (a != 0) {
            Type t = b / a;
            b -= a * t;
            x -= t * y;
            swap(a, b);
            swap(x, y);
        }
        if (x < 0)
            x += mod;
        return x;
    }
 
    template<typename U>
    static Type normalize(const U &x) {
        Type v;
        if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
        else v = static_cast<Type>(x % mod());
        if (v < 0) v += mod();
        return v;
    }
 
    const Type &operator()() const { return value; }
 
    template<typename U>
    explicit operator U() const { return static_cast<U>(value); }
 
    constexpr static Type mod() { return T::value; }
 
    Modular &operator+=(const Modular &other) {
        if ((value += other.value) >= mod()) value -= mod();
        return *this;
    }
 
    Modular &operator-=(const Modular &other) {
        if ((value -= other.value) < 0) value += mod();
        return *this;
    }
 
    template<typename U>
    Modular &operator+=(const U &other) { return *this += Modular(other); }
 
    template<typename U>
    Modular &operator-=(const U &other) { return *this -= Modular(other); }
 
    Modular &operator++() { return *this += 1; }
 
    Modular &operator--() { return *this -= 1; }
 
    Modular operator++(int) {
        Modular result(*this);
        *this += 1;
        return result;
    }
 
    Modular operator--(int) {
        Modular result(*this);
        *this -= 1;
        return result;
    }
 
    Modular operator-() const { return Modular(-value); }
 
    template<typename U = T>
    typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type &operator*=(const Modular &rhs) {
#ifdef _WIN32
        uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
        uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;
        asm(
        "divl %4; \n\t"
        : "=a" (d), "=d" (m)
        : "d" (xh), "a" (xl), "r" (mod())
        );
        value = m;
#else
        value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
#endif
        return *this;
    }
 
    template<typename U = T>
    typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value, Modular>::type &
    operator*=(const Modular &rhs) {
        int64_t q = static_cast<int64_t>(static_cast<long double>(value) * rhs.value / mod());
        value = normalize(value * rhs.value - q * mod());
        return *this;
    }
 
    template<typename U = T>
    typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type &operator*=(const Modular &rhs) {
        value = normalize(value * rhs.value);
        return *this;
    }
 
    Modular &operator/=(const Modular &other) { return *this *= Modular(inverse(other.value, mod())); }
 
    template<typename U>
    friend const Modular<U> &abs(const Modular<U> &v) { return v; }
 
    template<typename U>
    friend bool operator==(const Modular<U> &lhs, const Modular<U> &rhs);
 
    template<typename U>
    friend bool operator<(const Modular<U> &lhs, const Modular<U> &rhs);
 
    template<typename U>
    friend std::istream &operator>>(std::istream &stream, Modular<U> &number);
 
private:
    Type value;
};
 
template<typename T>
bool operator==(const Modular<T> &lhs, const Modular<T> &rhs) { return lhs.value == rhs.value; }
 
template<typename T, typename U>
bool operator==(const Modular<T> &lhs, U rhs) { return lhs == Modular<T>(rhs); }
 
template<typename T, typename U>
bool operator==(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) == rhs; }
 
template<typename T>
bool operator!=(const Modular<T> &lhs, const Modular<T> &rhs) { return !(lhs == rhs); }
 
template<typename T, typename U>
bool operator!=(const Modular<T> &lhs, U rhs) { return !(lhs == rhs); }
 
template<typename T, typename U>
bool operator!=(U lhs, const Modular<T> &rhs) { return !(lhs == rhs); }
 
template<typename T>
bool operator<(const Modular<T> &lhs, const Modular<T> &rhs) { return lhs.value < rhs.value; }
 
template<typename T>
Modular<T> operator+(const Modular<T> &lhs, const Modular<T> &rhs) { return Modular<T>(lhs) += rhs; }
 
template<typename T, typename U>
Modular<T> operator+(const Modular<T> &lhs, U rhs) { return Modular<T>(lhs) += rhs; }
 
template<typename T, typename U>
Modular<T> operator+(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) += rhs; }
 
template<typename T>
Modular<T> operator-(const Modular<T> &lhs, const Modular<T> &rhs) { return Modular<T>(lhs) -= rhs; }
 
template<typename T, typename U>
Modular<T> operator-(const Modular<T> &lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
 
template<typename T, typename U>
Modular<T> operator-(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) -= rhs; }
 
template<typename T>
Modular<T> operator*(const Modular<T> &lhs, const Modular<T> &rhs) { return Modular<T>(lhs) *= rhs; }
 
template<typename T, typename U>
Modular<T> operator*(const Modular<T> &lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
 
template<typename T, typename U>
Modular<T> operator*(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) *= rhs; }
 
template<typename T>
Modular<T> operator/(const Modular<T> &lhs, const Modular<T> &rhs) { return Modular<T>(lhs) /= rhs; }
 
template<typename T, typename U>
Modular<T> operator/(const Modular<T> &lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
 
template<typename T, typename U>
Modular<T> operator/(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) /= rhs; }
 
template<typename T, typename U>
Modular<T> power(const Modular<T> &a, const U &b) {
    assert(b >= 0);
    Modular<T> x = a, res = 1;
    U p = b;
    while (p > 0) {
        if (p & 1) res *= x;
        x *= x;
        p >>= 1;
    }
    return res;
}
 
template<typename T>
bool IsZero(const Modular<T> &number) {
    return number() == 0;
}
 
template<typename T>
string to_string(const Modular<T> &number) {
    return to_string(number());
}
 
template<typename T>
std::ostream &operator<<(std::ostream &stream, const Modular<T> &number) {
    return stream << number();
}
 
template<typename T>
std::istream &operator>>(std::istream &stream, Modular<T> &number) {
    typename common_type<typename Modular<T>::Type, int64_t>::type x;
    stream >> x;
    number.value = Modular<T>::normalize(x);
    return stream;
}
 
const int md = 1e9 + 7;
 
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
 
ll sqr(ll x) {
    return x * x;
}
 
int mysqrt(ll x) {
    int l = 0, r = 1e9 + 1;
    while (r - l > 1) {
        int m = (l + r) / 2;
        if (m * (ll) m <= x)
            l = m;
        else
            r = m;
    }
    return l;
}
 
#ifdef ONPC
mt19937 rnd(513);
mt19937_64 rndll(231);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
    mt19937_64 rndll(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
 
template<typename T>
T gcd(T a, T b) {
    return a ? gcd(b % a, a) : b;
}
 
int gcdex(int a, int b, int &x, int &y) {
    if (a == 0) {
        x = 0;
        y = 1;
        return b;
    }
    int x1, y1;
    int ret = gcdex(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return ret;
}
 
void setmin(int &x, int y) {
    x = min(x, y);
}
 
void setmax(int &x, int y) {
    x = max(x, y);
}
 
void setmin(ll &x, ll y) {
    x = min(x, y);
}
 
void setmax(ll &x, ll y) {
    x = max(x, y);
}
 
const ll llinf = 4e18 + 100;
 
const ld eps = 1e-9, PI = atan2(0, -1);
 
const int maxn = 1e5 + 100, maxw = 2e6 + 1111, inf = 1e9 + 100, sq = 450, LG = 18, mod = 1e9 + 933, mod1 = 1e9 + 993;
 
int p[maxn], tot[maxn], cs[maxn];
 
int main() {
#ifdef ONPC
    freopen("../a.in", "r", stdin);
    freopen("../a.out", "w", stdout);
#else
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
#endif // ONPC
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    for (int i = 2; i < maxn; i++)
        if (p[i] == 0) {
            for (int j = i; j < maxn; j += i)
                if (p[j] == 0)
                    p[j] = i;
        }
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<vector<int>> a(n);
        vector<int> all;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            while (x > 1) {
                int w = p[x];
                while (x % w == 0)
                    x /= w;
                a[i].push_back(w);
                all.push_back(w);
                tot[w]++;
            }
        }
        int cur = 0;
        for (int i = 0; i < n; i++) {
            for (int j : a[i]) {
                if (cs[j] == 0)
                    cs[j] = 1, cur++;
                tot[j]--;
                if (tot[j] == 0)
                    cur--;
            }
            if (cur == 0) {
                cout << i + 1 << '\n';
                break;
            }
        }
        for (int i : all)
            tot[i] = 0, cs[i] = 0;
    }
} 
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

const int maxA = 1e5+1;

vector<int> spf(maxA, -1);

void computeSPF() {
	spf[1] = 1;
	for(int i = 2; i < maxA; i ++) {
		if(spf[i] == -1) {
			for(int j = i; j < maxA; j += i) {
				if(spf[j] == -1) spf[j] = i;
			}
		}
	}
}

void Solve() {
	int N;
	cin >> N;
	vector<int> marking(N, 0); // difference array, for marking restricted index.
	vector<pair<int, int>> prime_range(maxA, {-1, -1});
	for(int i = 0; i < N; i ++) {
		int x;
		cin >> x;
		while(x > 1) {
			int prime = spf[x];
			if(prime_range[prime].first != -1) {
				prime_range[prime].second = i;
			}
			else prime_range[prime] = {i, i};
			x /= prime;
		}
	}
	
	// Now marking the indexes with difference array which can't be answer;
	for(int i = 2; i < maxA; i ++) {
		if(prime_range[i].first == -1) continue;
		int L = prime_range[i].first;
		int R = prime_range[i].second;
		// All the index from [L, R-1] can't be the "l" as the answer
		marking[L] ++;
		marking[R] --;
	}
	for(int i = 1; i < N; i ++) {
		marking[i] += marking[i-1];
	}
	for(int i = 0; i < N; i ++) {
		if(marking[i]) continue;
		cout << i+1 << "\n";
		return;
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	computeSPF();

	int test_case;
	cin >> test_case;
	for(int i = 1; i <= test_case; i ++) {
		Solve();
	}
}

VIDEO EDITORIAL:

Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed. :smile:

14 Likes

nice questions

See the constrains, a[i] can be upto 1e5, so in the worst case, say just for the value of n = 20. it cannot be stored even in long long and n can be upto 1e5.

1 Like

Thanks! Was missing something obvious. Got it now!

1 Like

My solution isn’t really efficient, but I wanted to know why my solution gets AC in all but RE SIGFPE in last task of subtask 3. Is this because of Memory limit?
https://www.codechef.com/viewsolution/39234496

Could anyone tell me why using recursive function for GCD is giving me Runtime Error.
static long gcd(long a, long b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
For reference here is my java solution Link to code

Due to overflow, A_i <= 1e5 and N<= 1e5. Therefore, Multiplying that bigger values will overflow.

1 Like

Editorial’s approach is much simpler.
Here is a different approach. Here L is the optimal end for the first segment that we have to print (i.e. the answer), first segment means a[1:L] and second segment is a[L+1:N]

For subtask 1 and 2

  • Notice that if there are two numbers x and y and gcd(x,y)>1, then x and y can’t lie in same segment. So for the first element find out R, index of the rightmost element such that gcd(a_1,a_R)>1. After that increase R if you can for every element in [1:R]. Final R is the smallest L you can get.

  • My submission

For subtask 3

  • S_{l,r} - set of primes which divide the numbers in a[l:r].

  • If there exists some valid l then S_{1,l} and S_{l+1,N} are disjoint.

  • To find such partition we maintain a frequency array for prime numbers and first fill it for all the numbers, now we’ll update it as we move from N to 1, by decreasing contribution of current number’s prime factors.

  • Keep a running set used which contains prime numbers which have been used till now but their frequency is not zero yet.

  • If at some index used becomes empty, then this index is a valid start for the second segment.

  • Sanity check: used is always empty at the beginning, thus N is always a valid start for second segment, as it is guaranteed that a solution exists for input data.

  • Submission

2 Likes

Can anyone tell me, what is the mistake in my code for COPAR problem ?

Code explanation :
I simply check all prime factors of i-th element of the array, and mapped them in a map.
If the prime factor is not mapped, then mapped to that prime factor, else if that prime factor is already mapped into the map, then I mark that i-th index.
And output is that marked i-th index.
Simple logic of the code that, where I find repeated prime factor, my answer is that index.

Code link is here - https://www.codechef.com/viewsolution/39247254

This approach is wrong because in many cases you will venture into second segment and there is no way for you to know that in your algorithm.
Here is one example:

6
2 2 2 3 3 3
1 Like

Thanks Sir, I got my mistake…

1 Like

I used following approach for COPAR but is showing runtime error pls check this code
#include<bits/stdc++.h>
using namespace std;
main()
{ int t;
cin>>t;
while(t–)
{ int n,mux=1,i,j,cp=1,op,cop;
cin>>n;
int a[n];
for(i=1;i<=n;i++)
cin>>a[i];
for(i=1;i<=n;i++)
mux=muxa[i];
for(i=1;i<n;i++)
{ cp=cp
a[i];
op=mux/cp;
if(__gcd(cp,op)==1)
{cout<<i<<endl;
break;}

}

}

}

A simpler solution which does not require sieve or difference array:

Quick explanation:

Try every split point from left to right and the first good one will be our answer, where a split point considered to be good if the product of the elements on the left of it and product of the elements on the right of it are coprime.

More Details:

Go through the elements from left to right starting from the second one and for each one of them do the following:

Let our index be i and the array be a and its size is n,

1. Factorize a[ i - 1 ] and for each factor mark it as visited in some boolean array

2. We will try to make the split between the i-th and (i - 1)-th element, so we will iterate from i to n, let our index for this iteration be j and then do the following:

2.1. Factorize a[ j ] and for each factor look up if it is marked before as visited, If it is visited we will break because we can not split right before the i-th element
Otherwise we continue to step 2.2.

2.2. Now we know that the j-th element can be in our right halve of the split, so we need to check the (j + 1)-th element (if it is existed)

3. If we checked every element on the right halve (from i to n) without breaking, then we can split right before the i-th element so our answer will be i since we are iterating over the split point from left to right, and then we break because we found an answer and we do not need to check any other split points

Code:

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a) {
      cin >> x;
    }
    vector<vector<int>> fc(n); // fc[i] stores the prime numbers which divide a[i] in increasing order
    for (int i = 0; i < n; i++) { // calculating fc[i] for each a[i]
      for (int x = 2; x*x <= a[i]; x++) {
        bool bl = false;
        while (a[i]%x == 0) {
          if (!bl) {
            fc[i].push_back(x);
            bl = true;
          }
          a[i] /= x;
        }
      }
      if(a[i] > 1) fc[i].push_back(a[i]);
    }
    int l = n + 1; // this variable will store our final answer
    vector<bool> vis(100005, false); // in this array we will mark factors as visited, note that its initial state is: each element is 0, which means that nothing is marked as visited
    // Note that this won't get Time Limit Exceeded because we are breaking early most of the times.
    for (int i = 1; i < n; i++) { // This will iterate over the split point
      for (const auto& x : fc[i - 1]) vis[x] = true; // Marking the factors of a[i - 1] as visited
      bool bll = true; // This boolean will store if we can split right before the ith element
      for (int j = i; j < n; j++) { // Iterate over the right halve
        bool bl = true; // This will store if the jth element can be a part of the right halve
        for (const auto& x : fc[j]) { // In this iteration we will find out if any of the prime factors of the jth element is visited before
          if (vis[x]) {
            bl = false;
            break; // Note that we break.
          }
        }
        if (!bl) {
          bll = false;
          break; // Note that we break.
        }
      }
      if (bll) { // We found an answer (that means we can split between the ith and the (i - 1)th elements).
        l = i;
        break; // Note that we break.
      }
    }
    cout << l << '\n';
  }
  return 0;
}
2 Likes

int gcd(int a,int b){
if (a == 0)
return b;
return gcd(b % a, a);
}
int d(vector a,int i,int n){
int x=1;
for(;i<n;i++)
x=(x*a[i]);
return x;
}
int solve(vector a,int n){
int i=0;
for(;i<n-1;i++){
int l=d(a,0,i+1),r=d(a,i+1,n);
if(__gcd(l,r)==1){
break;
}
}
return i+1;
}
int main(){
int t;
cin>>t;
while(t–){
int n;
cin>>n;
vectora(n);
rep(i,0,n)
cin>>a[i];
cout<<solve(a,n)<<’\n’;
}
}
why this approach is not working in cpp but i saw same approach in python which is working
python code:
def prod(myList) :

result = 1
for x in myList:
    result = result * x
return result

def d(a, b):

if a == 0:
    return b
return d(b % a, a)

def L(n, seq):

for i in range(n-1):
    a = prod(seq[:i+1])
    b = prod(seq[i+1:])
    if d(a, b) == 1:
        return i + 1
    else:
        continue

T = int(input())

for _ in range(T):

n = int(input())
sequence = list(map(int, input().split()))

print(L(n, sequence))

another simple approach after calcuting prime factors .
1.keep note of frequencies of primes .
2.start from left and add prime factors of a_i to set left
and decrease count in frequencies and maintain record of distinct primefactors of a_i.
3.check whether the frequencies of disctinct primefactors of a_i is 0
4.find sum of remaining primes in right and size of left and check whether they are equal to total count from beginning
https://www.codechef.com/viewsolution/39275146

Could somebody post some corner cases? Getting WA despite having a working program

Why can’t we simply use the approach of maintaining the product subarray from the left and right side and checking the gcd of ith elements in each of these arrays , if we get gcd = 1, we break the loop and that index would be our ans ?

Link to my code : https://www.codechef.com/viewsolution/39245316

You can’t do that because maximum product will be (10^5)^(10^5) which will overflow. You can’t do modulus also because that will change the result and it is not mentioned to do modulus.

1 Like