Solution of "Optimal Xor Set" works but not successful on the codechef compiler

1

I think my python code works well for the problem (mentioned in the
subject) and it prints out all the possible solutions. But your compiler
says it doesn’t work. In the question, you asked for all the solutions.
But, I tried one of the successful codes (from your site) in c++14, which
shows only one possible solution, which does not fulfill the requirement.
Would you please check whether my code fails to provide the required
solutions? My code is provided below:

-- coding: utf-8 --

"""

https://www.codechef.com/problems/OPTSET
Optimal Xor Set
@author: shahriar.forhad.eee


"""
import itertools
import numpy as np
from operator import ixor as ix 
from functools import reduce
  
def subsets(s, n):
    return list(itertools.combinations(s, n))

t=int (input())



for tt in range(t):
    
    n,k=map(int, (input().split()))
    n=set(range(n+1))
    n.remove(0)
    sub_n=subsets(n, k)
    r=[]
    for j in range(len(sub_n)):
        
        sub_n_=subsets(sub_n[j], 1)
        sub_n_=np.array(sub_n_)
    
        r.append(reduce(ix, sub_n_)) # res = reduce(lambda x, y: x ^ y, sub_n_)
    r_max=max(r)
    j=0
    r_max_index=[]
    for i in r:
        if i==r_max:
            r_max_index.append(j)
        j=j+1

    res=[]
    for i in r_max_index:
        res.append(sub_n[i])
    
    
    for i in range(len(res)):
        print(*res[i],sep=' ')
2

On my machine, it gives the wrong output for the Sample Input:

[simon@simon-laptop][20:05:38]
[~/devel/hackerrank/otherpeoples]>echo "3
10 1
9 2
8 7" | ./shahriar_eee-OPTSET.py
10
6 9
7 8
1 2 3 4 5 6 8
3

6 xor 9= 7 xor 8 = 15, so for input 9 2 we have two results. In the question it was mentioned that:
Find K distinct numbers in the range [1,N] such that the bitwise XOR of all the numbers is maximized. Print any set of these numbers that maximize the XOR.
In the input output explanation it said that:
Test Case 2: The other possible set is {9,6} which gives the value 9⊕6=15=7⊕8. My program showed all the possible values.

4

“any” != “all” :slight_smile:

It’s very explicit about what output it will accept:

The Sample Input has 3 testcases, but you are outputting 4 sets of numbers.

5

Thanks for your feedback.

1 Like