How to solve the following problem ? Given an array of size N having integer elements A[1], A[2] , …, A[N] find the maximum value of ( (A[1] xor X) + (A[2] xor X) + (A[3] xor X)+ … + (A[N-1] xor X) + (A[N] xor X) ) for some X belonging to [L,R] . constraints- N <= 100000, 1 <= A[i], L, R <= 1000000000 . A good follow up ques to try is https://www.codechef.com/problems/CHANDF
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3947 |
| 2 | jiangly | 3734 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3612 |
| 7 | ecnerwala | 3581 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | ksun48 | 3479 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 162 |
| 2 | maomao90 | 160 |
| 3 | nor | 156 |
| 4 | cry | 155 |
| 4 | adamant | 155 |
| 4 | atcoder_official | 155 |
| 4 | -is-this-fft- | 155 |
| 8 | maroonrk | 153 |
| 9 | Petr | 146 |
| 10 | SecondThread | 144 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 24.08.2024 06:18:10 (g1).
Десктопная версия, переключиться на мобильную.
При поддержке
Auto comment: topic has been updated by deepkamal (previous revision, new revision, compare).
Auto comment: topic has been updated by deepkamal (previous revision, new revision, compare).
Problem source?
https://www.hackerrank.com/contests/cp-recruitment-contest-iiti/challenges/the-greatest
Classic problem: fill X's bits from the most significant to the least significant, then do digit dp with the extra state of "is the current number equal to the prefix of L/R" and answer being the max answer considering the unfilled bits. When you fill a bit with 0/1, add 2^B * frequency of the 1/0 in that bit position from the array.
Please, always link the problem source along with your question.
Can you please explain the dp part more vividly, I am having a hard time understanding it .
If you had solved any digit dp problem you'd know what I'm talking about. I'll explain it if you could change to [0, r] then.
dp[i][0/1] = max answer if we're filling the i-th bit from most significant to least significant and a boolean flag that says if the prefix currently filled is equal to the prefix in r. If the flag is off, it's different so we can choose anything: dp[i][0] = max(taking 0 here + dp[i+1][0], taking 1 here + dp[i+1][0]). If it's on and the current bit is 0, we must take 0 otherwise we take a number greater than r so dp[i][1] = taking 0 here + dp[i+1][1] and if it's on and the current bit is 1, we can take 0 and make the prefix smaller or take 1 and keep the prefix equal so dp[i][1] = max(taking 0 here + dp[i+1][0], taking 1 here + dp[i+1][1]).
One thing I would like to ask. I can use two flag to check if X is a prefix of r or l respectively. Can we do this with just one flag? Because I don't know how to reduce thisit in this form like $$$f(l,r)=g(f(0,r),f(0,l))$$$
For this problem you can't since you want max. If you wanted the count of some property you would be able to do f(r) — f(l-1) probably but here it's different.
Yes. Can you share your view on the 1st part means if you can do this with just 1 flag?
Edit: sorry if I misunderstood. Your answer is no for both the part?
Use 2 flags. I'd make the extra state a bitmask of 2 bits.
Another way to look at the dp solution above is that, if you imagine fixing the value of $$$x$$$ bit-by-bit MSB to LSB (in a backtracking-like approach, or more specifically D&C, if that's more towards your style), then if at some point in the recursion you detect that you could fill the remaining bits with any values you want (e.g. you can guarantee that $$$1011?????_{(2)}$$$ would be inside $$$[L..R]$$$ for all assignations of bits to the question marks), you can essentially switch to greedy, and pick the best choice to fill them. This essentially reduces the number of interesting candidates of $$$x$$$ to $$$O(log(R))$$$ (try to prove that).
Another way to think about this problem is as of splitting the segment $$$[L, R]$$$ into $$$O(\mathrm{bits})$$$ segment tree vertices, in the same way as we do with segment tree queries. Indeed, if $$$[L, R]$$$ is a vertex in the segment tree, then some prefix of bits of the number $$$x \in [L, R]$$$ is fixed, and the remaining bits can be chosen arbitrarily. Hence, in each of those $$$O(\mathrm{bits})$$$ subproblems, all bits are independent and it is easy to solve them in $$$O(\mathrm{bits})$$$ time each after some precomputation.
Exactly what I wanted to point out. I think this approach might prove a lot more straightforward in a lot of scenarios where intended solution is digit dp. I guess it goes without saying that you can extend this idea to your needs (e.g. base 10, if problem requires it).
Perhaps the biggest downside is that it would be more complicated to adapt for the case where the number of digits is up to 1 million, though.
Auto comment: topic has been updated by deepkamal (previous revision, new revision, compare).