XORED - Editorial

[ssjgz]

Invalid set iterator erasure with sample input:

[simon@simon-laptop][18:04:48]
[~/devel/hackerrank/otherpeoples]>./compile-latest-cpp.sh 
Compiling hacker325-XORED.cpp
Executing command:
  g++ -std=c++17 hacker325-XORED.cpp -O3 -g3 -Wall -Wextra -Wconversion -DONLINE_JUDGE -D_GLIBCXX_DEBUG    -fsanitize=undefined -ftrapv
hacker325-XORED.cpp: In function ‘int main()’:
hacker325-XORED.cpp:10:15: warning: unused variable ‘M’ [-Wunused-variable]
   10 |     const int M = 32;
      |               ^
Successful
[simon@simon-laptop][18:05:24]
[~/devel/hackerrank/otherpeoples]>echo "3
1 10
2 4
3 1
" | ./a.out
/usr/include/c++/9/debug/set.h:345:
In function:
    std::__debug::set<_Key, _Cmp, _Allocator>::iterator 
    std::__debug::set<_Key, _Cmp, _Allocator>::erase(std::__debug::set<_Key, 
    _Cmp, _Allocator>::const_iterator) [with _Key = long int; _Compare = 
    std::less<long int>; _Allocator = std::allocator<long int>; 
    std::__debug::set<_Key, _Cmp, _Allocator>::iterator = 
    __gnu_debug::_Safe_iterator<std::_Rb_tree_const_iterator<long int>, 
    std::__debug::set<long int>, std::bidirectional_iterator_tag>; typename 
    std::iterator_traits<typename std::__cxx1998::set<_Key, _Compare, 
    _Allocator>::iterator>::iterator_category = 
    std::bidirectional_iterator_tag; typename std::__cxx1998::set<_Key, 
    _Compare, _Allocator>::iterator = std::_Rb_tree_const_iterator<long 
    int>; std::__debug::set<_Key, _Cmp, _Allocator>::const_iterator = 
    __gnu_debug::_Safe_iterator<std::_Rb_tree_const_iterator<long int>, 
    std::__debug::set<long int>, std::bidirectional_iterator_tag>; typename 
    std::iterator_traits<typename std::__cxx1998::set<_Key, _Compare, 
    _Allocator>::const_iterator>::iterator_category = 
    std::bidirectional_iterator_tag; typename std::__cxx1998::set<_Key, 
    _Compare, _Allocator>::const_iterator = 
    std::_Rb_tree_const_iterator<long int>]

Error: attempt to erase from container with a past-the-end iterator.

Objects involved in the operation:
    sequence "this" @ 0x0x7ffdbe70c3b0 {
      type = std::__debug::set<long, std::less<long>, std::allocator<long> >;
    }
    iterator "__position" @ 0x0x7ffdbe70c380 {
      type = std::_Rb_tree_const_iterator<long> (constant iterator);
      state = past-the-end;
      references sequence with type 'std::__debug::set<long, std::less<long>, std::allocator<long> >' @ 0x0x7ffdbe70c3b0
    }
Aborted (core dumped)

From here, apparently:

                    // don't want some number which is greater than one
                    ans.erase(it); <--

[hacker325]

Thanks for your reply.

#include <bits/stdc++.h>
using namespace std;
#define int     int64_t
#define IOS     ios::sync_with_stdio(0); cin.tie(0); 


signed main() {
    IOS;
    int t; cin >> t;
    const int M = 32;
    int even = 4e5, odd = 4e5+1, zero = 0;
    int even_two = 400000, odd_two = 400002;
    while(t--) {
        int n, x; cin >> n >> x;
        
        if(n == 1) {
            cout << x << "\n";
        } else if(n == 2) {
            cout << 0 << " " << x << "\n";
        } else {
            set<int> ans;
            // ans[0] = even, ans[1] = odd;
            int till = 0;
            for(int i=1;i<=n-1;i++) {
                ans.insert(i);
                till = till ^ i;
            } 
            // n - 1 elements filled till here [1, 2, 3, ... n - 1]
            int last = x ^ till;
            // last ^ till = x; last = x ^ till;
            // if last belongs to [1, 2, 3, ... n - 1] 
            if((last > 0) && (last < n)) {
                auto it = ans.find(last);
                if(it == ans.begin()) {
                    // don't want 1 in the array as [2 ^ 3 ^ ... ^ n - 1] = X
                    // erase 1 and 2
                    ans.erase(it);
                    ans.erase(2);
                    // add three unique elements such that 
                    ans.insert(even_two);
                    ans.insert(odd_two);
                    ans.insert(zero);
                } else {
                    // don't want some number except one
                    ans.erase(it);
                    ans.erase(ans.begin());
                    ans.insert(even);
                    ans.insert(odd);
                    ans.insert(zero);
                }
            } else {
                ans.insert(last);
            }

            int i = 0;
            // cout << "SIZE: " << ans.size() << "\n";
            // for(auto num : ans) {
            //     cout << i + 1 << " " << num << "\n";
            //     i += 1;
            // }
            till = 0;
            for(auto num : ans) {
                till = till ^ num;
            }
            // cout << "XOR: " << till << "\n";
            // assert(ans.size() == n);
            // assert(till == x);
            
            
            for(auto num : ans) {
                cout << num << " ";
            }
            cout << "\n";
        }
    }
}

This is the code that passes the first subtask. What’s going wrong here?

[ssjgz]

Consider the test input:

1
471 499739

[hacker325]

@ssjgz

1
471 499739

Thanks @ssjgz. When i ran this test case, one number in my answer was overflowing the given bounds. I fixed it by xoring 1 by 2^18 and setting off the MSB of the highest number. It got accepted.

[sahil_mahajan7]

import java.io.*;
import java.util.*;

public class Main {
    //--------------------------INPUT READER---------------------------------//
    static class fs {
        public BufferedReader br;
        StringTokenizer st = new StringTokenizer("");

        public fs() { this(System.in); }
        public fs(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }
        String next() {
            while (!st.hasMoreTokens()) {
                try { st = new StringTokenizer(br.readLine()); }
                catch (IOException e) { e.printStackTrace(); }
            }
            return st.nextToken();
        }

        int ni() { return Integer.parseInt(next()); }
        long nl() { return Long.parseLong(next()); }
        double nd() { return Double.parseDouble(next()); }
        String ns() { return next(); }

        int[] na(long nn) {
            int n = (int) nn;
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = ni();
            return a;
        }

        long[] nal(long nn) {
            int n = (int) nn;
            long[] l = new long[n];
            for(int i = 0; i < n; i++) l[i] = nl();
            return l;
        }
    }
    //-----------------------------------------------------------------------//

    //---------------------------PRINTER-------------------------------------//
    static class Printer {
        static PrintWriter w;
        public Printer() {this(System.out);}
        public Printer(OutputStream os) {
            w = new PrintWriter(os, true);
        }
        public void p(int i) {w.println(i);}
        public void p(long l) {w.println(l);}
        public void p(double d) {w.println(d);}
        public void p(String s) { w.println(s);}
        public void pr(int i) {w.print(i);}
        public void pr(long l) {w.print(l);}
        public void pr(double d) {w.print(d);}
        public void pr(String s) { w.print(s);}
        public void pl() {w.println();}
        public void close() {w.close();}
    }
    //-----------------------------------------------------------------------//

    //--------------------------VARIABLES------------------------------------//
    static fs sc = new fs();
    static OutputStream outputStream = System.out;
    static Printer w = new Printer(outputStream);
    static long lma = Long.MAX_VALUE, lmi = Long.MIN_VALUE;
    static int ima = Integer.MAX_VALUE, imi = Integer.MIN_VALUE;
    static long mod = 1000000007;
    //-----------------------------------------------------------------------//

    //--------------------------ADMIN_MODE-----------------------------------//
    private static void ADMIN_MODE() throws IOException {
        if (System.getProperty("ONLINE_JUDGE") == null) {
            w = new Printer(new FileOutputStream("output.txt"));
            sc = new fs(new FileInputStream("input.txt"));
        }
    }
    //-----------------------------------------------------------------------//

    //----------------------------START--------------------------------------//
    public static void main(String[] args)
            throws IOException {

         ADMIN_MODE();

        int t = sc.ni();while(t-->0)
            solve();


        w.close();
    }

    static Random rnd = new Random();

    static int btw(int l, int r) {
        return Math.abs(rnd.nextInt())%(r-l+1)+l;
    }

    static void solve() throws IOException {
        int n = sc.ni();
        int xor = sc.ni();
        char[] strr = Integer.toString(xor, 2).toCharArray();
        int[] xrr = new int[32];
        int id = strr.length-1;
        for(int i = 0; i < strr.length; i++) {
            xrr[i] = (strr[id--]=='1'?1:0);
        }

        List<Integer> li = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            li.add(0);
        }

        for(int i = 0; (i < strr.length) || !diff(li); i++) {
            int curr = xrr[i];

            int one = 0, zer = 0;
            int add = (int)Math.pow(2, i);
            List<Integer> nn = new ArrayList<>();

            nn.add(li.get(0));
            zer++;
            int last = -1;
            int diff = -1;
            boolean on = true;
            for(int j = 1; j < n; j++) {
                if(li.get(j-1).equals(li.get(j))) {
                    if(on) {
                        nn.add(li.get(j) + add);
                        last = j;
                        one++;
                        on = false;
                    } else {
                        nn.add(li.get(j));
                        zer++;
                        on = true;
                    }
                } else {
                    if(diff == -1 && (j == n-1 || !li.get(j+1).equals(j))) {
                        diff = j;
                    }

                    on = true;
                    nn.add(li.get(j));
                    last = j;
                    zer++;
                }
            }

            if((curr == 1 && one%2==0) || (curr == 0 && one%2==1)) {
                if(diff != -1) {
                    nn.set(diff, nn.get(diff)+add);
                } else {
                    if (last != -1 && one >= zer) {
                        nn.set(last, nn.get(last) - add);
                    } else {
                        nn.set(0, nn.get(0) + add);
                    }
                }
            }

            li = nn;
            li.sort(Integer::compare);
        }

        for(int i = 0; i < n; i++) {
            w.pr(li.get(i)+" ");
        }
        w.pl();
    }

    static boolean diff(List<Integer> li) {
        for(int i = 1; i < li.size(); i++) {
            if(li.get(i).equals(li.get(i-1))) return false;
        }
        return true;
    }
}

totally different approach

[lakshayn]

How did you get the idea of 19th bit ? How do you know that a number >= 5x10^5 will have 19 bits ? How did you calculate the bits, can anyone explain please

[ps47]

I used a similar approach but for cases with N%4 = 3 and N%4 = 0, I took the numbers of the form 0(this one if N % 4 = 0), x ^ i, x ^ (i + 1), x ^ i ^ (i + 1). Just brute force to find any valid i.

[vishwajeet7381]

We have to flip 19th bit of one more number, so we will flip 19th bit of a[n-2] if after fliping its not equal to a[n-1] else we will another number which in this case is a[0].