I have done something different, see my solution CodeChef: Practical coding for everyone
1 Like
In the tester’s solution , the vector of prime numbers which consist of prime numbers upto value 10^6 should definately has a size of less than 10^5.
and in the code "pr[b] " is used and b has a range uptil 10^5 , so why does the code work?
Could anyone please explain.
Well, I don’t think that A[i] = N-B[i] (indexing done from 1 to N) works. Let’s take an example
B = [5,2,3,4,5], then A = [1,2,2,1,0] but A[2] divides A[5]. So, B[2] should be 5 but it is 2.
1 Like
yeah,you get it right! , Instead we can use A[i] = (N+1)-B[i] .
hey there, can you please explain how you arrived with that n-x+1 expression ?
1 Like
-> for any i, b[i] >= i
suppose there is a number at a[i], then obviously it should divide itself so the minimum value of max index it can divide is i itself. Though it can be greater than i in case if it divides someone on it’s right side but never smaller than i.
Suppose there is a B[k] which is = k and suppose several positions i on its left side contain B[i] = k .
How can we construct A array ?
We can make all these left side elements that contain k, equal to the value at A[k].
But how we ensure they don’t divide any number after k th position? We will try to keep all the right elements less than A[k].
How?
Since those all A[i] always have value of A[k] which is on their right. One thing we can do is, the more the k the less value we give in A[k].
It will also work if you replace n-x+1 by 1000000 -x
2 Likes
Is
5 2 3 2 5 an invalid input?
Yes
What should be the output for this:
1
5
2 4 3 4 5
will be consider as invalid input
After running this code i got RuntimeError but while submitting got AC,
How ? please Explain…
1 Like
I tried to do the same but I am getting TLE. Can you please review my code.
https://www.codechef.com/viewsolution/39796851
Kunwar Pratap Singh Bro, this logic is best than I have seen others,
can you please explain this logic of (n-x+1)?
edit:
saw your explanation and though I had some difficulty in understanding it, being beginner, but it’s nice and clean and easy to implement solution ever for this problem.
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?
1 Like
ohh bro, you made video for me, thanks a lot,
I understand now, why people say, community of competitive-programming is helpful…
thanks.
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.
- 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).
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;
}
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.