RESTORE - Editorial

editorial
, , ,
22

can you please explain the logic, and how you came up with this?

I am not able to get logic by @emotiological, though he has explained here RESTORE - Editorial - #13 by emotiological,
can someone explains me in more depth or on call or just wanted to explain somehow?

23
1 Like
24

ohh bro, you made video for me, thanks a lot,
I understand now, why people say, community of competitive-programming is helpful…
thanks.

25

It’s because your implementation takes too time. You go till n/2 values to check if it’s a prime number or not.There are two more optimizations fo it.

  1. It is sufficient to go till sqrt(n) (btw u’ll get tle if u do this for this problem)
    2)sieve algorithm (U can use this , it will be under timelimits).
26

I am getting Runtime error(SIGSEV) and i can’t figure out why!
#include<bits/stdc++.h>
#include<math.h>
#define MAXX 1000000
#define MAXY 100020
using namespace std;

int main()
{
long t;
cin>>t;
long x=t;
bool pr[MAXX];
long ans[t][MAXY]={{0,0}}; // prime sieve logic
pr[0]=0;
pr[1]=0;
for(long i=2;i<MAXX;i++)//N
{
pr[i]=1;
}
for(long i=2;i<sqrt(MAXX);i++)
{
if(pr[i]==1)
{
for(long j=i*i;j<MAXX;j+=i)
{
pr[j]=0;
}
}
} // prime sieve logic ends
while(x>0) //N
{
long n;
cin>>n;
long brr[n];
for(long i=0;i<n;i++)//N
{
cin>>brr[i]; /// input sequence
}

long k=0;
for(long i=0;i<n;i++)//N2  // filling prime numbers in the ans array.
{
  while(ans[t-x][i]==0)
  {
    if(pr[k]==1)
    {
      ans[t-x][i]=k;
    }
    k++;
  }
}

for(long i=0;i<n;i++) //actual logic
{
  if(i!=brr[i]-1)
  {
    ans[t-x][i]=ans[t-x][brr[i]-1];
  }
}
x--;

}
for(long i=0;i<t;i++)//printing the ans
{
for(int j=0;ans[i][j]!=0;j++)
{
cout<<ans[i][j]<<" ";
}
cout<<endl;
}
return 0;
}

27

Even though I know Number Theory Concept , I was Not able to come up Logic/Solution for the Problem. Is there any Observation or Pattern I’m missing or I have not practiced . If there is Similar question in past which has similar Approach do please drop the Link.