| # | User | Rating |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 153 |
| 2 | nik_exists | 151 |
| 3 | maroonrk | 150 |
| 4 | maspy | 149 |
| 5 | AmShZ | 146 |
| 6 | Um_nik | 143 |
| 7 | Errichto | 139 |
| 8 | adamant | 135 |
| 9 | BledDest | 134 |
| 10 | cry | 130 |
|
0
I tried to solve it by first creating the MST and then applying DP on this tree to get the values for each node. It turned out to give me a WA. Can someone please explain why this didn't work? |
|
+1
Well I can try explainging the transitions. The transition dp(i+1,0) is straightforward. The transition dp(i+2,1):-> Suppose the array is ---(----)--- and the array elements within paranthesis denotes the subarray(from index 4 to 8) we need to reverse then when we are at index 4 then we start to reverse the subarray and the transition will be from 4 we need to got 6 with values reversed hence we need to take the value of dp(4,0) but at index 6 we will make a transition to 8 and notice that when making this transition the maximum value will be for dp(6,1) not dp(4,1). This type of reversal is taken into account because the reversal of an array of size 2x is same as reversing array of size 2 in x moves hence dp(i+2,1)=max(dp(i+2,1,max(dp(i,0),dp(i,1))+(i%2==0?a(i+1):a(i)) The last transition dp(i+1,2):-> Now suppose we are at an index where we have ended reversing the subarray then at this index what transitions we are left with are the max sum until index i + the sum at remaining even indices therefore the transition looks like dp(i+1,2)=max(dp(i+1,2),max(dp(i,0),dp(i,1),dp(i,2)+(i%2==0?a(i):a(i+1)). |
|
0
Thanks I got it now. |
|
0
Can someone please tell me what's wrong with my submission to C? https://codeforces.me/contest/1367/submission/83970779 |
|
0
How did you come up with this? Was this just an observation or something u knew beforehand? |
|
0
because suppose the highest bit is 2 that will be 100 but the time this would have occurred will be 3 seconds(1,2,4). Due to this, we need to add 1 to the highest bit that we obtain. |
|
0
While traversing the array keep a count of what maximum difference have you seen so far from the previous element i.e maximum value uptil that i minus the array value at that i. Then once you found the maximum difference than going for finding the position of the highest bit in this maximum difference. The ans is going to be the value of this highest bit + 1. Make sure to include the edge case that if the maximum difference is 0 then the ans is also 0. |
|
0
consider the case of three numbers (v-u)/2,(v-u)/2 and u. The xor of these three numbers will always be u as (v-u)/2 xor (v-u)/2 is equal to 0. Hence for every case, we can say that the minimum length array will be 3. |
|
0
The RHS becomes 1 but LHS is 3? |
|
0
How come a⊕b≡a+b mod2 consider a=2 and b=5 then how the above holds? |
|
0
since a^b=a+b-2(a&b) now you are given a^b as u and a+b as v therefore u=v-2(a&b) 2(a&b)=v-u as our ans is [a,b] as elements of the array in case there exists 2 elements therefore v-u has to be even for a solution to exist. |
|
+3
Thanks for such a clear explanation. |
|
0
Can you give an example of the same? |
|
0
What is the need of dividing the remainder by 2 and putting the 2 bits in the positions having 1 in the binary representation of the remainder? |
|
+3
Can you please explain the approach you have used to solve it? |
|
+1
Is there any formal proof of it? |
|
0
In D how can we say that the max length of such an array can be at most 3? |
| Name |
|---|


