HackerEarth Partition it! problem solution

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.

#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";
    }
}

coding problems solutions