Help needed in XORSUB

help
,
1

This might be very naive, but still, can anyone help me by telling why the problem XORSUB can’t be solved with an intuitive subset selection recursive method like:

ll recurse(ll x, ll cur) {
if(x >= n) return cur;
return max(recurse(x+1, cur), recurse(x+1, cur^a[x]));
}

I know this problem will be solved with gaussian elem. but I can’t get it.
Thanks for anyhelp.

2

Are you asking about why will this solution get TLE ?
Then answer is your solution is O(2^n) (as you are checking each and every subset naively and there are total 2^n subsets possible of a set having size n)
and 2^{100} == 10^{30} whereas one can only do about 10^8 to 5*10^8 operations in one second…

2 Likes
3

No i knew recursion is a tle but i was getting a WA on the above code, even on the smaller subtasks of the problem, although I have found the mistake I was doing in the implementation part.
BTW, can u suggest some good resources for gaussian elimin.??

4

@shan01
I don’t think we need anything like that for solving this question… I have a very simple solution…
https://www.codechef.com/viewsolution/24082100
see this solution and try to understand what I did…
It has very very simple solution trust me…
Ping me if you still don’t understand it…
boolean array a stores if it exist a subset having value of xor=index

5 Likes
5

Thanks man, I think that was the easiest to understand among all the solutions I encountered.
cheers!

2 Likes
6

Welcome :slight_smile:
Like my answer then :stuck_out_tongue::joy:

2 Likes
7

i tried to solve this question using normal array - got RE ( as size is getting too large).
then uses index of boolean array max size will be 1024 ( worked fine)
then i tried unordered set getting WA for half of test case - unordered_set solution

1 Like
8

I thought a written acknowledgement would be much more valuable.

2 Likes
9

Yeah it was valuable… Thanks…
I want to increase my trust level :smiley:

1 Like
10

@l_returns has an awesome and easy to understand solution.
But if you are looking for a recursive solution then you can have a look at this solution.

3 Likes
11

@shivamchef
unordered set means it completely unordered… adding one element can change order of all other elements…
So if you insert elements while you are using for each loop then there will be lot of mess…
https://www.codechef.com/viewsolution/24082696
here is your AC solution
check this code and you’ll understand the problem…

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

#define ll long long int
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007

int main() {
   FIO;
   int t,n,k,i,j;
   unordered_set<int> v;

   v.insert(0);
   v.insert(5);
   v.insert(8);

   for(auto it:v)
      cout << it << " ";
   cout << endl;

   v.insert(4);

   for(auto it:v)
      cout << it << " ";
   cout << endl;

   v.insert(10);

   for(auto it:v)
      cout << it << " ";
   cout << endl;

   return 0;
}
1 Like
12

Karma Farming :stuck_out_tongue:

2 Likes
13

yeah inspired by @vijju123 XD…

1 Like
15

I think there are 3 levels and vijju is on 3rd one… I am on 2nd one… XD
Now i think i wont get to 3rd level…

2 Likes
17

exactly… got it XD… never mind…
that’s very bad @taran_1407 … @vijju123 may ban both of them… be careful XD…

1 Like
18

Off-topic level --> infinity :rofl: :joy:

2 Likes
19

You just pitched an idea for @vijju123 .
@taran_1407 beware!

20

thanks for the solution :smiley:

21

:joy::joy::joy:… (Need 20 characters)

1 Like
22

Lol,I never knew that top-contributors get laddus :stuck_out_tongue: :stuck_out_tongue:

1 Like