| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | Dominater069 | 154 |
| 8 | nor | 154 |
What's the best algorithms for these below problems?
Subarray with Max Xor ?
Subsequence with Max Xor ?
Longest Subarray among those have Max Xor ?
Longest Subsequence among those have Max Xor ?
Can we use each algorithm for Min Xor , too ?
Longest Common Substring between two strings ?
Bit trie. If you will use array of partial xors
This is linear algebra problem which can be done with some Gauss elimination if you will maintain basis in correct form.
Use the algorithm from the first point and for each R you should find the minimum L.
I dunno. Is it solvable at all, guys?
Yes.
Any suffix structure is sufficient. You may take a look at my artice about suffix tree or suffix automaton for example :)
Thanks ;D
These are the best I know:
So the first problem is just simply a trie of the prefix xors.
Actually I learned the second one just yesterday. Its similar to Gauss Elimination but not the same. I can explain the idea below. It works in O(Nlog(MAX)). Another way to do this is with FFT in O(MAXlog(MAX)log(N)). Note that the second way (with FFT) can be applied if we have a bound for the subset size.
3rd. can be done again with a trie. We just need to find the first occurance of each possible xor.
4th. If you google the first approach for the second problem (max xor subset) and understand it. You should be able to solve this problem. Time complexity again will be O(Nlog(MAX)).
5th. Its the same as for the max.
6th. Again there are a lot of solutions for this problem. The best I know and the easiest to write in my oppinion is using suffix automaton in O(N+M) time.
You misread the 4th one.
Ops, you are right.
Then you should be able to apply the second method (with FFT). First we find the Maximum xor of a subsequence. Then we will apply a binary search on the maximum length. Then the complexity will be O(MAX * log(MAX) * log^2(N)).
Edit: Never mind. That was a silly question. I understood now. Nice comment. :)
Then we will apply a binary search on the maximum length.
How did you prove that the length of the max XOR is a linear increasing function?
How to do this with FFT?
So it isn't the straight forward FFT. It is a slight modification of it.
In the default FFT multiplication if we have polynomials A and B (lets represent the ith coefficient of a polynomial with A[i] or B[i]) we will have RESULT[i+j] = SUM(A[i]*B[j]). In this modification we will have RESULT[i XOR j] = SUM(A[i]*B[j]) — we won't sum the powers but we will xor them.
Now lets represent our input array as an polynomial. We should count the number of occurrences of every element of the input. Then our polynomial should look something like that:
A(x) = CNT[0] * x^0 + CNT[1] * x^1 + ... + CNT[MAX] * x ^ MAX
Lets find Kth power of A(x). In this new polynomial the coefficient before x will be the number of subsets with xor equal to x and with size equal to K.
You can see problem 663E - Двоичная табличка and my 17700160 with FFT.
Also you can look at this HackerRank problem.
Omg, you don't use any single xor operation in your code... I need further elaboration :(
In FFT after transform you have values in roots of unity. And here?..