if(sum % 2 == 1) — issue was here. If sum is odd and negative then sum % 2 will be -1, not 1

Just now, I submitted this for this straightforward bipartite problem, and it got accepted w/o any change in logic

mesanu

I am unable to figure out the issue with my problem F submission. I am simply following 3 steps:

if the summation of the difference is odd -> "NO"
else if (not bipartite graph) || (sumOfDifference(color-0) - sumOfDifference(color-1)) == 0 -> "YES"
else "NO"

I am trying to find the bug for the last 2 hours but no luck so far. Please help.

For problem D I tried the following for v > u

x = u
diff = v-u

for i:0 to 29
  if ith bit of x is 0 and ith bit of diff is 1:
    search for biggest j such that j < i & jth bit of x and diff are both 1
       if there is no such j then return "NO"
       if for any k between i & j:
          if kth bit of x and diff are both 0
                 return "NO"
return "YES"

But it is failing

I am unable to come up with a counter example. Please help

nicely explained!! thanks

Can we prove that at any layer there will be at most 2 distinct numbers? I tried a few examples and it seems to be working

Please ignore.. will ask here https://codeforces.me/blog/entry/86642

For F I understand that if y is even and the optimal answer is going to have a division operation then it is optimal to perform division right now. If y is odd then try both y-1 and y+1. It suggests that after at most 2 operation value will be halved. This way the height of the recursive tree will be log(y)=~60

I tried a few examples and it seems the number of states at each height is not growing very fast because of collision

Is there any tight upper bound for the number of states at each height and overall states in the tree?

sshwyR SecondThread Monogon — Since this post is ~ 2 months old, hence tagging few members. Please don't mind.

Can someone please explain the hashing part in Div2E? I understand that we want to compare the union of sets to {1, 2, 3, ..., n} using hashing e.g. union of {1, 2, 4} and {3, 5, 6} is equal to {1, 2, 3, 4, 5, 6}

I tried hash as product modulo prime but I got an error on 8th test case and I realized that this is not a good way to hash because it can generate same hash for distinct sets

Is there any blog/tutorial that I can follow to understand this? Any help will be appreciated

ddzzdefc was the culprit

This example is working fine

I have tried a lot but still stuck in Test 46. The above 2 examples are working fine. Any help/guidance will be appreciated

During the contest, I was able to derive this formula

G(n, m) = (m — n) * G(n — 1, m — 1) + (n — 1) * (n - m + 1) * G(n - 2, m - 1)

I am sure this recurrence is correct but this form didn't let the computation to be in O(N)

Thanks for sharing the formula @mickeyandkaka

Finally I understood. The above code is same as

ans = abs(A[N-1]-W);
if(N > 1) ans = max(ans, abs(A[N-1]-A[N-2]));

max(|B - a[n - 1]|, |a[n - 2] - a[n - 1]|)

I manage to solve Problem D: ABS. But I am still not sure whether my logic was correct or the test cases were weak. Please help.

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pii pair<int, int>
#define mod 1000000007

int N, A[2099], Z, W, ans = 0;
int main() {
    cin >> N >> Z >> W;
    for(int i = 0;i < N;i++) {
        cin >> A[i];
    }
    ans = abs(A[N-1]-W);
    for(int i = 0;i < N;i++) {
        int minm = abs(A[N-1]-A[i]);
        for(int j = i+1;j < N-1;j++) {
            minm = min(minm, abs(A[N-1]-A[j]));
        }
        ans = max(ans, minm);
    }
    cout << ans << endl;

    return 0;
}

DIV2 D using binary search on multiple intervals. CODE.