Here is the Problem Image : Click here
Sample Input output and constraints : CLICK here
Please specify an approach for this problem
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 166 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 18.11.2024 01:26:47 (j2).
Десктопная версия, переключиться на мобильную.
При поддержке
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?