can someone explain the O(n) approach for C .

The problems might be too difficult for me, but there's no doubt that the illustration in each problem is beautiful!

I recognized the entire solution to H during the contest except that I don't have a template or know how to compute min cost matroid intersection. I know how to compute maximum cardinality matroid intersection only. Does anyone have a good resource about the weighted case?

I did not know the relation used in D and was very happy to solve it without using the relation.

Basically you can perform both operations for (n-1) pairs (0,1), (1,2) ... (n-1,n). if the jth bit is set in the 'and' value, then jth bit of both numbers is 1. if the 'or' value is 0, then jth bit is 0 for both the numbers.

Now some bits will be left unknown but they will always be alternating. For any bit which has atleast one 1 or one 0. We can know all the other bits.

If we have no knowledge on some bits. We can perform 'and' and 'or' on 1st and 3rd element because their parity will always be the same for all the unknown bits. After knowing these two numbers we can get all the others as well.

Can anyone help me figure my mistake for B I am unable to find and stuck for hour now :( https://codeforces.net/contest/1556/submission/127399981 upd: Got it AC'ed finally :)

In the solution for C, while describing balance I think it might have been intended to write c_{l+3} instead of c_{l+2} twice.

There is a ~$$$\frac{5n}{3}$$$ query solution to D. The main idea is to find the values of each group of $$$3$$$ elements in $$$5$$$ queries. First note that $$$(a ^ b) = (a & b) ^ (a | b)$$$, so you can find the xor of two indices using only the and and the or. Now if you want to find the values of the elements $$$(a, b, c)$$$, first query $$$(a & b)$$$ and $$$(a|b)$$$ to get $$$(a \oplus b)$$$, query $$$(a & c)$$$ and $$$(a|c)$$$ to get $$$(a \oplus c)$$$. Now $$$(b \oplus c) = (a \oplus b) \oplus (a \oplus c)$$$, so you get $$$(b \oplus c)$$$ for free. Another important fact is that $$$(a+b) = (a ^ b)+2*(a & b)$$$. You can get $$$(a+b)$$$ using $$$(a \oplus b)$$$ and $$$(a & b)$$$ (both of which were queried earlier). You can get $$$(a+c)$$$ the same way. You can query $$$(b & c)$$$ to find $$$(b+c)$$$. Now you have the values $$$a+b, a+c, b+c$$$, and you can just solve the system of equations on paper to get the values of $$$a$$$, $$$b$$$, and $$$c$$$. Thus, you can get the values of $$$3$$$ elements with $$$5$$$ queries, making the total number of queries $$$\frac{5n}{3}$$$. Note that if $$$n$$$ is not a multiple of $$$3$$$, you can use $$$2 \cdot (n \mod 3)$$$ queries to get the remaining two elements (by querying the xor of those elements with an element you already know).

Sorry for the issues with latex, it doesn't like & for some reason (using \& doesn't work either).

Nice round.I did enjoy the struggle even though I lost rating :).

Does anyone have a nice explanation for the inclusion exclusion formula in F? I'm struggling with the G(sub) factor in the subtraction

linear solution for C 127401730

I think D is an easy version of 1451E1 - Bitwise Queries (Easy Version)

I'm not the first one to notice it, but the tests for E were quite weak. My contest submission used the fact that arrays a and b play a similar role (which of course they don't), and can easily be hacked with arrays of size 2.

Nonetheless, it passed the 80 main tests and got Accepted.

I understand that making tests is not a perfect science, but how did something this big slipped through ? Even with random tests, this seems unrealistic, as simply swapping the two arrays should cause it to fail.

Can someone tell me the solution to problem E please?

I'm a fan of problem G but...

Do you store all the edges? Do you sort them by the time they need to appear?

From your complexity, it seems that you don't have a better bound for the number of edges than $$$O(mn^2)$$$. That's a lot. During the contest I think I have proven ($$$V$$$ is the number of vertices) $$$V \le 2m(n+1-k) + 2^{k}$$$ for any $$$k$$$, which roughly means $$$V \le 3.5 \cdot 10^6$$$. I think I have also proven ($$$E$$$ is the number of edges) $$$E \le V \cdot n / 2$$$, which will get us $$$E \le 9 \cdot 10^7$$$. That is an awful lot of edges. We can barely store them thanks to 1 GB ML, but to sort them by the time of appearance we should either use in-place sort, I know only of $$$O(E \log E)$$$ ones, and that sounds like TL, or use counting sort, which is $$$O(E)$$$ but not in-place. I did counting sort in the following fashion: generate edges, count them (for counting sort) but don't store them, then generate them again and now store in right places.

I actually assume that it is really hard to construct tests of reasonable strength, but why set so high limitations then?

I wonder how many solutions on E passed systests but fail this test case:

2 1
1 0
0 1
1 2

Thanks for great problems , i have learnt a lot!

My randomized greedy solution during contest got WA on test 133. I optimized it for a little and it passed all tests now. Can anyone hack me?

I don't know but why Deltix don't decide to update the testcase in E and rejugde all the submissions?

Can anyone please help with understanding the formula in Problem C editorial? Basically, the solution has the following skeleton.

      for (int l = 0; l < n; l += 2) {
          long long balance = 0;
          long long minbalance = 0;
          for (int r = l + 1; r < n; r++) {
              if (r & 1) {
                  // MAGIC HERE
                  balance -= c[r];
              } else {
                  balance += c[r];
              }
              minbalance = min(minbalance, balance);
         }
     }

Now, if $$$minbalance < 0$$$, then we take $$$-minbalance$$$ opening brackets out of $$$c[l]$$$ to fix the issue, ending up with $$$c[l] + minbalance$$$ opening brackets. If that value is negative, there is no way we can create a correct bracket sequence as we are lacking the opening brackets. On the other hand, if $$$c[l] + minbalance > 0$$$, then we can take $$$c[r] - balance$$$ closing brackets, and so the answer in this case must be $$$min(max(c[l] + minbalance, 0), max(c[r] - balance, 0))$$$.

If $$$minbalance > 0$$$, then we can take $$$c[l]$$$ opening brackets and $$$c[r] - balance$$$ closing brackets, having $$$min(c[l], max(c[r] - balance, 0))$$$ as the answer for this case.

Clearly, my reasoning here is utterly wrong. Can you please advice how to think here in the right way? Thank you!

In D,why a+b=(a or b)+(a and b)， not a+b=(a or b)+(a and b)<<1 ?

127410355 AC a+b=(a or b)+(a and b)

127409931 WA a+b=(a or b)+(a and b)<<1

Another approach for D: If a bit appears in x | y and not in x | z, y will have the bit.

We can use this fact to calculate the whole array.

I think there is something wrong with the second formula in the solution for F.

I tried to simulate it.And when n is equal to 3,$$$F((11)_2) \neq 0$$$,but it is obviously wrong.

I have a doubt in first part itself: In example say I want 5,3. I add 1 to both a,b. Now the value of k = 4. and with second operation, I add it to a and subtract it from b. which makes a=5 and b = -3. Can someone explain me how are operations justified ? .... Thanks for explaining. 300iq

My solution on G used $$$O(nm)$$$ DSU operations.

You don't need to split each interval into $$$n$$$. Notice for any nonnegative integer $$$x$$$, $$$[0,x]$$$ is connected. Thus it's enough to split an interval into two (from the LCP of both endpoints).

To find the edges, iterate digits, using two-pointers method to find pairs of intervals that contains a pair of numbers whose difference is $$$2^k$$$. There are $$$O(m)$$$ of them on each digit, so the total number of edges is $$$O(nm)$$$.

can anyone please give any testcase for Div2B that fails my code i have implemented with same logic that editorial says. my code verdict WA on test case 2 ,wrong answer 17th numbers differ — expected: '3', found: '1'

/*  CREATED BY
    STREAM_CIPHER
    aug-2021
*/
#include<bits/stdc++.h>
using namespace std;
void __print(long long x) {cerr << x;}void __print(unsigned long long x) {cerr << x;}void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define int long long int
#define double long double
#define fix_precision(n) cout<<fixed<<setprecision(n)
#define all(a) a.begin(),a.end()
#define endl "\n"
const double pi=acos(-1.0);
int inf=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
// const int mod=998244353;
const int mx=5*1000000;//5*64M bit ->5*8M byte ->40MB size for long long int (64 bit) // long long can cause TLE
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    #endif
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<int>a(n+1);
        // arr.clear();
        int one=0,zero=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            one+=(a[i]%2==1);
            zero+=(a[i]%2==0);
        }
        if(abs(one-zero)>1){
            cout<<-1<<endl;
        }
        else{
            vector<int>see;
            int ans=inf;
            for(int i=1;i<=n;i++){
                if((a[i]%2)!=(i%2)){
                    see.push_back(i);
                }
            }
            int temp=0;
            for(int i=1;i<see.size();i+=2){
                temp+=see[i]-see[i-1];
            }
            // debug(see);
            if(see.size()%2==0)
                ans=min(ans,temp);
            see.clear();
            for(int i=1;i<=n;i++){
                if((a[i]%2)!=((i+1)%2)){
                    see.push_back(i);
                }
            }
            temp=0;
            for(int i=1;i<see.size();i+=2){
                temp+=see[i]-see[i-1];
            }
            if(see.size()%2==0)
                ans=min(ans,temp);
            cout<<ans<<endl;
        }
    }
}

Nice problems!

My explanation for F :- its clear that we want to calculate for some subset the probability that it is strongly connected, to do that observe that if some mask is not strongly connected then consider all its strongly connected components their would exist some node (in SCC) with zero in degree. Now their would exactly one such node as each pair of nodes have some edge b/w them (crux of the problem), we iterate on this submask and calculate its contribution. my submission

Please, write the editorial of Problem E.

https://codeforces.net/contest/1556/submission/127394438 Can anyone review my code, it is failing at test case 17, can you please suggest som good test case. https://codeforces.net/contest/1556/submission/127400247 this one is failing at case 13

The shortest solution of Problem H:

1. Choose a valid spanning tree.

2. Use simulated annealing algorithm, randomly delete and add an valid edge each time.

Code:https://codeforces.net/contest/1556/submission/127455481

"$$$−c_{l+1}+c_{l+2}−c_{l+2}+… as balance$$$"

Is there a problem with this sentence? Nothing is done like this one plus one minus

where E?

Can someone tell me how to solve problem E ? :(

I try to present my thoughts and my solution for Problem E. I had 45 minutes left, when i tried solving this task, so what I did was looking at small examples. The examples gave me an idea what the solution could be and lo and behold it got accepted. Let's get to it.

My first example tried to find out, how many steps do we need to equalize the values of the query, if it is solvable? Let's look at this:

We can see, that we obviously need 21 operations. Each operation can always take only 2 Elements at once. I calculated the differences $$$b-a$$$ and built the prefixarray on those differences. My assumption was: If it is solvable, then we have to take the maximum value of this prefixarray. That is the amount of operations we need. We can verify it with some more examples. if we double the arrays $$$a$$$ and $$$b$$$ (so $$$a$$$ will be 000777000777)? Yes, we still get 21! We need to adjust twice the values, but we can pick 4 elements at once for each operation!

Now I want to find out, when is it impossible to equalize the arrays? Of course it is impossible, if the sum of $$$a$$$ is not equal to $$$b$$$. But there are cases, where the sums are equal, but it is still impossible:

In the left example, we cannot increase $$$b_1$$$. So this case is not possible. In the second case, we could increase $$$b_2$$$, but that would lead to us needing to increase $$$b_1$$$ to $$$4$$$. So this case is impossible too. My assumption was: If we have a negative value in the prefix sum, then it is impossible.

Turns out, those are the ideas needed to get AC.

Rest was creating the right datastructures. Prefixsum is easy to generate. Now we need a data structure, to obtain the maximum and the minimum values from the prefixsum $$$[prefix_l, prefix_{l+1}, ... prefix_r]$$$. This can be done with a segmenttree (I guess there are simpler data structures for this, we do not need updates). We obtain $$$prefix_{min}$$$ and $$$prefix_{max}$$$. We still need to subtract $$$prefix_{l-1}$$$ from our values, to obtain the right numbers (to obtain, like in the examples, $$$prefix_0=0$$$).

So the solution is: If $$$prefix_{min}-prefix_{l-1}$$$ is smaller than $$$0$$$ or if $$$prefix_r-prefix_{l-1} \neq 0$$$ (the sums of the subarrays are different), then there is no solution. We can output $$$-1$$$. Else there is an solution in $$$prefix_{max}-prefix_{l-1}$$$ queries.

Complexity is $$$O(N log N)$$$ for preparing the prefix sums and segment tree, and then $$$O(Q log N)$$$ for answering the queries, in sum $$$O((N + Q) log N)$$$.

Here is my submission: 127385969

I tested my solution to problem H locally using this solution and randomly generated graphs. On a case the solution reported answer is 1e9.

I submitted the test to Hacks, but Unexpected verdict is given. Such a verdict is previously discussed here.

The test is attached below:

10 1
3
2 1 3 3 4 9 3 1 5
5 3 6 2 3 4 2 5
10 5 5 6 8 9 6
7 5 5 7 3 10
5 6 6 6 3
5 10 10 3
2 2 3
2 7
4

Can someone give some help? Thanks.

It is possible to solve $$$D$$$ with at most $$$2n-1$$$ queries.

In problem F why do we it why do we insist that every x in the set winners has an edge with every y in the set of ALL\winners? Since the set of winners contains a cycle isn't it sufficient that for every y in the set of ALL\winners the exist some x in winners such that there is an edge from x to y?

When will the solution for E be published?

Can somebody explain to me the editorial solution of C, I am not able to understand it even after multiple reading...

For F:

Can we just calculate every one's contribution independently,let's denote we make I be the winner and I have defeated the S(include I) and we want to defeat j , the transition is dp[S|(1<<j)] = mul(dp[S|(1<<j)],f[S][j]) ,f[S][j] means that the probability defeat j with at least one member in S.

How can we hack the thought.... I code it and fail on the test2... Can someone hack me,please,I almost be mad....

thanks for the editorial,

I didn't know this fact in problem D 1556D - Take a Guess

here is my solution which performs 2*n - 1 questions

knowing the first number in the array we can get the rest of the array

let the array be [x, y, z]

y = (x&y) | (~x & (x|y))

z = (x&z) | (~x & (x|z))

it's not hard to prove why this is correct

you just need the value of x and

all values of x&(other n-1 elements)

all values of x|(other n-1 elements)

assume the array is [x, y, z]

to Compute the value of the first number let it be x

initially, the value of x is x&y | x&z

and now for each bit i in x if it is not set

how to know it must be set in x?

first, to know it must be unset, we just see the values of x|y, x|z

if the $$$i_{th}$$$ bit is unset in at least one value of those then it must be unset in x

else

there are only two cases:

1- $$$i_{th}$$$ bit is set in x only.

2- $$$i_{th}$$$ bit is set in all other numbers except x.

we can check the second case by asking about & between any two numbers except x

if the $$$i_{th}$$$ bit is set in the result then the second case is true

else the first case is true and adds 2^i to x.

here is my solution for better understanding, hope it helps :D

128722532

pls upload tutorial for problem E