In this HackerEarth Partition it! problem solution Tubby the doggu, likes sets which are closed. Your task is to help him/her solve a problem.

Now the task is that you are given a prime number P and an array A of N integers , in which the ith integer is denoted by Ai, 1<=i<=N, 1<=Ai<=P.

You have to partition the set of indices {1,2,3,4,...,N} into a partition of minimum length such that if Closure({Ai}) subset of Closure({Aj}) then i and j must be in different sets of the partition.

Here, i!=j , 1<=i,j<=N.


HackerEarth Partition it! problem solution


HackerEarth Partition it! problem solution.

#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pii pair<int,int>
#define mk make_pair
#define pb push_back
#define eps 1e-12
#define MAXN 200009
using namespace std;
vector<ll> v;
vector<int> ans[MAXN],out_g[MAXN];
ll p;
inline ll fastexpo(ll base,ll expo,ll mod)
{
ll result=1;
while(expo)
{
if(expo%2==1)
{
result=result*base;
result%=mod;
}
base=base*base;
base%=mod;
expo=expo/2ll;
}
return result;
}
inline void fact(ll n)
{
for(ll i=1;i*i<=n;i++)
{
if(n%i==0)
{
v.pb(i);
v.pb(n/i);
}
}
sort(v.begin(),v.end());
}
inline ll find_order(ll x)
{
for(int i=0;i<v.size();i++)
{
ll res=fastexpo(x,v[i],p);
if(res==1)
{
return v[i];
}
}
assert(false);
}
inline bool check_if_prime(ll n)
{
if(n==1||n==0)
{
return false;
}
for(ll i=2;i*i<=n;i++)
{
if(n%i==0)
{
return false;
}
}
return true;
}
int main()
{
// ios_base::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
int t;
cin>>t;
assert(t<=100);
ll s=0;
while(t--)
{
v.clear();
ll n;
cin>>p>>n;
assert(check_if_prime(p));
s=s+n;
assert(p<=1000000000);
assert(p>=2);
assert(n<=1000);
ll a[n+1];
for(int i=1;i<=n;i++)
{
cin>>a[i];
assert(a[i]<p);
assert(a[i]>0);
}
fact(p-1);
pli ord[n+1];
for(int i=1;i<=n;i++)
{
ord[i]=mk(find_order(a[i]),i);
assert(((p-1)%ord[i].first)==0);
}
sort(ord+1,ord+n+1);
int indeg[n+1];
memset(indeg,0,sizeof(indeg));
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(ord[j].first%ord[i].first==0)
{
out_g[i].pb(j);
indeg[j]++;
}
}
}
int dp[n+1],maxx=0;
queue<int> q;
for(int i=1;i<=n;i++)
{
if(indeg[i]==0)
{
maxx=max(maxx,1);
dp[i]=1;
q.push(i);
ans[dp[i]].pb(i);
}
}
while(!q.empty())
{
int x=q.front();
q.pop();
maxx=max(maxx,dp[x]);
for(int i=0;i<out_g[x].size();i++)
{
indeg[out_g[x][i]]--;
if(!indeg[out_g[x][i]])
{
q.push(out_g[x][i]);
dp[out_g[x][i]]=dp[x]+1;
ans[dp[out_g[x][i]]].pb(out_g[x][i]);
}
}
}
cout<<maxx<<"\n";
// for(int i=1;i<=maxx;i++)
// {
// for(int j=0;j<ans[i].size();j++)
// {
// cout<<a[ord[ans[i][j]].second]<<" ";
// }
// cout<<"\n";
// }
//clear
for(int i=0;i<=n;i++)
{
out_g[i].clear();
ans[i].clear();
}
}
assert(s<=25000);
//cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}

Second solution

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int A[1011];
int dp[1011];
ll bpow(ll x,ll n, ll mod) {
ll ans = 1;
while(n>0) {
if(n&1) ans*=x;
x*=x;
ans%=mod;
x%=mod;
n/=2;
}
return ans;
}
int main()
{
int T;
cin >> T;
while(T--) {
int P,N;
cin >> P >> N;
vector<int>divs;
int sz = sqrt(P-1);
int num = P-1;

for(int j=1;j<=sz;j++) {
if(num%j==0) divs.push_back(j), divs.push_back(num/j);
}
sort(divs.begin(),divs.end());
vector<int>periods;
for(int i=0;i<N;i++) {
assert(cin >> A[i]);
assert(A[i]>=1 and A[i]<P);
ll cur = 1;
for(auto d:divs) {
if(bpow(A[i],d,P)==1){
periods.push_back(d);
break;
}
}
}
int maxLen = 0;
sort(periods.begin(),periods.end());
for(int i=N-1;i>=0;i--) {
dp[i] = 1;
for(int j=i+1;j<N;j++) {
if(periods[j] % periods[i] == 0) dp[i] = max(dp[i], dp[j]+1);
}
maxLen = max(maxLen, dp[i]);
}
cout << maxLen << "\n";
}
}