BITSWAPS - Editorial

editorial
, , ,
21

thank you for explaining hopefully understand

22

This problem kept be busy for 2 days! Only to later find out the first test case fails both cases print “yes” or “no”! is that even possible?

for _ in range(int(input())):
    N = int(input())
    _list = list(map(int, input().split(' ')))
    print("No")

for _ in range(int(input())):
    N = int(input())
    _list = list(map(int, input().split(' ')))
    print("Yes")

I new; is there something Iam missing here?

23

I am sorry, but could you please explain what are you trying to do?

24

answer to test cases is wrong WA or passed AC right? the first test case shows wrong answer for both cases the first code snippet where i print no; and the second test case where i print yes! A6C416A19D70416896F822F4593CCCEF
1BF41B0346AD455B9BB6D6F021A1D00D

25

Yes.

The reason is that, either of your code where you are printing yes or no, does not take care of the input that you are receiving. It just prints either yes or it prints just no.
Think 'test case' as an 'input file'. Think 'the first test case' as 'the first input file'.
Like the first sample input given in the problem page, each input file consists of many inputs, whose outputs may be ‘Yes’ or ‘No’. But your first code snippet will print ‘No’ for every input (where it should have printed Yes for some input; No, for other inputs) and your second code snippet will print ‘Yes’ for every input (where it should have printed Yes for some input; No, for other inputs).

So overall either of your code snippets does not pass the first input file, so you are receiving a WA verdict.

Interestingly, the fifth input file contains input whose output is No for all inputs, so your first code snippet is passing all, hence you got AC only in the fifth input file.
Similarly, the second, third and fourth input files contain inputs whose output is Yes for all inputs, so your second code snippet is passing them all.

PS, I forgot to mention that for each input file, they have an output file and the output of your program will be redirected to another file. The two output files would then be matched. If any difference exists, Codechef will automatically report a WA, else you will get an AC verdict. For more info, refer this :slight_smile:

1 Like
26

Are you sure?
The first line of the input should contain T, the number of test cases.
So, the input must be:

1
8
0 0 9 34 4 24 1 6

For which the Editorialist’s solution gives Yes.

27

Thanks for pointing out! I have made the changes.

28

I tried to find out what indexes can be swapped. Instead of doing it in O(N^2) by checking whether each pair of indices will swap I joined each index to the bits it had set.

For a given element at index i, let [1, 2, 7] be the positions of set bits in arr[i]. Then I do

unionSet(i, 100001);
unionSet(i, 100002);
unionSet(i, 100007);

This will help me check if any 2 indexes be swapped if they belong to the same set.
Then I sort the array and keep a track of what index goes where after sorting.
After that its just a matter of querying whether the index in the sorted array belongs to the same set which occupied the current index before sorting.
Here’s my solution

29

Can any one tell me why I am getting wrong answer?

I have used set to implement it using editorial and youtube video ( TLE is fine).

https://www.codechef.com/viewsolution/58562720

30

TC of function *min_element(arr+i,arr+n) is O(N) so overall complexity of your approach is O(N^2) so TLE.

31

Consider this input:

1
5
2 5 4 2 3

Expected Output

YES
1 Like
32

we have to find a no. that a&c !=0 , c&b !=0

This condition is not necessary, For example for A=[12,3,6,1]
A_1 \& A_2 = 0 and A_4 \& A_2 \neq 0
A_1 \& A_3\neq 0 and A_4 \& A_3 = 0
Yet we can still swap A_1 and A_4 by applying operations : (1,3), (1,2), (1,4),(2,4), (3,4).

1 Like
33

Solved it using a similar approach with few differences.

If a & b > 0 then I am adding them in a set and that set can be represented as a | b .
We can also replace a and b with a|b because a can swap with all the elements that can be swapped with b and vice versa.

I am not sure about the time complexity though.

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

string solve() {
    int n, cur;
    cin >> n;
    vector<int> arr, sets;

    for (int i = 0; i < n; i++) {
        cin >> cur;
        arr.push_back(cur);
        for (int j = 0; j < sets.size(); j++) {
            if (cur & sets[j]) {
                cur = cur | sets[j];
                sets.erase(sets.begin() + j);
                --j;
            }
        }
        sets.push_back(cur);
    }

    vector<int> sorted_arr = arr;
    sort(sorted_arr.begin(), sorted_arr.end());

    for (int i = 0; i < n; i++) {
        bool can_swap = false;
        for (int j = 0; j < sets.size(); j++) {
            if (arr[i] & sets[j] && sorted_arr[i] & sets[j]) {
                can_swap = true;
                break;
            }
        }
        if (can_swap) continue;
        return "No";
    }

    return "Yes";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        cout << solve() << "\n";
    }

    return 0;
}
1 Like
34

Continuing the discussion from BITSWAPS - Editorial:
Nice . Seems like time complexity will be O(NlogN) since size of sets will be at worst logN .

1 Like
35

I think this is what the OP mentions as “Wrong Approach” You check whether a, b can be directly swapped, but they can both be swapped with a third member c like a \leftrightarrow c and c \leftrightarrow b.