You are not logged in. Please login at www.codechef.com to post your questions!

×

XORSUB - Editorial

9
1

PROBLEM LINK:

Practice
Contest

Author: Lalit Kundu
Tester 1: Minako Kojima
Tester 2: Shiplu Hawlader
Editorialist: Pawel Kacprzak

DIFFICULTY:

SIMPLE

PREREQUISITES:

DP, bits

PROBLEM:

You are given an array A of N integers and an integer K. Your task is to return the maximum possible value of F(P) xor K, where P is a subset of A and F(P) is defined as a xor of all values in P. If P is empty, then F(P) = 0.

QUICK EXPLANATION:

Since each element of A has a value of at most 1000, we can use dynamic programming dp[i][j] := 1 if and only if there exists a subset P of A[1..i] such that F(P) = j. In order to get the result, we return max 1 <= j <= 1023 { dp[n][j] * (j ^ k) }

EXPLANATION:

Let dp[i][j] := 1 if and only if there exists a subset P of A[1..i] such that F(P) = j, otherwise 0

The first observation is that F(P) can be at most 1023 since any input number is at most 1000.

Initially we set all dp[i][j] := 0.

Next, we set dp[0][0] := 1, since a xor of the empty set is 0.

We iterate over all elements of A from left to right. For each A[i], we iterate over all possible values of the xor function i.e. a range from 0 to 1023 inclusive and update these values as follows:

for i = 1 to N:
    for j = 0 to 1023:
        dp[i][j] = dp[i - 1][j] | dp[i - 1][j ^ a[i]]

The reason for this is that if there exists a subset P of A[1..i - 1] such that F(P) = j then there exists also a subset of A[1..i] such that F(P) = j or if there exists a subset P of A[1..i - 1] such that F(P) = j ^ a[i], then F(P) ^ a[i] = j, so there exists a subset P' of A[1..i] such that F(P') = j

At the end we have dp[n][j] for all 0 <= j <= 1023, and we can return a maximum value of dp[n][j] * (j ^ k) for all j.

Time Complexity:

The time complexity per one testcase is O(N * 1023);

AUTHOR'S AND TESTER'S SOLUTIONS:

To be uploaded soon.

RELATED PROBLEMS:

To be uploaded soon.

This question is marked "community wiki".

asked 15 Dec '14, 19:41

pkacprzak's gravatar image

5★pkacprzak ♦♦
72483888
accept rate: 12%

edited 15 Dec '14, 19:55

betlista's gravatar image

3★betlista ♦♦
16.8k49115225


18

I've managed to solve the problem without DP. I've used C++ STL's set and maintained all possible xors in it. Since all numbers are in [0, 1000], any xor of them will lie in [0, 1023]. So, set can have at max of 1024 elements at any point of time. So the complexity should be little less than O(n * 1024 + 1024 * log(1024)) where second term is for the inserts in the worst case.

Here's my solution: http://www.codechef.com/viewsolution/5592821

I've also solved this using Guassian Elimination, you can view my code here: http://www.codechef.com/viewsolution/5616381

Also, the problem does not even need a 2 Dimensional DP, it can be made simpler. Here's my DP solution: http://www.codechef.com/viewsolution/5616433

link

answered 15 Dec '14, 19:58

chaitan94's gravatar image

4★chaitan94
2326
accept rate: 0%

edited 19 Dec '14, 11:17

3

This man is a genius.

(20 Dec '14, 18:04) eisenhover3★

@chaitan94 About your Gaussian Elimination soulution: http://www.codechef.com/viewsolution/5616381

The logic is correct. But there is small flaw in implementation. The above code will give wrong output for following test case


1 
3 1 
12 10 8

This is because of how STL set works. For correct result, just swap these two statements


s.erase(t);
s.insert(t^m);

(22 Dec '14, 22:07) imswapy3★

Where else can we use gaussian elimination technique other than this example and the traditional example of solving linear equation?

(24 Dec '14, 08:05) bhavesh_munot3★

@bhavesh_munot Gaussian elimination technique can also be used to solve a system of congruences.

(29 Dec '14, 23:24) rushilpaul5★

Oh! So the xor basis reduction trick is actually called gaussian elimination , I never knew that. I did the same for my solution, but it's not too popular huh. I haven't seen tutorials on XOR G.E., so it might be good to cook up a good tutorial on it in the future.

(19 Jun, 06:22) hikarico6★

I have a quick question. Information that A is at most 1000 was written in problem statement from the beginning? I wrote a comment about this during the contest but it was not approved. I assumed, that A is up to 2^30, so I solved this problem almost as the last one (when I finally checked the problem statement again)...

link

answered 15 Dec '14, 19:54

betlista's gravatar image

3★betlista ♦♦
16.8k49115225
accept rate: 11%

3

No, it wasn't there in the beginning.. :(

(15 Dec '14, 20:00) ajinkya1p35★

Ai <= 1000 was there at least from 9pm GMT of December 5th, when I read the problem.

(16 Dec '14, 08:41) mogers5★

I used Gaussian elimination to transform the input array A into the lower echelon form which is an equivalent representation of the above array (in which the array of bits [1101, 1001, 1010, 111, 11, 1] for example gets transformed to something like [1111,101, 1] -- decreasing order of bits) Now it is easy to maximize the XOR value greedily. Start iterating with max = k from the left, and include the element only if the XOR value increases, else move on. Output max at the end of the iteration.

link

answered 16 Dec '14, 10:44

adijo's gravatar image

4★adijo
312
accept rate: 0%

edited 16 Dec '14, 10:44

@adijo i tried with the same Gaussian Elimination technique but my code failed for subtask 2....any suggestions on where i went wrong...http://www.codechef.com/viewsolution/5549953

(16 Dec '14, 15:59) skysarthak3★

So your code can solve it for A < 2^30 for example? I have to check that ;-) I was not able to find the solution for that...

(16 Dec '14, 16:46) betlista ♦♦3★
1

@betlista I think it should work!

@skysarthak Can you explain your algorithm? I might be able to point out flaws there if any. If not just reimplement the algorithm more carefully

(16 Dec '14, 23:02) adijo4★

Thanx @betlista & @adijo for help......I followed the first answer given here with slight modification that instead of starting with result = 0 i started with result = k where k is from F(p) xor k...and while traversing the echelon form i xor the row with result if and only if the corresponding bit in result is not set while the one in the array is. After each comparison i jump to the next row and next column. If the no. of columns > no. of rows(bit representation of number is long) then the last row is xor'ed with the result if need be.

(17 Dec '14, 01:10) skysarthak3★
1

gaussian elimination for me too ! :) got AC http://www.codechef.com/viewsolution/5505732

(17 Dec '14, 01:12) cyberax ♦2★

@skysarthak Follow the algorithm in the second answer (with 4 upvotes) After you transform the array to the echelon form don't worry about which bit is set etc, just select the value if the XOR increases, like so:

max = k

for value in array: if max ^ value > max: max = max ^ value

print max

(17 Dec '14, 10:50) adijo4★

I am doing the same thing here: http://www.codechef.com/viewsolution/5608801 I just changed the last for loop of my XMAX solution but it gives WA

(17 Dec '14, 11:47) damn_me3★

Also, what is then wrong with the following approach http://www.codechef.com/viewsolution/5527772 , it's doing the same thing by just dividing the input set in two different sets as explained in my answer below.

(17 Dec '14, 12:00) damn_me3★
1

@damn_me,upvote my comment!!!

U are correct,Your logics are absolutly correct. Just scratch your mind on your codes once again :( :(

You are pushing everything into vector.How can it be possible??!!!

vec.clear()!!!!

(17 Dec '14, 13:05) rudra_sarraf3★

@rudra_sarraf Thanks a lot, seems u needed an upvote :D But what is then wrong with this: http://www.codechef.com/viewsolution/5609487

(17 Dec '14, 14:58) damn_me3★

@damn_me,What I said was Just scratch your mind on your codes once again :( :(

But u didn't!!!

Declaring a variable twice gives error.(ll row=0)(Always try to write clean codes.)

This time no more bullshit neither I need more upvotes than I deserve!!so,

http://www.codechef.com/viewsolution/5609023

If you find clear proof of analogy of gauss elimination method=>Then kindly comment the link (other than mathematics stack exchange=>maximization of xor operator!!).

At last but not the least=>actually (2 upvotes>1upvote)!!!

(17 Dec '14, 16:32) rudra_sarraf3★
1

@rudra_sarraf I have already got AC on this logic. First open the code or link I have mentioned in my comment carefully and then say!! I think discussion forums are for help people want to do themselves and no one is forcing you to see someone's problems or errors. So better not use any more harsh words here!!!! And also, I was just joking for that upvote thing.

(17 Dec '14, 16:43) damn_me3★
2

Once again=>Declaring a variable twice gives error.( you have declared ll row=0 twice!!)

Is that harsh??? OOPS!!

And do you really think that I was taking your joke seriously??!!(just go on thinking blah blah...)

Just skip it...(Otherwise you may complain to admin!!!)

(18 Dec '14, 01:41) rudra_sarraf3★

Where else can we use gaussian elimination technique other than this example and the traditional example of solving linear equation?

(24 Dec '14, 08:06) bhavesh_munot3★
showing 5 of 14 show all

I made a recursive function for solving this. Considering that the biggest number we can make is 1023 and in any case, we can always use an empty set to get the answer as K^0 = K, the biggest number that can be attained is 1023, and the smallest (to be checked) is K. So the answer lies in the range from K to 1023.

To take the initial input, I made an array with size 1001, using which I could directly set array[i]=1 if i was present in the input, else the value of array[i] would be 0. One more thing I did was to go through this array and make a new array which only holds all the elements in descending order.

Now we basically need to check for each number from 1023 to K+1, whether that number can somehow be made with the other numbers present in the set. The most obvious(and ultimately required) case would be if the number is directly present in the set.

The basic idea is that if some number r is required, and isn't directly present in the set, take a number say p from the set, and again call the function for finding r^p in the remaining set. This forms the basic recursion.

But that would give a TLE, so I needed some constraints. I was using the array in decreasing order, so the first number would be the greatest, from this, one simple constraint I was able to make was that if the required number's Most significant bit(MSB) is greater than the currently largest number's MSB, then there is no way to make the required number.

Using all this I was able to get AC with time 0.00 in all but 1 case, which was giving TLE. For further refinement I used the concept that, considering a certain subset of a larger set, if a certain required number could not be made using the larger set, then it can definitely not be made using this smaller subset.

With this I was finally able to get AC that one case too, with a time 0.02

Here is my solution: http://www.codechef.com/viewsolution/5597629

link

answered 16 Dec '14, 21:05

thunderclash's gravatar image

5★thunderclash
183
accept rate: 0%

edited 16 Dec '14, 21:06

nice effort, nice logic :)

(16 Dec '14, 21:13) achaitanyasai5★

I would like to explain the Gaussian Elimination method which I have used and got AC in 0.00 :) The link to my solution. (sorry for some dubugging statements in it).

  1. The idea here is to choose a no. which has MSB with maximum value. With a little thinking, we will get the max(array) will have this feature. Say, maximum of array is a k-bit no. and that no. is M. Now, there can be multiple no.s which are k-bit no.s and have the same highest-value bit as '1'. So in that case we will EX-OR each of them with the M and put them again input array (ideally, we can choose any one of those k-bit no.s as M and put others in array after ex-oring with it). At the same time we will keep the no. M in some other array say x[].

  2. We will keep doing step 1 until we get 0 as maximum in the array i.e. this loop will run for iterations = no. of bit the maximum of array is.

  3. Now will have a x[] array which will be of size = no. of bit the maximum of array is

  4. Now we will initialize the answer variable to given K and loop for each value in array x[], if value of answer variable is going to increase with the inclusion of ith element, we will update the answer variable with the new value as answer^x[i], else we will keep it as is.

  5. Finally returning the value of answer solves our problem.

About my solution:

Bucket[i] contains all i-bit no.s

the M chosen is first element of bucket i.e. Bucket[i][0]

x[] is modified_array[]

link
This answer is marked "community wiki".

answered 19 Dec '14, 00:28

bhavesh_munot's gravatar image

3★bhavesh_munot
1981413
accept rate: 0%

edited 19 Dec '14, 02:39

I just inserted k in the array and used the solution of the problem XMAX on SPOJ which is quite similar. Obviously that's the wrong logic I assumed in the beginning but I got AC in all the subtasks except 4 in subtask 2.

link

answered 15 Dec '14, 20:05

h1ashdr%40gon's gravatar image

3★h1ashdr@gon
2782317
accept rate: 10%

I think that not only you used this approach. It is incorrect, because you have to take k in the resulting subset and not might to take it.

(15 Dec '14, 20:16) pkacprzak ♦♦5★

Yes.I realised it later that k may or may not be taken into consideration in some cases but the co-incidence is great or maybe the test cases fake! :D

(15 Dec '14, 20:21) h1ashdr@gon3★

I tried doing this in the problem. This is the link:: http://math.stackexchange.com/questions/48682/maximization-with-xor-operator

This is same as what @adijo said, I believe. But, the main idea behind this approach is setting one bit of each number one and then xoring with the numbers below in the series if they have that specific bit set, just to ensure no 2 numbers have the same MSB (most significant bit) as 1.

If this is to follow, then since we were given a k, and it also had an MSB, so shouldn't we have xored k with every element in the series which had its bit corresponding to the MSB as 1.

But, it gave me a wrong answer. :/

link

answered 16 Dec '14, 13:18

coderzz027's gravatar image

2★coderzz027
311210
accept rate: 0%

Don't take anything about k into consideration and apply the algorithm as stated by llmari Karonen on stackexchange.

The only difference to be made is in maximum finding algorithm is to initialize max to k instead of 0.

(18 Dec '14, 21:52) bhavesh_munot3★

I thought something similar to the XMAX solution as mentioned above by @h1ashdr@gon . What i did was: divided the whole array in two subarrays, the first that doesn't have any of the bits set as of k and the other that have atleast one bit set. In my maximum, xor of all elements in the first set has a fair chance of giving me the maximum. My task was reduced to finding the maximum of ((xor of set1^k), (xor of set2^k), (set1^set2^k). But then I got stuck in finding the maximum for set2 which is nothing but one of the subproblem of the original question(I tired many approaches though). So, it was just DP i should have thought about or any other way out in this approach??

link

answered 16 Dec '14, 01:15

damn_me's gravatar image

3★damn_me
2.6k21336
accept rate: 24%

"The first observation is that F(P) can be at most 1023 since any input number is at most 1000". How can we conclude that ?

link

answered 16 Dec '14, 06:55

bovas's gravatar image

1★bovas
1
accept rate: 0%

2

Because all numbers less or equal 1000 are written on 9 bits and any bit operation on two numbers which are written on 9 bits results also in a number written o 9 bits. The maximal number which may be written using 9 bits is 1023.

(16 Dec '14, 06:58) pkacprzak ♦♦5★

I have tried this problem and 9 testcases are not passed . This is my solution link : http://www.codechef.com/viewsolution/5518114

Could anyone help me out .

link

answered 17 Dec '14, 09:04

ritwikenator's gravatar image

2★ritwikenator
4614
accept rate: 16%

Explain your logic step by step or write well commented solution at least.

(18 Dec '14, 21:59) bhavesh_munot3★

Which is better for large inputs - Gaussian elimination or dp?

link

answered 17 Dec '14, 11:09

piyush%20asutkar's gravatar image

3★piyush asutkar
14
accept rate: 0%

Can anyone tell me how this solution works? I think it doesn't cover all possibilities?

link

answered 17 Dec '14, 14:45

mtbar131's gravatar image

2★mtbar131
163
accept rate: 0%

Can anyone explain me this plz

dp[i][j] = dp[i - 1][j] | dp[i - 1][j ^ a[i]]
link

answered 17 Dec '14, 15:28

ravidelcj's gravatar image

4★ravidelcj
10139
accept rate: 16%

can any one explain why gaussian method work.?? i mean after take echleon form of the matrix what happend that it is giving me sum of each subset from the given set....

link

answered 17 Dec '14, 16:45

coredumped's gravatar image

0★coredumped
1
accept rate: 0%

I got AC by using gaussian elimination.

A simple explanation :

First do the gaussian elimination, now traverse through each row. having the value of k, do k xor the first row and if the result is bigger than k, assign the value of the result to k, otherwise donot change k.

Similarly iterate over all the rows

and the final k is the answer

my link to answer : code

link

answered 17 Dec '14, 16:52

king_of_hacker's gravatar image

3★king_of_hacker
204311
accept rate: 7%

@king of hacker.....

i know .. i am asking as to why this method worked?

link

answered 17 Dec '14, 18:25

coredumped's gravatar image

0★coredumped
1
accept rate: 0%

Instead of using 2-d array solution can be easily solved using 1-D array. I found that solution from submission list. Really nice logic.

http://www.codechef.com/viewplaintext/5531874

Can anyone please explain how Gaussian Elimination is applied on this problem. I saw the stack exchange link but couldn't make out anything from that.

link

answered 17 Dec '14, 19:22

vidhyabhushan's gravatar image

2★vidhyabhushan
111
accept rate: 0%

did it using gaussian elimination but dp also seems really cool trick here.......

loved the editorial (thnx codechef)

link

answered 18 Dec '14, 08:22

ritesh_malav's gravatar image

4★ritesh_malav
743
accept rate: 8%

for i = 1 to N: for j = 0 to 1023: dp[i][j] = dp[i - 1][j] | dp[i - 1][j ^ a[i]] how is this working ?? getting difficulty in understanding this part , can someone explain it to me. plzzz

link

answered 19 Dec '14, 13:58

tirthtp's gravatar image

2★tirthtp
2814
accept rate: 0%

Why my solution is not working ? I have commented my algorithm in the code. My solution

link

answered 20 Dec '14, 19:55

sdream's gravatar image

2★sdream
-124
accept rate: 0%

I tried greedy approach for this problem and it did not work. Can some one please point out the mistake in my logic/approach. Here is what I did

  1. XOR K with each of the elements in the array. Say the result is a.

  2. I pick the max a and then try to XOR it with the remaining elements(one element at a time) and see if the value of a is increased or not. Let us say the value is b.

  3. If b is greater than a, then i will override a with the value of b. Repeat this process until b > a. Otherwise i will terminate the logic

  4. Return the last value of a if a is greater than K. or else return K

Below is my solution in Java

http://www.codechef.com/viewsolution/5534659

link

answered 21 Dec '14, 10:29

biluriuday's gravatar image

3★biluriuday
1
accept rate: 0%

edited 21 Dec '14, 18:29

@chaitan94 why the C++ STL's unordered_set is not working in place of set ??

link

answered 18 Mar '15, 23:13

bajaj6's gravatar image

2★bajaj6
39135
accept rate: 0%

"if there exists a subset P of A[1..i - 1] such that F(P) = j ^ a[i], then F(P) ^ a[i] = j, so there exists a subset P' of A[1..i] such that F(P') = j" Can anyone explain the above statement?

link

answered 04 May '15, 07:57

siddhant_08's gravatar image

4★siddhant_08
1
accept rate: 0%

Can anyone explain why A[0..i-1] having the value j makes it necessary for A[0...i] to have value j and also the next condition?I'm not understanding this dp.

link

answered 11 Nov '15, 13:39

getsuga's gravatar image

3★getsuga
613
accept rate: 0%

how did we reach the conclusion that xor of any subset of the numbers less than 1000 will be less than 1023?

link

answered 04 Dec '15, 16:55

stellar97's gravatar image

3★stellar97
1
accept rate: 0%

Numbers up to 1000 have powers of 2 up to 9 in their binary representation (2^9 = 512). Hence, the xor of these numbers is at most "1111111111", i.e. 2^0 + 2^1 + ... + 2^9 = 1023.

(04 Dec '15, 17:05) mogers5★

How do we find out a sub-array having maximum xor value?

link

answered 23 Mar '16, 19:14

samgrv's gravatar image

3★samgrv
261
accept rate: 20%

sorry, I'm forget to add the word efficiently.

(23 Mar '16, 19:16) samgrv3★

This informative article was very inspiring visitors I hope there will certainly be content to teach the next content Please also visit my web site at Garden Statue

link

answered 23 Mar '16, 21:01

punkbrebes13's gravatar image

0★punkbrebes13
1
accept rate: 0%

This article was very inspiring visitors I hope there will be content to instruct the next content You should also visit my web site at Bali Buddha Statue

link

answered 23 Mar '16, 21:02

punkbrebes13's gravatar image

0★punkbrebes13
1
accept rate: 0%

the pc is usually a software that we are able to use to lift websites cooperating with search engine optimization techniques. for those of you who would like to learn web optimization please visit our website Jasa SEO the pc is a instrument that we uses to improve websites working with search engine optimization methods. for those of you who wish to learn assist in please visit internet site

link

answered 23 Mar '16, 21:03

punkbrebes13's gravatar image

0★punkbrebes13
1
accept rate: 0%

This article was very inspiring visitors I hope there will certainly be content to instruct the next content Please also visit my website at Cargo Bali

link

answered 23 Mar '16, 21:04

punkbrebes13's gravatar image

0★punkbrebes13
1
accept rate: 0%

the pc is a device that we could make use of to optimize websites cooperating with search engine optimization strategies. for those of you who would like to learn search engine ranking please visit internet site Jasa SEO typically the pc is a program that we uses to maximize websites working with search engine optimization techniques. for those of you who would like to learn search engine ranking please visit our website

link

answered 23 Mar '16, 21:04

punkbrebes13's gravatar image

0★punkbrebes13
1
accept rate: 0%

-1

I tried couple of times.Task# 8-15 passed for Subtask 2. Subtask 1 completely failed. I am still wondering what did i miss in my solution. Here is my solution http://www.codechef.com/viewsolution/5532642

any insight will be a great help.

Thank you.

link

answered 17 Dec '14, 01:21

mirza_gaush's gravatar image

2★mirza_gaush
-1
accept rate: 0%

Check your solution link! Its bytelandian gold coin problem.

(18 Dec '14, 21:54) bhavesh_munot3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×12,235
×1,320
×801
×303
×227

question asked: 15 Dec '14, 19:41

question was seen: 16,179 times

last updated: 19 Jun, 06:22