flamestorm's blog

Codeforces Round #742 Editorial
By flamestorm, 8 months ago, In English

Thank you for participating in our contest! We hope you enjoyed it. UPD: Implementations have been added.

1567A - Domino Disaster

Solution
Implementation (C++)
Video Solution

1567B - MEXor Mixup

Solution
Implementation (C++)
Video Solution

1567C - Carrying Conundrum

Solution (Observation)
Implementation (C++)
Video Solution
Solution (DP)
Implementation (C++)

1567D - Expression Evaluation Error

Solution
Implementation (C++)
Video Solution

1567E - Non-Decreasing Dilemma

Solution
Implementation (C++)
Video Solution

1567F - One-Four Overload

Solution
Implementation (C++)
Video Solution
 
 
 
 
  • Vote: I like it
  • +237
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it +57 Vote: I do not like it

Lightning Fast Editorial.

→ Reply
»
8 months ago, # |
  Vote: I like it +26 Vote: I do not like it

Thanks for the Video Solutions.

→ Reply
»
8 months ago, # |
  Vote: I like it +44 Vote: I do not like it

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

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    E question not bad problem. don't freak out baby. decide when you wiser :)

    → Reply
»
8 months ago, # |
  Vote: I like it -6 Vote: I do not like it

This contest had a great difficulty curve. Kudos!

→ Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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).

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Firstly I was also calculating XOR(n) for every test case and got TLE :/

    → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    but one can clearly see that it will get tle if xor value is calculated every time.

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey, can you please tell me why do we get TLE if we precalculate the xor using for loop? Won't it be O(a)?

      → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        We won't get TLE if we precalculate the XOR values. I saw your submission of B, You are getting TLE because you are calculating XOR values for every test case. The time complexity of calculating XOR will be $$$O(n)$$$, and you are doing this for every test case, so your time complexity is actually $$$O(t*n)$$$ and that's why the TLE.

        → Reply
        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh okay I see now. But please tell me how can we precalculate the xor without getting the TLE?

          → Reply
          • »
            »
            »
            »
            »
            »
            8 months ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            You can make an array, where $i$th element will store the value, 0^1^2^....^i. You should do this before you start processing test cases.

            int arr[300005];
arr[0] = 0;
for(int i = 1; i <= 300004; i++)
{
     arr[i] = arr[i-1]^i;
}

// now you have precalculated the xor values.
// If you want to know what 0^1^2^...^i is, use arr[i].

while(t--) {

}
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Oh, yeah I get it now. Thank you so much :)

              → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              ll xorr; ll rem = (a — 1) % 4; if (rem == 0) xorr = a — 1; else if (rem == 1) xorr = 1; else if (rem == 2) xorr = a ; else if (rem == 3) xorr = 0;

              We can calculate xor upto a by this method also that taking modulo of a-1 with 4 and if remainder is o then xor will be a-1 else other condition. Time complexity =O(1)

              → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Precalulate zor values before inputting test cases then time complexity will be O(t)

        → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        To calculate the xor value of all the numbers from 1 to n in O(1) time :

        Find the remainder rem = n % 4

        If rem = 0, then xor = n

        If rem = 1, then xor = 1

        If rem = 2, then xor = n+1

        If rem = 3 ,then xor = 0

        This works because we get 0 as the XOR value just before a multiple of 4. This keeps repeating before every multiple of 4.

        → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn't note that need to precalculate too. But because of pragmas I get AC.

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Even with pragmas you wouldn't get AC in the worst case which will be around 1e10

      → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Mine too accepted with pragmas + bruetforce

      → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got tle :'( , then I had to use the properties of XOR. It was good tho

    → Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it

    There is a method that you can use, which can essentially answer each test case in O(1) without having to run any precomputation or use any pragma optimizations.

    It is based on the simple observation in the trend of the XOR value from 0 to a. It goes a little something like this.

    • If 'a' is a multiple of 4, the XOR of the sequence will be 'a' itself
    • If 'a' is a multiple of 2 but not a multiple of 4, the XOR of the sequence will be 'a' + 1
    • If 'a' is an odd number and the 'a' + 1 is both a multiple of 4 and 2, the XOR of the sequence will be 0
    • If 'a' is an odd number and the above constraints fail, the XOR of the sequence will be 1

    Which Roughly Translates to This:

    if(a % 2 == 0)
{
    if(a % 4 == 0) limit = a;
    else limit = a + 1;
}
else
{
    if((a + 1) % 2 == 0 and (a + 1) % 4 == 0) limit = 0;
    else limit = 1;
}

    Then you can simply perform the usual checks to get to the final answer.

    Here is my submission if you need any further clarifications. 128021227

    → Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    There is another way of computing xor in O(1) time complexity because xor of numbers from 1 to n follows a pattern and pattern repeats itself in the following manner

    lets say rem = n%4

    If rem = 0 xor = n

    If rem = 1, xor = 1

    If rem = 2, xor = n+1

    If rem = 3, xor = 0

    and with slight modification we can get the required results.

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      well even looping through n and using pragma optimization gives AC:):)

      → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

seen/good

→ Reply
»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    C is simple if u dont approach the dp way.Just divide the input string into even and odd parts.If u analyse the problem its actually simple addition on adjacent values.This observation is enough to solve the problem .

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But can you tell me why are we subtracting 2?

      → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yes as in question both numbers should be positive....hence if s=given sum,then we have to ignore two possibilities (s,0) and (0,s).

        → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah i tried dp (couldn't solve), its very easy to make error, or think of wrong transitions equation.

      → Reply
»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    basically 11th base was for hinting to the fact that you need to make n numbers such that they can achieve highest decimal place. example — to make 1000 with 2 numbers consider two cases, 900 100 990 10

    now you can see that in first case you are multiplying higher decimal places with even higher power of 11, 9*((11)^3) + 1*((11)^3) and in second case it is 9*((11)^3) + 9*((11)^2) + 1*((11)^2)

    so basically 1*((11)^3) > 9*((11)^2) + 1*((11)^2)

    → Reply
»
8 months ago, # |
  Vote: I like it +27 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah!thinking in that direction is hard! I tried one hour for it:)

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      I actually came up relatively quickly with a solution, but it was a bit un-elegant, in my opinion: using backtracking, I fixed the digits that would have a carry, then I calculated how many pairs of numbers satisfy the fixed digits' carries.

      → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes if someone approaches the DP way it gets complicated ,but if one thinks greedily its easy. Somehow i got the greedy idea on time:)

    → Reply
»
8 months ago, # |
  Vote: I like it +8 Vote: I do not like 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 !

→ Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Video tutorials are nice.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Very fast and amazing editorials with video solutions too.

→ Reply
»
8 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

→ Reply
»
8 months ago, # |
  Vote: I like it +7 Vote: I do not like it

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

→ Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    I don't know how to do addition, apparently. It will be fixed soon.

    → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The editorial came earlier than expected thank you.

→ Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

For solution C: "Note that in every other column, the addition Alice performs is correct."

This doesnt seem to be correct in the example in the question?

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

c was nice

→ Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There are a + 1 ways of getting the odd digits, there are b+1 ways of getting the even digits and they are independent. After that we have two solutions that dont work, (0,s) and (s,0), so we remove them with this "-2"

    → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if you're talking about problem C we can divide number n to 2 numbers a and b. by the position of their digits depending on odd or even. Then you have to make that number sum of 2 different numbers. we can 0+a,1+(a-1)+...a+1 in total a+1. it's the same for b. but the problem said positive integers which don't include 0. so we exclude the first number equals 0 and the second number equals zero which are 2. So the answer is (a+1) * (b+1) — 2. It might be different from some people's solution.

    → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    because the answer ask the pair of positive integer,answer can appear tow pairs (0,a+b)and(a+b,0),so you need to minus 2.

    → Reply
»
8 months ago, # |
  Vote: I like it +19 Vote: I do not like it

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).

→ Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Wouldn't the time complexity be O(nlog10(s)) because of computing the power of 10 for each iteration?

    → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    have you got any proofs why is this works? I will be very grateful if u explain it:D

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      It's actually pretty simple. If the largest power of 10 we can put is x, then we will add 11^log10(x) to the answer. If we choose power of 10, we can get at most y*(11^log10(x/y)) in the sum, y being power of 10 lower or equal to x. Now we just need to prove that 11^log10(x) >= y*(11^log10(x/y)).

      11^log10(x) >= y*(11^log10(x/y))

      11^log10(x)/11^log10(x/y) >= y

      11^(log10(x)-log10(x/y)) >= y

      11^(log10(x)-log10(x) + log10(y)) >= y

      11^log10(y) >= 10^log10(y)

      11 >= 10

      → Reply
»
8 months ago, # |
  Vote: I like it +90 Vote: I do not like it

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.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Lightning-fast editorial with video solution. Nice Job

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Editorial of problem C is really good.

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, this time editorial were pretty good and damn fast

    → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow, solution to C is incredible!!

→ Reply
»
8 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used that approach, check my submission here

    → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes,I did using backtracking all the possible cases.Link to my submission 128014364

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain your approach?

      → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        firstly i precalculated no.of ways to represent n(n<20) as a sum of two single digits. Now,start from the leftmost digit (let's say x) . It can be formed by two ways a) simply as a sum of two single digits which is ways[x] b) can be formed by a carry(which is 1) ,in this case x becomes x-1 and the digit next to the next to the current digit say y becomes 10+y; In each case the no.of ways the remaining digits can be formed can be calculated recursively.

        → Reply
»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
8 months ago, # |
  Vote: I like it +16 Vote: I do not like it

why Alice and Bob do weird things :(

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C was damn awesome after looking at editorial! Felt happy after looking at the editorial although I was unable to think it during contest

→ Reply
»
8 months ago, # |
  Vote: I like it -46 Vote: I do not like it

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';
        }

    }
}

}

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    in first else block declare a tmp variable of int type store the value of "b^all" and then compare with a i had the same problem lmao

    like else{ ll tmpvar = b^all; if(tmpvar != a){ cout << a+1 << endl; return; } cout << a+2 << endl; }

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why is it like this? , means what is the problem , can you explain little bit.

      → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        It something related to buffer Sometimes without storing and directly using some function can cause error like 

        int a = 7;
double b = a/2;
int c = ceil(b);

// Above code gives wrong output for 'c'

// But not below one
int a = 5;
double b = a;
b = b/2;
int c = ceil(b);
 
For above code output will be as expected for 'c' which is 3
        → Reply
        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          uhh, i dont think it is a buffer or whatever error,

          in the first code, when you do double b = a/2; a is considered int and a/2 is done in int division where we just cut everything after decimal.

          in second code b = b/2; is double division, so that gives correct output

          → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    just enclose ^(xor) in a bracket, ^ has a higher precedence that = operator, that may be the error

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thank you

      → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      yes i think that was the issue (b^all == a) is treated as (b^(all == a)). so in my code it should be ((b^all) == a)

      → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

problem C was irritating to be honest

→ Reply
»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I miss read the problem statement of B and got stuck and tried to find xor of every a-1 elements ;_;

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Really fun contest. Unfortunately I was too dumb to realize the miniscule errors I made in B and D :'(

But my rating increased by 69, so I guess that's nice.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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}

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    $$$100_{11}$$$ is never interpreted as $$$10 \cdot 11 + 0 \cdot 1$$$; the digit $$$10$$$ is typically represented by $$$A$$$.

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why it is always optimal to divide the sum into a power of 10.

      → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you please explain why for the test case "999999 3" the answer "1 1 999997" is better then "800000 100000 99999"? It seems to me that they have the same sum in 11-based system

      → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        They have the same sum, but your submission gets WA on test case 4: $$$10_{11}+90_{11}=A0_{11}$$$, but $$$1_{11} + 99_{11}= 9A_{11}$$$.

        → Reply
        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh, I see. Thank you!

          → Reply
        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          For Problem D, regarding the idea of splitting the least power of 10: "we should split the smallest power 10". I can't seem to make a correct algorithm for input, say: 100 3.

          I would end up with the 3 following terms: 90, 9, 1.

          Starting with [100], splitting into [90, 10] and then, take the smallest power of 10, 10, ending up with [90, 9, 1].

          Have I misinterpreted your words?

          → Reply
          • »
            »
            »
            »
            »
            »
            8 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            You should only split powers of $$$10$$$ when we have no other ways to split any of the numbers: $$$90_{11}$$$ can be split as $$$10_{11}$$$ and $$$80_{11}$$$ still, and so a better answer is $$$[80, 10, 10]$$$.

            When we add them:

            • $$$80_{11} + 10_{11} + 10_{11} = A0_{11}$$$.

            • $$$90_{11} + 9_{11} + 1_{11} = 9A_{11}$$$.

            As you can see, we should continue to split all numbers into powers of ten, and as soon as all numbers are powers of ten, then we can take the smallest one.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I got you! Thank you for the time you took to reply.

              → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        they are same

        → Reply
»
8 months ago, # |
  Vote: I like it +78 Vote: I do not like it

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)??

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    127946227

    ^ here is my submission. Hope it helps!

    → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    a great exercise would be to make a dp based soln. for finding number of ways when we normally add 2 numbers. I know it is n + 1, but if you can make that dp then you can do that alternatively in this problem.

    → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We were aware of this, but we didn't want to force people to google the solution. The editorial mentions this as well.

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      It will be better if you add it in editorial. I didn't know about it before seeing this comment.

      → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1567/submission/127954668

How does this solution for D split the 10s into 9s and 1s if there isnt enough digits?

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does this get WA on test 3 in problem B https://codeforces.com/contest/1567/submission/127978046

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you so much

→ Reply
»
8 months ago, # |
  Vote: I like it +6 Vote: I do not like it

flame, please lmk how to be as orzosity as you

thanq

→ Reply
»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

The video is really great

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

    Is this your assumption or can you prove that?

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can't say I proved that but this is my rough idea:

      Cells that share common empty cells form a "connected component" in which the way of filling two diagonally adjacent cells determines how to fill the whole component.

      1. If some marked cell has only two adjacent empty cells, we should make the two empty cells different => opposite empty cells should be the same.
      2. Otherwise all marked cells have four adjacent empty cells => opposite empty cells can be the same or different.
      → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        After writing that I thought 2-SAT are just redundant. You can simply fill two diagonally adjacent empty cells and do a bfs/dfs to spread the coloring.

        → Reply
    • »
      »
      »
      8 months ago, # ^ |
      ← Rev. 2   Vote: I like it +33 Vote: I do not like it

      I also solved the problem with this method, and my proof went something like this:

      Build a graph whose edges are pairs of unmarked cells that we want to force to be different. For marked cells with 2 adjacent unmarked cells, draw an edge between them; for marked cells with 4 adjacent unmarked cells, draw edges between (top, left) and (bottom, right).

      Any bipartite colouring of this graph yields a valid solution. To prove such a colouring exists, it suffices to show that there are no odd simple cycles in the graph.

      Let's assume, for the sake of contradiction, that such a graph with an odd cycle exists.

      There are two types of edges in this graph: "grid-aligned" and "diagonal". Notice that "grid-aligned" edges do not change the parity of coordinates, but "diagonal" edges change the parity of both coordinates. Therefore there must be an even number of "diagonal" edges, and so, an odd number of "grid-aligned" edges.

      If the edges are straight lines, the cycle is a boundary of a section of the grid. Notice that the only marked cells on the boundary are on the "grid-aligned" edges, so there are an odd number of them.

      Count the number of ordered pairs of marked cells (P, Q) where P and Q are adjacent and both on or inside the boundary. By double-counting, this number must be even.

      However, for a marked cell inside the boundary, we know that the number of adjacent marked cells on or inside the boundary must be even, and for a marked cell on the boundary, this number must be odd. As there is an odd number of marked cells on the boundary, the number of ordered pairs is odd, which is a contradiction.

      → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
        ← Rev. 2   Vote: I like it -26 Vote: I do not like it

        there is a simpler proof to the 2-coloring if you instead connect (top,right) and (bottom,left) for the diagonal edges .

        the difference between the x and y coordinate remains invariant under the diagonal edges since it ±1 to both coordinates , and grid aligned edges changes the difference by ±2 since you need a net change of 0 to the difference thus you need an even number of grid aligned edges (parity argument still holds for even diagonal edges)

        UPD : this is wrong I missed that for connecting two forced unmarked cells you can get diagonally left edges

        → Reply
»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
8 months ago, # |
← Rev. 17   Vote: I like it 0 Vote: I do not like it

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.

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$$$.

→ Reply
»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Recursive Solution for problem C.

Code
→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the DP solution for problem C in a detailed manner? Thanks!

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In B, I never knew such formula existed for xor and I got TLE for using the naive approach. But then in the end, I formulated my own formula for xor and achieved O(1) time. I am so noob in coding, but to know that I constructed a formula that I never knew existed gives me some motivation. Its my dream to at least solve 3 problems during one contest

→ Reply
»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 months ago, # |
  Vote: I like it +21 Vote: I do not like it

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:

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How 3+4+100+4=110 in base 11 in the third test case explanation? when 70+27=97 in base 11 in the first test case explanation? Am i missing any knowledge? Please share it! Thanks!

→ Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I got it now. Think like how we do normal base 10 addition

    9 + 1 = 10 where 1 is carry and 0 is the sum at that position. Similarly, In base 11, 4+4 = 8 + 3 = 9 + 2 = 9 + 1 + 1 = A + 1 = 10 where 1 is carry and 0 is sum at that position. Note: 9 + 1= A because in base 11, digits are {0, 1, 2,...9, A}

    See this https://math.tools/table/addition/base/11 Similarly think for binary addition (Base 2 addition). You will definitely understand it.

    → Reply
»
8 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Special Thanks to flamestorm for problem-C !!!

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I really loved problem E. I have written an implementation of it by using two extra pieces of information at each node l and r, where l and r are the range that this node covers. I did this because I felt that the implementation of the query function in the editorial was hard for me to understand and hence I wrote this code which only changes the merge function and the query function is not changed: 128038196

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem B, the facts that we use are for precalculating XOR from 1 to n are mismatching with the facts that I have.

https://www.geeksforgeeks.org/calculate-xor-1-n/

Can somebody confirm if it's wrong in the above link?

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I had messed up with a bracket in my code, giving me an erroneous result. rather than the above could you check how the 2 statements below are calculated differently?

    (d^b)!=a

    d^b!=a

    → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

E is the hardest to me.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Because the pairs (0, n) and (n, 0) have also been included in (a+1)*(b+1). We need to remove them as we want both numbers to be greater than 0. Hope you got it. I also did not get it but I tried with n = 22 and I understood. Hope it helps you too :)

    → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I guess sol(obs) for C is wrong somewhere... because 15 * 90 = 1350 instead of 1950.

Please correct me if I'm taking the solution in the wrong way!

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain query part of problem E

→ Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C Submission with complete Newbie Implementation https://codeforces.com/contest/1567/submission/128091033

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey, Can u please help in one sample test case of problem c the last one (10000) how its 99 ,I am getting only 81 cases with 2 case only Refer this image if u need According to me The blue ones underlined will have no contribution, and C means it will generate carry and NC means it will not generate carry Any help will be appreciated

    → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice round bro . I think E is easier than C

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

who can explain the C by using dp,the translate as if some trouble

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain D in simple words? I have looked at both the editorial and the video but don't seem to grasp the idea.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why the video solution can not connect

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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]];
            }
        }
    }
→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E:

My Submission

Giving wrong answer on test case 3 128573992

what's wrong in my code?

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, you are right; I updated the editorial some time ago, but for some reason, it didn't seem to update here. I am not entirely sure what's going on ¯\_(ツ)_/¯

    → Reply