CP Brainfarts
Writing down my biggest brainfarts, or like scenarios where I just can’t possibly find an edge case… Accumulating Scar Tissue.
particles
I was so confused, it feels like this relationship is enough
dp[i] = max(a[i] + dp[i - 2], a[i]);But why doesn’t it work??
- I thought that you were only able to merge adjacent things with a gap of 2, but that was actually a brainfart, any two elements with a gap with a multiple of 2 can be merged. So it’s basically the largest subset. No need for fancy dp
Or actually, if you want to make it work, you should do
dp[i] = max(max(a[i], a[i] + dp[i - 2]), dp[i - 2]);I like this better (make sure you initialize dp[i] = a[i])
dp[i] = max(max(dp[i], dp[i] + dp[i - 2]), dp[i - 2]);it’s the difference between computing the largest subarray sum and largest subset sum.
subarray sum is dp[i] = max(a[i], dp[i-1] + a[i]) (continue the previous subarray or start a new one)
For subset sum, you would do dp[i] = max(a[i], dp[i-1] + a[i]) as well??? im comfused. nope its dp[i] = max(dp[i-1], dp[i-1] + a[i], a[i])
- you have 3 choices: the best subset doesn’t have this value, the subset includes this value, and it’s a new subset
Sums on segments (-1 or 1 except one number) https://codeforces.com/contest/2043/problem/C
- Really braindead how I thought that resetting was good enough, when the sum can become even more positive, so resetting is bad idea. Rather, keep track of the bounds
Almost multiples problem (, and ., you select other numbers with the smallest lexographical permutation) https://codeforces.com/contest/1758/problem/C
I was convinced my solution was correct.