Lightning Fast Editorial.

Thanks for the Video Solutions.

Liked problem E and really disappointed about not solving it :(

This contest had a great difficulty curve. Kudos!

Weak test cases in problem B. Under the given condtions no precomputation should give TLE as no condition was given to limit the sum of all values of a.

Edit: Obviously I mean TLE only for those who have calculated XOR everytime in O(a).

Didnt got an approach to solve C. Were you able to solve C problem

seen/good

I knew how to solve E the moment I saw it, too bad I suck at implementation. Back to practice.

I think C is more difficult than D. Tutorial of problem D is much more difficult than mine. My solution works O(n)

Problem E is great but didn't understand the 11th base for problem D :(.

For me at least, C is the type of problem that seems quite hard, then, when you see the editorial, you realise it was really easy and you were the one who complicated it.

Wow! The solution for C is really cool! I got a kinda brute-force solution in O(2^log10(n)). Fixing which digits are going to add in such way that, it would create a carry. Then just checking how many pairs satisfy that kind of fix carried addition. Here is my submission link Link !

I thought of an algorithm to F, 127979513, that came up to mind when simulating filling the grid by hand. However, this algorithm failed Pretest #6, and I don't know where it went wrong, nor am I able to come up with a counter-testcase for it. The algorithm is as follows.

• Create an array $$$ans$$$, which is our answer. Initially, all elements of $$$ans$$$ are $$$0$$$.

• First, check if a marked cell has an odd number of unmarked cells. If true, then there must be no grid that satisfies the condition. Else, for each marked cell $$$(x,y)$$$ with $$$n$$$ neighbors, $$$ans[x][y] = \frac{5n}{2}$$$.

• Create an array $$$req$$$. $$$req[i][j]$$$ is initially $$$0$$$ for unmarked cells and $$$ans[i][j]$$$ for marked cells. Think of $$$req$$$ as the sum which we still need to 'distribute' to adjacent cells. We will subtract from $$$req$$$ when we update the neighbors of marked cells such that at the end, $$$req[i][j] = 0$$$ for all $$$i$$$ and $$$j$$$.

• Iterate through each cell in $$$ans$$$. For each unmarked cell with $$$ans=0$$$, update its value with $$$1$$$.

Updating a cell goes as follows:

• To update an unmarked cell by $$$a$$$, set its value to $$$a$$$. Then, update all adjacent marked cells with $$$a$$$.

• To update a marked cell at $$$(x, y)$$$ by $$$a$$$, subtract $$$a$$$ from $$$req[x][y]$$$. Then, if $$$req[x][y] = 1$$$ or $$$2$$$, we know that all remaining unmarked neighbors of $$$(x, y)$$$ should contain $$$1$$$. Thus, update them by $$$1$$$. The same thing happens when $$$req[x][y] = 4$$$ or $$$8$$$, where all its remaining neighbors should be $$$4$$$.

Does anybody have any idea on where or why it breaks down? Any help would be appreciated.

I suppose there is a mistake in explanation for problem C as $$$9 + 13 = 22$$$

can anybody explain why we are doing (a + 1) * (b + 1) — 2 after spliting it to 'a' and 'b' ? in problem C

I did D by simply printing the largest possible power of 10 (say x) such that (s-x) ≥ (n-1) in a loop while n is greater than 1. Finally printed whatever remained of s. This works in O(n).

E is a very standard problem. I don't see it appropriate for a Div2 Round. I guess it would be better in a D of an Educational Round.

Lightning-fast editorial with video solution. Nice Job

I know how to solve F, but I didn't read it during this round. What a pity. MySolution

Editorial of problem C is really good.

Wow, solution to C is incredible!!

Did anyone solve C using brute force in o(2^n) like either consider the carry or don't consider the carry?

When I try to access C Submission link CF says: "You are not allowed to view the requested page"

why Alice and Bob do weird things :(

Can someone help me to debug this code Q(B) — MEX or Mixup

include <bits/stdc++.h>

using namespace std;

int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); long int t = 1; cin >> t; while(t--) { long long a,b; cin >> a >> b;

long long all = 0;

    a--;

    if (a % 4 == 0)
     all = a;

    if (a % 4 == 1)
      all = 1;

    if (a % 4 == 2)
     all =  a+1;

    if (a % 4 == 3)
     all =  0;


    a++;

    // cout << all; 
    if(all == b)
    {
        cout << a << '\n';
    }
    else
    {
        if(b^all != a)
        { 
            cout << a+1 << '\n';
        }
        else{
            cout << a+2 << '\n';
        }

    }
}

}

I can't see the implementations. Even after solving the problem it doesnt let me check them.

problem C was irritating to be honest

C question was really good and tricky and thank you for the contest and very fast tutorial

Question D was just amazing and liked the logic behind C and D. It was very good contest

I can't view the codes in the tutorial. It says-'You are not allowed to view the respected page'.

In Problem D there is an ambiguity in the statement- the decimal number may not be uniquely interpreted in the 11-based system, for example, 100_{10} -> 100_{11} = 0 + 10*11 = 110_{10} or 100_{10} ->100_{11} = 0 + 0*11 + 1*121 = 121_{10}

After seeing solution to E, I started to wonder what Segment trees can't do.

Maybe it can even end world hunger in O(nlogn)??

Someone please link memoisation based Dp solution for problem C. Mine is giving wrong answer at test 5.

You can calculate XOR of first $$$n$$$ natural numbers in $$$O(1)$$$. You can learn more about that here.

flame, please lmk how to be as orzosity as you

thanq

The video is really great

[submission:https://mirror.codeforces.com/contest/1567/submission/127980698] O(n) solution for problem D

I think F can be transformed into a 2-SAT problem (maybe easier to think for some people): If one marked cell has an odd number of adjacent empty cells, obviously there's no answer.

Otherwise if it has 2 adjacent cells, one must be filled with true (representing 1) and the other must be filled with false (representing 4). Let the two cells be $$$a$$$ and $$$b$$$, we have the relation $$$(a \lor b) \land (\neg a \lor \neg b)$$$.

If it has 4 adjacent empty cells, it's always better to fill the opposite empty cells with the same number, and we can get a similar relation as the above case.

Was so close to solving B but missed the case when xor of a-1 and b is equal to a :(

I used a recursive algorithm for solving problem 1567C - Carrying Conundrum

128012196

The algorithm is based on the idea that as $$$2 \leq n \leq 10^9$$$, the 2-digit carry operation can be expressed in terms of the decimal digits and the carry bit using at most 10 linear equations.

If the decimal representation of $$$n$$$ has $$$k$$$ digits, where $$$1 \leq k \leq 10$$$, then the equations relating the least signification two digits $$$n_0$$$ and $$$n_1$$$ do not have carry-in bit. Similarly, the equations relating the most significant two digits $$$n_{k-2}$$$ and $$$n_{k-1}$$$ do not have carry-out bit. Therefore, there are at most $$$2^{k-2}$$$ possible distinct states for the binary vector of $$$k-2$$$ carry-out bits.

It is noted that the $$$k$$$ equations are separable into two independent sets of linear equations according to the odd/even parity of the digit index. This leads to the same solution given in the editorial for partitioning $$$n$$$ into two numbers $$$a$$$ and $$$b$$$, with the conventional 1-digit carry, where the answer can be computed as $$$(a+1)(b+1)-2$$$.

I am an absolute noob :’(. I got the idea of problem B but could not be able to find anything on the Internet about the formula for xor of 1…n. So bad. Anyway I love the editorials and thank you all for an awesome contest.

In problem B, Should the elements of the be distinct?

D can be done in $$$O(n*log_{10}(s))$$$ as well with simple recursion. https://mirror.codeforces.com/contest/1567/submission/127976931

In problem C(Carrying Conundrum), Could anyone please tell Why we are subtracting 2?

I feel like the Editorial to Problem D doesn't carry all cases, so I did a visual explanation.

Take $$$s=113$$$ and $$$n=7$$$. First we split the decimals into powers of $$$10$$$:

We could still need more numbers to fully get $$$n=7$$$. So we look for the smallest number $$$>1$$$:

An we split it into $$$10$$$ equal parts. To achieve this you can just replace this number with a tenth and then push back this value 9 times:

We repeat this step, until we have at least $$$n$$$ values. The editorial proposes a $$$O(n \log n)$$$ solution for this step using a priority queue, but this can also be done in $$$O(n)$$$ if we keep 2 separate arrays, one for numbers $$$>1$$$ and one for numbers $$$=1$$$. The former one will be automatically sorted at all times following this procedure.

In the next step we could have more than $$$n$$$ numbers. We just collect the overflow and add it to the last value:

And we are done:

Special Thanks to flamestorm for problem-C !!!

Thank you for that round, the problems were really interesting. BUT!!! Maybe C and D should be replaced)

E is the hardest to me.

Why are we doing -2 in (a+1)(b+1) in the editorial of problem C.

can anyone explain query part of problem E

1567F : As I can see, those who got AC in the contest had simpler solutions than the author. The editorial is quite general, I think. Just curious how this problem can be extended.

color[u] = (color[v] ^ 3); What is the purpose of this code?

I also don't understand the aim of the below part of the code in the solution for F. Can someone explain further. Thanks.

// flip each cell appropriately, column by column
    for (int j = 1; j <= m; j++) {
        int curr = (j % 2 ? 4 : 1);
        res[1][j] = curr;
        int prev = color[val[1][j]];
        for (int i = 2; i <= n; i++) {
            if (grid[i][j] == '.') {
                if (color[val[i][j]] != prev) {curr = flip(curr);}
                res[i][j] = curr;
                prev = color[val[i][j]];
            }
        }
    }

For problem E, the editorial's implementation is very suck.

I think there might be some mistakes according to tutorial of problem F. In the tutorial it said: "However, the tricky case is to deal with cells with 0 unmarked neighbors". But it is obvious that cells with 0 unmarked neighbors will get the value of 0 in the end. So what is really tricky to deal with is those cells with 4 unmarked neighbors. I think the writer might confuses the definitions of marked and unmarked cell.

E editorial seems a bit impl heavy. My solution is a lot shorter(50 lines).

Basically, each node stores the following: answer for the range, longest non-decreasing prefix, longest non-decreasing suffix, size of range, 1st and last elements in the range. I won't explain the combine part as it's easy to understand from the code. Also, notice you could just store l,r for range instead to take care of the last 3 parts but I decided not to store the elements in an array.

Solution

can someone tell me where this submission might be failing ?

I am in a trouble with the last note of Problem C, "Note that pairs (a,b)and(b,a) are considered different if a≠b." Could anyone give me a proper explanation, please?