As someone who got WA pretest 8, was G doable with flows?

I solved upto E in the contest and have ready code for F to submit now lol. Amazing problems.

How to solve problem b for l and r less than equal to 10^9.

Hey! I actually found some different solution for problem C and I guess it's supposed to work? I started with the same observation than the editorial: we will consider the count of different types of candles.

The four types are: $$$10, 00, 01, 11$$$

We can apply operations on types: $$$10$$$ and $$$11$$$ because these types are the only ones having the candle of string $$$a$$$ setted to $$$1$$$ (and we can only to operations on $$$1$$$ candles)

Now, what will happen if we apply an operation on a char of type $$$10$$$ ? Let's call $$$[a_ib_i]_{old}$$$ the count of the type $$$a_ib_i$$$ before the operation and $$$[a_ib_i]_{new}$$$ the count of the type $$$a_ib_i$$$ after the operation.

So if we apply an operation on a char of type $$$10$$$ we'll have:

$$$[10]_{new} = 1 + [00]_{old}$$$

$$$[01]_{new} = [11]_{old}$$$

$$$[11]_{new} = [01]_{old}$$$

$$$[00]_{new} = [10]_{old} - 1$$$

In a similar way we can find how $$$[a_ib_i]$$$ will change if make an operation on a char of type $$$11$$$.

Furthermore, doing the same operation twice is useless as we will comeback to the same string.

As an operation only do a small local change (+/- 1) and let two counts invariant (it just swaps them) we may think there is not that much reachable strings.

So one could implement a BFS where the nodes contains the count of each type and the transitions are: apply operation on $$$10$$$ or apply operation on $$$11$$$.

It appears that it works quite fast. Here is my AC code (~90ms): 140494838

I have some intuitive ideas of why it's fast. I'll try to think a bit more and I'll update this comment if I found something :)

How to do B??? :(((( Can someone give an easy explanation plzzz!

I'm not sure, but I think that it's possible to solve H using slope trick.

Just wanted to say, D was brilliant

Tasks are good but time to think about them no so much :(

Can anyone give the proof of bonus in problem C?

Problem D was very nice imho.

Hey !

I actually solved $$$C$$$ quite differently. First check if two strings are equal if yes answer is $$$0$$$. Otherwise, Consider two pairs: $$$E$$$ = (count of equal $$$0s$$$, count of equal $$$1s$$$) and $$$NE$$$ = (count of not equal $$$0s$$$, count of not equal $$$1s$$$). Consider these two pairs as starting state. Now, we can simply run $$$BFS/DFS$$$ to check if we can reach to goal state which is $$$E$$$ = ($$$0$$$, $$$1$$$) and $$$NE$$$ = ($$$x$$$, $$$y$$$) where $$$x + y = N - 1$$$. This is the goal state because last move we do will have this kind of form. At each step, we can either take $$$1$$$ from $$$E$$$ or $$$NE$$$ and then we swap $$$N$$$ and $$$NE$$$ (we also swap number of $$$0$$$s and $$$1$$$s in each pair while handling picked $$$1$$$ separately). If we can't reach goal state answer is obviously $$$-1$$$ otherwise we can simply output current level of $$$BFS/DFS$$$. I had an intuition that this process will not continue forever and will end in after some small number of steps (I didn't prove correctness do reply if you can prove it).

My Submission

Another way to solve $$$C$$$:

First of all, selecting the same candle twice will not change anything, so each candle will either be selected once or not at all.

If we select $$$x$$$ candles, the number of ones in them must be $$$\lceil\frac{x}{2}\rceil$$$, because the sequence of selected candles must be those with initial values 1010101...

If $$$x$$$ is even, at the end the selected candles will be inverted and the others will not. If $$$x$$$ is odd, the selected candles will not change and others will be inverted.

As we know the invalid candles that need to be inverted having count $$$cnt$$$, if $$$cnt$$$ is even we can try to select the invalid candles, and if $$$n-cnt$$$ is odd, we can try to select the correct candles.

At the end take the minimum answer found or -1 if both trials failed. If a trial succeeds, its answer is the count of selected candles.

I have solved so many problems similar to problem D and yet again during the contest struggles to do it

Problem E has an N*sqrtN*logN solution which is good enough to pass system tests but can be hacked. I hacked 1 and 2

Does anyone know the ratings for each of the problems?

i went to youtube to see the explanation of problem C and i saw it

youtube.com/watch?v=B9Xr3tm5_K4

In the editorial for problem F, $$$p_{ij}$$$ is defined as the number of ways to get $$$\sum_{i=1}^{k} |a_i-b_i| = j$$$. I think the $$$\sum_{i=1}^{k}$$$ shouldn't be there.

In problem B

What I did is count the number of 0s of every array element at every bit position and the ans will be the minimum of all those counts

My solution

Its complexity is O(32*n) which should pass the given constraints, isn't it?

since the maximum constraints is 2*10^5.

Am I wrong?

The Problem H is well-known in China...

Hello Monogon, I think there is a typo in your editorial.

In problem H's editorial,

If there is any node u such that $$$s \rightarrow u$$$ and $$$u \rightarrow v$$$ both have flow, make them both have 0 flow, and this won't change the cost.

I think it's supposed to be $$$s \rightarrow u$$$ and $$$u \rightarrow t$$$, right?

which problem was interactive ?

https://mirror.codeforces.com/contest/1615/submission/140504399 problem B. I dont know why i got a time limit error at pretest 3 .

Is there anyone can use DP to solve problem E? Thank you in advance.

[ignore, sorted] i was returning without taking complete input on a multi — test.

Problem D was not original. I think a similar problem appeared once on codechef PARITREE

Can someone explain why we only check bits 1-30 at problem B? Shouldnt we also include the 0th bit?

could someone elaborate the bonus statement of problem C

I only want to know how to find the Key observation of 'F'? It is too difficult for me.

where is D problem standard code?

Problem C : Menorah

My Code with explanation : click here

// we will change 1-1 and 1-0 alternatively because
//  if we changes same pair twice or more times consecutively than it will nullify the previous change
//  for ex. changing 1-1 (odd number of times consecutively) is equivalent to changing 1-1 (only once).
//         same for changing even no. of times which is equivalent to changing 0 times;

int go(int a, int b, int c, int d, bool flag) {

    // if flag == 1 : it's time to choose 1-0 else 1-1
    // c1 : 1-1
    // c0 : 0-0
    // w1 : 1-0
    // w0 : 0-1
    // x-y : x is the ith character of first string and y is the ith character of second(destination) string
    // a = c0, b = c1, c = w0, d = w1;

    if(c == 0 && d == 0) return 0; // no wrongs, only corrects

    if(flag) {
        // change 1-0 pair
        if(d == 0) return 1e9; // no more 1-0 left to change
    
        int c1 = c;
        int c0 = d - 1;
        int w1 = a + 1;
        int w0 = b;

        return 1 + go(c0, c1, w0, w1, 0);
    }
    else {
        // change 1-1 pair
        if(b==0) return 1e9; // no more 1-1 left to change

        int c1 = c + 1;
        int c0 = d;
        int w1 = a;
        int w0 = b - 1;

        return 1 + go(c0, c1, w0, w1, 1);
    }

} 


void solve() 
{
    string a, b;
    cin >> n >> a >> b;
    if(a==b) {
        cout << 0 << endl;
        return;
    }
    int mn = 1e9;

    int c1 = 0, c0 = 0, w1 = 0, w0 = 0;

    fr(i,0,n) {
        if(a[i] == '1') {
            if(b[i] == '1') c1++; // 1-1
            else w1++; // 1-0
        } else {
            if(b[i] == '1') w0++; // 0-1
            else c0++; // 0-0
        }
    }

    mn = go(c0, c1, w0, w1, 0);
    mn = min(mn, go(c0, c1, w0, w1, 1));

    if(mn > n) mn = -1;

    cout << mn << endl;

}
   

I'm not sure whether the proof in E is called contradiction or exchange argument. Can somebody elaborate?

Edit: Oh, the editorial is updated! There was the word "contradiction" sometime and I commented on that. I also had too many doubts about the first revision of the proof but everything is now clear to me. Thanks!

In problem D,how can I find out the final r_i for each node? Could anyone please show me a sample of the code to problem D?Thank you!

Nice contest!!

Can anyone share their code for C that worked? Thanks in advance

Why are we able to add a direct edge between nodes $$$a$$$ and $$$b$$$? Or more precisely, how is a path relationship converted into a parent-child relationship?

Also if we add direct edges, won't we be creating a graph rather than a tree? PurpleCrayon