Given array a of length 1 ≤ n ≤ 44, 0 ≤ ai ≤ 244. Calculate di = number of subsets that their xor has i '1' bits.
I think this is a meet-in-the-middle problem but I couldn't solve it, so I need help.
Given array a of length 1 ≤ n ≤ 44, 0 ≤ ai ≤ 244. Calculate di = number of subsets that their xor has i '1' bits.
I think this is a meet-in-the-middle problem but I couldn't solve it, so I need help.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
The set of ai generates a vector space. Let D be the dimension of this space.
There are 2D elements in this vector space. Brute force works in O(2D * poly(N)).
There is a system of N - D equations that defines this space. Bitmask DP works in O(2N - D * poly(N)).
The same solution/approach from a bit different perspective (I think it's different enough to describe it):
Imagine a grid with 0's and 1's, where the i-th row contains ai. Run Gauss Elimination, to get 1's in say first D cells of the main diagonal, and only 0's above and below those 1's. Also, only first D rows are non-zeros. (We can obtain that, but in Gauss we must swap rows and swap columns).
Then run brute force if D is small, and otherwise run bitmask DP on last M-D columns, where the score of subset of taken rows should be equal to the numbers of 1's in the xor, increased by the number of rows taken, because each taken row has one 1 on the left, in forgotten main diagonal.
btw. I think all blogs like this one should give the source of a problem, so others could implement and submit a solution, and to fight (a bit) with cheating and asking about problems from ongoing contests.
Could you please explain why brute force for the first D rows is sufficient?
Other rows contain 0's only. It means that now we want to know the answer for the initial problem with some new values ai (each corresponding to one row) and only first D of them are non-zero — we can check all subsets of those.
Does that mean for every mask among the 2^D elements we will have 2^(N-D) subsets corresponding to it.Please correct me if it is wrong.
2D elements? Do you mean 2D achievable total xors? Then the answer is yes, but your strange question might mean you don't understand something. We are left e.g. with numbers {3, 8, 50, 100, 0, 0, 0}, so we say D = 4. For each of 2D subsets of first D elements, we get some xor, and there are 2N - D = 23 ways to choose which of 0's we always take in the subset.
Thanks for clarification.But,even if D is large wouldn’t choosing i(query parameter) from D elements and multiplying it by 2^(N-D) give the answer within time limit?
I don't understand what you mean with "choosing i from D elements". Do you want to iterate over all subsets of D elements (subsets with size i)? If not, what complexity do you have in your mind?
No,given that there are D independent non zero row vectors and di(query parameter) NCR(D,di)*pow(2,N-d) would give us number of ways to generate di 1’s.
The number of taken numbers isn't equal to the number of 1's in the xor. For example, xor of 2 numbers 101011 and 110100 is 011111. There are 5 1's in the xor.
But the numbers after gaussian elimination will only have a single 1 and for each vector it should be at different bit position.Maybe I am missing something.
It isn't true. Let's say you start with two rows: 10111 and 01111. What matrix do you want to get?
UPD: I'm so so sorry guys I completely misunderstood the problem please don't take this answer in consideration.
I'm not sure if this is correct but maybe we can do something like this:
DP[pos][bit][ok] which denotes the number of subsets that don't have an element whose index is bigger than
posand that has thebitth bit equal tookand your moves will be eitherDP[pos + 1][bit][ok] or dp[pos + 1][bit][ok ^
bitth bit of a[pos]].Now I know that this probably isn't a right solution I'm just trying to provide a perspective that someone might use to achieve a correct solution.