# Help analyzing Randomize Algorithms

F. GCD Groups 2

## What I do understood

The basic idea about what we are doing in below logic (no more than k=9 primes, kill primes etc.).

## What I don’t understand (Analysis Part)

How in this and similar algorithms we find #iterations such that we can pass all the tests or probability of failure is very small (also what is considered small here).

## What I tried so far

Read several blogs, comments related to randomize algorithms, expected value and so on & came back to analyze this multiple times.

Editorial

## Code (Partially similar to editorial with same base idea)

``````#include <bits/stdc++.h>

using namespace std;

int main() {
int n;
scanf("%d", &n);
vector<int> a(n);
for (int &ai : a) { scanf("%d", &ai); }

vector<int> p(n), grp(n);
iota(p.begin(), p.end(), 0);
for (int t=0; t < 45; t++) {
random_shuffle(p.begin(), p.end());
int g1=0, g2=0;
for (int pi : p) {
if (gcd(g1, a[pi]) != g1) {
g1 = gcd(g1, a[pi]);
grp[pi]=1;
} else {
g2 = gcd(g2, a[pi]);
grp[pi]=2;
}
}

if (g1 == 1 and g2 == 1) {
printf("YES\n");
for (int gi : grp) { printf("%d ", gi); }
return 0;
}
}

printf("NO\n");
}
``````