Header Ad

HackerEarth The smallest subsequence problem solution

In this HackerEarth The smallest subsequence problem solution You are given an array A that contains N integer elements. The value A[i] of every element is such that the number of divisors of A[i] is at most 7.

Find the length of the smallest non-empty subsequence of this array such that the product of elements in the subsequence is a perfect square. If no such subsequence exists, then print -1.

A sequence A is a subsequence of an array B if A can be obtained from B by deleting several (possibly, zero or all) elements.

HackerEarth The smallest subsequence problem solution


HackerEarth The smallest subsequence problem solution.

#include <bits/stdc++.h>
using namespace std;
#define MX 1000000
int lp[MX+5],dist[MX+5];
vector<int> d[MX+5],v[MX+5],pr;
vector<vector<int> > e;
int main()
{
pr.push_back(1);
for (int i=2;i<=MX;i++)
{
if (!lp[i])
{
pr.push_back(i);
for (int j=i;j<=MX;j+=i)
lp[j]=i;
}
d[i]=d[i/lp[i]];
auto it=find(d[i].begin(),d[i].end(),lp[i]);
if (it!=d[i].end())
d[i].erase(it);
else
d[i].push_back(lp[i]);
}
int n,ans=1e9;
scanf("%d",&n);
for (int i=0;i<n;i++)
{
int a;
scanf("%d",&a);
if (d[a].empty())
{
printf("1");
return 0;
}
if (d[a].size()==1)
d[a].push_back(1);
e.push_back({d[a][0],d[a][1]});
v[d[a][0]].push_back(i);
v[d[a][1]].push_back(i);
}
for (int i:pr)
{
if (i*i>MX)
break;
for (int j:pr)
dist[j]=0;
queue<pair<int,int> > q;
for (int j:v[i])
{
q.push({j,(e[j][0]==i)});
dist[e[j][0]^e[j][1]^i]=1;
}
while (!q.empty())
{
auto p=q.front();
q.pop();
int node=e[p.first][p.second];
for (int u:v[node])
{
if (u!=p.first)
{
pair<int,int> np(u,(e[u][0]==node));
int nnode=e[np.first][np.second];
if (!dist[nnode] && nnode!=i)
{
q.push(np);
dist[nnode]=dist[node]+1;
}
else
ans=min(ans,dist[node]+dist[nnode]+1);
}
}
}
}
if (ans==1e9)
ans=-1;
printf("%d",ans);
}

Second solution

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1e6 + 14;
vector<int> g[N];
vector<int> pr[N];
int d[N], par[N];

int main() {
ios::sync_with_stdio(0), cin.tie(0);
for (int p = 2; p < N; ++p)
if (pr[p].empty())
for (int i = p; i < N; i += p)
if (pr[i].size() < 2)
pr[i].push_back(p);
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
if (int(sqrt(x)) * int(sqrt(x)) == x)
return cout << 1, 0;
if (pr[x].size() == 2) {
g[pr[x][0]].push_back(pr[x][1]);
g[pr[x][1]].push_back(pr[x][0]);
}
else if (pr[x].size() == 1) {
g[pr[x][0]].push_back(1);
g[1].push_back(pr[x][0]);
}
}
int ans = INT_MAX;
for (int p = 2; p * p < N; ++p)
if (pr[p] == vector{p}) {
memset(d, 63, sizeof d);
queue<int> q({p});
d[p] = 0;
par[p] = -1;
if (count(g[p].begin(), g[p].end(), par[p]) > 1)
return cout << 2, 0;
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto u : g[v])
if (d[u] > d[v] + 1) {
par[u] = v;
d[u] = d[v] + 1;
q.push(u);
}
else if (u != par[v])
ans = min(ans, d[v] + d[u] + 1);
}
}
cout << (ans == INT_MAX ? -1 : ans) << '\n';
}

Post a Comment

0 Comments