ARRGRAPH problem gives Wrong Answer although code and output is correct

help
1

I am solving Snackdown’s practice problem ARRGRAPH. I use python and wrote the correct code. I tested it for boundary cases and exceptions and it works fine. Yet, I am getting the wrong answer.
Here is my code. Hope someone will tell me whats going on.


# cook your dish here
from math import gcd
for t in range(int(input())):
    N = int(input())
    A = list(map(int, input().split()))
    primes = []
    others = []
    max_prime = 0
    B = []
    temp = A[0]
    spcl = 0
    while A:
        B.append(A[0])
        if A[0] == temp:
            spcl += 1
        if ((A[0] - 1)/6).is_integer() or ((A[0] + 1)/6).is_integer() or A[0] == 2 or A[0] == 3:
            prime = A.pop(0)
            if prime > max_prime:
                max_prime = prime
            primes.append(prime)
        elif A[0] < max_prime:
            A.pop(0)
        else:
            others.append(A.pop(0))
            
    i = 0
    while i < len(others):
        for prime in primes:
            if gcd(others[i], prime) == 1:
                others.pop(i)
                i -= 1
                break
        i += 1
    
    if len(others) == 0 and spcl != N:
        print(0)
    elif len(others) == 0 and spcl == N:
        print(1)
        if B[0] == 47:
            B[0] = 41
        else:
            B[0] = 47
    else:
        print(1)
        B[0] = 47
    print(*B)
2

I’ve only glanced at the question, but this seems to be a valid input for which your solution seems to give the wrong answer(?):

1
2
5 25
3

Ok, so I updated my code to exclude numbers, 25, 35 and 49 which wrongly satisfied the primality test. But I still get wrong answer. Any other special cases?

4

Post your updated code, please :slight_smile:

Edit:

While we’re waiting - consider the test input:

1
2
10 21
1 Like
6 

# cook your dish here
from math import gcd
for t in range(int(input())):
    N = int(input())
    A = list(map(int, input().split()))
    primes = []
    others = []
    max_prime = 0
    B = []
    temp = A[0]
    spcl = 0
    while A:
        B.append(A[0])
        if A[0] == temp:
            spcl += 1
        if ((((A[0] - 1)/6).is_integer() or ((A[0] + 1)/6).is_integer()) and A[0] not in [25, 35, 49]) or A[0] == 2 or A[0] == 3:
            prime = A.pop(0)
            if prime > max_prime:
                max_prime = prime
            primes.append(prime)
        elif A[0] < max_prime:
            A.pop(0)
        else:
            others.append(A.pop(0))
            
    i = 0
    while i < len(others):
        for prime in primes:
            if gcd(others[i], prime) == 1:
                others.pop(i)
                i -= 1
                break
        i += 1
    
    if len(others) == 0 and spcl != N:
        print(0)
    elif len(others) == 0 and spcl == N:
        print(1)
        if B[0] == 47:
            B[0] = 41
        else:
            B[0] = 47
    else:
        print(1)
        B[0] = 47
    print(*B)
7

Thanks - see my Edit :slight_smile:

8

Yes, I did. Thanks for pointing out the mistake in my code. I was checking for primes. But two coprimes need not necessarily be prime. I now have an idea how I should go about. Thanks again.

1 Like
9

A nice input set to consider:

1
4
48 35 45 28