Here is the Problem Image : Click here

Sample Input output and constraints : CLICK here

Please specify an approach for this problem

# | User | Rating |
---|---|---|

1 | tourist | 3707 |

2 | Benq | 3672 |

3 | ksun48 | 3575 |

4 | Radewoosh | 3562 |

5 | Miracle03 | 3480 |

6 | maroonrk | 3406 |

7 | ecnerwala | 3400 |

8 | peehs_moorhsum | 3384 |

9 | sunset | 3338 |

10 | Um_nik | 3320 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 208 |

2 | YouKn0wWho | 204 |

3 | Um_nik | 197 |

4 | Errichto | 181 |

4 | sus | 181 |

6 | awoo | 179 |

7 | tourist | 175 |

8 | -is-this-fft- | 171 |

8 | SecondThread | 171 |

10 | Ashishgup | 170 |

Here is the Problem Image : Click here

Sample Input output and constraints : CLICK here

Please specify an approach for this problem

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/28/2021 19:00:13 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Auto comment: topic has been updated by code_tycoon (previous revision, new revision, compare).I guess dp can be applied , the states are $$$i$$$ and $$$j$$$ where $$$i$$$ is the index till where we have considered the input array and j is the number of elements in the current subset. The transitions are $$$ dp[i+1][j]=std::max(dp[i+1][j],dp[i+1][j]) $$$ (You are not adding the i'th element to the xor subset) and $$$ dp[i+1][j]=std::max( dp[i][j] $$$ ^ $$$ ar[i] , dp[i+1][j] ) $$$ (meaning you are considering adding the element to the subset )

The final answer would be the highest value in the last row and in the first $$$n/2$$$ numbers.

Edit: won't work because a^b > c^b even if a<c , so this method is wrong

apply reverse dp, minimum size subset with xor = j considering i elements

transition will be like

$$$dp(i,j) = min(dp(i,j) , dp(i-1,j \oplus a_i) + 1)$$$

total complexity will be $$$N * 2^{20}$$$

I guess this can also be solved using linear basis(gaussian elimination), but i am not sure how, if someone could explain me that would be great.

Don't know about gaussian elimination although there is also another method to solve this problem using vector addition on xor (reference here )

It will allow us to solve in around $$$10^6$$$ iterations.

But how will you calculate maximum xor using the size of the subset which you are storing into the DP array ? the problem is to calculate maximum xor possible using atmost n/2 elements from the array not to find the minimum number of elements to form xor of n/2 ... kindly correct me if I am wrong navneet.h

Ya, i think it is some kind of variation of knapsack dp because we can either choose the element or not choose .

This problem was already asked here today. And a few more times earlier this week.

why isnt this some greedy over the bits?

Yes, definitely it is solvable through dp