Please find why codechef is showing wrong answer for my code

help
1

include <bits/stdc++.h>
using namespace std;
bool isPrime(int num) {
if (num <= 1)
return false;
for (int i = 2; i * i <= num; i++) {
if (num % i == 0)
return false;
}
return true;
}
void find(int n, vector& primes) {
for (int i = 2; i <= n; i++) {
if (isPrime(i))
primes.push_back(i);
}
}
int main() {
int t;
cin >> t;
while (t–) {
long long int n;
cin >> n;
vector primes;
if(n<4){
cout<<-1<<‘\n’;
}
else{
find(n, primes);
int s = primes.size();
int a = n;
for (int i = s - 1; i >= 0; i–) {
if (primes[i] <= n - 2) {
a = primes[i];
break;
}
}
vectorans;
for( int i = a+1; i<=n; i++){
ans.push_back(i);
}
int newsize = n - ans.size();
for ( int i = 1; i<=newsize; i++ ){
ans.push_back(i);
}
for(auto i :ans){
cout<<i<<" ";
}
cout<<endl;
}
}
return 0;
}

Prime Permutation Practice Coding Problem - CodeChef

2

You can take any testcase and than find result given by my code than check output was correct but still wrong ans…
if anyone find any testcase that give wrong ans than mention it…

3

You code makes three assumptions:

  1. The biggest prime or last element is by any reason the difference that works for any N (how did you concluded that?)

  2. Two progressions are enough to built the ans with any N:
    [prime+1, n] + [1, prime]

  3. If the first progression works, then the second as well.

None of those assumptions are ok.

It will fail on N = 6, and likely in most of the biggers than 7

4

for N = 10 output is ```
8 9 10 1 2 3 4 5 6 7

and for N = 6 output is 
4 5 6 1 2 3
I think both of them are correct according to given condition
5

I mean, you can get to an answer by brute force. The problem is that sometimes that specific approach will fail to some N

Your code outputs this for N = 11:
[ 8, 9, 10, 11, 1, 2, 3, 4, 5, 6, 7]

This is the thing.
You cleverly spotted that you can split a progression in two parts. But did you spot this?

If an answer for N=4 is:
[3, 4, 1, 2]

Why can’t N=8 be this?
[3, 4, 1, 2, 7, 8, 5, 6]

Instead of 2 progessions, I made 4 following the same logic, but using progressions I knew they were going to work.

For N = 11, my code output this:
[3, 4, 5, 6, 7, 1, 2, 10, 11, 8, 9]

That was enough hit.
Here is my solution:

#include <bits/stdc++.h> 
#define ll long long 
using namespace std; 

void solve(){ 
    vector<ll> S4 = {3,4,1,2};
    vector<ll> S5 = {3,4,5,1,2};
    vector<ll> S6 = {4,5,6,1,2,3};
    vector<ll> S7 = {3,4,5,6,7,1,2};

    ll N;
    cin >> N;
    
    if (N < 4){
        cout << "-1\n";
        return;
    }
    
    ll fours = N/4 - 1;
    ll rem   = N - 4*fours;
    
    vector<ll>* first;
    switch(rem){
        case 4:
            first = &S4;
            break;
        case 5:
            first = &S5;
            break;
        case 6:
            first = &S6;
            break;
        case 7:
            first = &S7;
            break;
    }
    
    for(auto a : *first){
        cout << a << " ";
    }
    for(ll i=0; i<fours; i++){
        for(auto a : S4){
            cout << a+(i*4)+rem << " ";
        }
    }
    cout << "\n";
    
} 

int main() { 
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL); 
    int T; 
 
    cin >> T; 
    while(T--){ 
        solve(); 
    } 
}
1 Like
6

ok…

7

If you are still doubty, this is a numeric problem.

You were actually asked to spot that every 4 numbers you can make an absolute difference of two (prime):

3,4,1,2

If you made enough N, you’ll end up knowing that brute force was taking much time.

A technic is knowing that if you take much time guessing the answer, the answer was easier than you think. Take the easier path.

If you spotted one answer, try generalizing