flamestorm's blog

By flamestorm, 22 months ago, In English

Thanks for participating!

1722A - Spell Check

Idea: mesanu, MikeMirzayanov

Tutorial
Solution

1722B - Colourblindness

Idea: flamestorm

Tutorial
Solution

1722C - Word Game

Idea: flamestorm

Tutorial
Solution

1722D - Line

Idea: flamestorm

Tutorial
Solution

1722E - Counting Rectangles

Idea: mesanu

Tutorial
Solution

1722F - L-shapes

Idea: MikeMirzayanov

Tutorial
Solution

1722G - Even-Odd XOR

Idea: mesanu

Tutorial
Alternate Tutorial Sketch
Solution
  • Vote: I like it
  • +71
  • Vote: I do not like it

| Write comment?
»
22 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I didn't even think that Timur is lexicographically in order. What a brilliant solution!

Edit: It isn't, but it's still an interesting solution to think of.

»
22 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Problem D can also be solved in O(n) using two pointers

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

    exactly

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

    Can you give your solution here it would help

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

      here if you need explanation feel free to ask

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

        Hello, I saw your solution but I didn't understand this line . What is it for > for (k;k<=n;k++) ans[k]=s;

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

          let's suppose that it was already optimal like RRLL so in the line you mentioned it just sets the remaining indexes (which could not be covered in while loop cuz of being optimal) they will just get the previous value as we will not be changing them...

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

          Let's say the number of characters I needes to change was 8 and n is 10. I need go give an answer for all k such that 1<=k<=n so I just output for the remaining k

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

            I got it. Thank you so much.

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

    I solved it in O(n) aswell, but using prefix array

    170271299

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

      Can u pls explain,how did u do it using Prefix arrays

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

        Take a look at the comments in the submission, if that doesn't help let me know once again.

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

          Still i didn't get .M new to prefix array

          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            You can have a look at others two-pointer solution. It's almost similar.

            Explanation
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      it seems that we have the same idea

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

    What is two pointer approach... Can you share some resources from where I should learn... It would be a great help

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

      Check Codeforces edu section. You can also read about it on USACO Guide

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

    i do it with queue :)

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

      It can be done too, because there indices that must be changed before others right?

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is problem A $$$O(n)$$$? You check if $$$n = 5$$$ in $$$O(1)$$$; If it is, then sort the string which in this case will always have length $$$n = 5$$$ so sorting and checking is done in $$$O(1)$$$ (since the length is upper bounded). So overall $$$O(1)$$$, or am I missing something?

  • »
    »
    22 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I think that's true. Change it, flamestorm.

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

      You check if "T" is in the string, that can be done in $$$O(1)$$$ (since it only has 5 elements). Then you check if "i", also $$$O(1)$$$ And so forth. In total $$$5 \cdot O(1) = O(1)$$$

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

        You have to read the string size of n, so it is O(n)

»
22 months ago, # |
Rev. 2   Vote: I like it +41 Vote: I do not like it

problem G:

topic 1

Regardless of your correct answer, when you choose some elements and take their XOR, then the value will be equal to the XOR of the remaining elements. Why?
Sample: $$$(4,2,1,5,0,6,7,3)$$$ is one of answer for $$$n=8$$$, and $$$4 \oplus 0 \oplus 3 = 2 \oplus 1 \oplus 5 \oplus 6 \oplus 7 = 7$$$

Answer
topic 2

There exists a randomized solution.

Explanation
topic 3

For $$$3 \le n \le 6$$$, the answers are provided in the sample, so let's use them as a prefix.

  • $$$n \equiv 0 \mod 4$$$ then prefix = $$$(2,1,3,0)$$$
  • $$$n \equiv 1 \mod 4$$$ then prefix = $$$(2,0,4,5,3)$$$
  • $$$n \equiv 2 \mod 4$$$ then prefix = $$$(4,1,2,12,3,8)$$$
  • $$$n \equiv 3 \mod 4$$$ then prefix = $$$(2,1,3)$$$

After that, add $$$(100,101,102,103,\dots)$$$ until the length of the sequence becomes $$$n$$$. (note that the length of added sequence is a multiple of $$$4$$$ ) Then, you can get a correct answer.
Submission: 170321109

Why?
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    master piece. i tried to construct a solution similar to topic 3, but unfortunately fell into tons of case work.

    however, instead we can take advantage of samples, XD

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

    Thanks alot. Can you share the proof of topic 3 ?

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      proof with an example
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    A1⊕A3⊕⋯=A2⊕A4⊕… ↔A1⊕A2⊕A3⊕A4⊕⋯=0

    can you swap randomly and still have the equality?

    if yes, can you do the same in

    X ^ Y < A ^ B -> x ^ B < A ^ Y ?

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The latex for $$$2^{30}$$$ is bugged in the tutorial of problem G.

Aside from that, problem G is a really cool problem!

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For anyone who is finding the solution of problem F, hard to understand/code, can take a look at my solution using DFS 170297341

»
22 months ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

Weak pretests for A , so many solutions got hacked.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to write the code for Problem G with the alternate tutorial, I am unable to understand the approach

»
22 months ago, # |
Rev. 2   Vote: I like it -9 Vote: I do not like it

Simple implementation for problem G

void solve()
{
    int n;
    cin >> n;

    int xorr = 0;
    vector<int> ans;
    for (int i = 1; i <= n - 2; ++i)
    {
        ans.push_back(i);
        xorr ^= i;
    }
    if (xorr != 0)
    {
        ans.push_back(1 << 30);
        ans.push_back((xorr) ^ (1 << 30));
    }
    else
    {
        /*

        The maximum xor of all the elements from 1 to n-2 or n-3 will be less than 2**21.
        (So, you can choose any power of 2 from [21, 30) and replace n-2 with it)
        If we have XOR([1...n-2]) as zero, we can remove (n-2) and can push (1<<21)
        And now the XOR([1....n-3, (1<<21)]) will be some number having the 21st as set

        Now, we just need two more nos, that can be (1<<30) and XOR([1...n-3, (1<<21)])) ^ (1<<30)

        */
        xorr ^= (n - 2);
        ans.pop_back();
        ans.push_back(1 << 21);
        xorr ^= (1 << 21);
        ans.push_back(1 << 30);
        ans.push_back(xorr ^ (1 << 30));
    }

    for (auto &i : ans)
    {
        cout << i << " ";
    }

    cout << nline;
}
»
22 months ago, # |
Rev. 3   Vote: I like it -6 Vote: I do not like it

Problem F can be done using

Surprise !

:D

»
22 months ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

I had school so I wasn't able to do the contest, however I've solved them all and I present my solutions. They may or may not be worse quality than the official editorial.

A
B
C
D
E
F
G
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please tell me where my submission 170342106 for problem E is failing?

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

      I think your code is quite overcomplicated

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

    tgp07 Excellent editorial, better than official one! Could you please tell me if there is a way to solve E under the same time constraints for tighter dimensions of the rectangle say 1e5 or 1e9 or even higher?

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

      That would be a lot tougher. I'm not immediately sure of any way to solve that.

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

    your G one is really good Thanks for sharing.

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

    I think an improvement for F would be to extend adjacency to include diagonals, i.e., each cell has up to 8 neighbors for the purposes of DFS. Then all we need to do is make sure each connected component has size 3 and forms an L shape.

    This way, there is no need to check if different blocks touch by edge or corner, since the DFS would've merged such cases into larger components.

    (also, checking whether three cells form an L-shape can be done by simply checking if, for each of the three pairs of cells, the difference between the x- and y-coordinates is at most 1)

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

      This seems smart, have you submitted a solution with this approach?

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

        I had a partially written code, but the contest ended and I didn't bother finishing it up. But your comment encouraged me to complete and submit it, so here it is: 170513958!

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My first contest solving more than 1 problem :) I was excited to realize I could use a max heap to solve problem D.

»
22 months ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

Hey!, can someone help me up solving question F,

My logic for the solution was that for each * there can be only and only 2 '*' neighbors in all 8 directions(if a cell exists there) no more, no less than that.

But it fails on test no. 4, 69th ticket. can someone help me find a test case where this fails. WA link — https://mirror.codeforces.com/contest/1722/submission/170290140

Any help would be very appreciated.

  • »
    »
    22 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    1
    3 3
    .*.
    *.*
    .*.

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

      Thanks a lot, how do you come up with such cases, like how do you think of cases where our code might fail, how to develop that? any tips on that would be very helpful.

      • »
        »
        »
        »
        22 months ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        If it's after the contest, you can simply view the test cases in your submission. Often the input would be truncated, but you can often still find a way to reveal it. Modify your code by adding conditions to specifically check for the problematic test case, and then use it to print the result.

        In this case, for example, you can see that in Test #4, the first case has n = m = 3, unlike the earlier Test Suites. So you can write your program such that if the first test case begins with n = m = 3 (you can use scanf for this, if desynced with cin), then you call a different function that reads the first 68 cases while printing absolutely nothing (not even the answers), and then reads the 69th case to print the complete test case details. When submitting, this should pass Tests #1-3, and then print the problematic test case in #4 for you to view.

        This can be cumbersome sometimes, but at least it's a generally definite approach to finding the test case that breaks your program. I haven't yet encountered a situation where I was unable to expose the problematic test case this way.

»
22 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

fst

»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Alternate solution for Problem G:
Observe that $$$ a \oplus b$$$ $$$=$$$ $$$\sim a \oplus \sim b. $$$ Now you can construct a sequence $$$a0$$$, $$$\sim a_0,$$$ $$$a_1,$$$ $$$\sim a_1,$$$ $$$a_2,$$$ $$$\sim a_2, \dots$$$ (upto n terms) where $$$n \equiv 0$$$ ($$$mod$$$ $$$4$$$).
For $$$n = 4k+1$$$ or $$$4k+2$$$ or $$$4k+3$$$, just take some prefixes of length $$$1$$$ (0), $$$6$$$ (4,1,2,12,3,8), and $$$3$$$ (2, 1,3) respectively from the given testcases itself and the remaining sequence will be of length $$$4k'$$$.

Note that $$$a_0$$$, $$$a_1$$$, $$$\dots$$$ can be taken to be $$$13,$$$ $$$14,$$$ $$$15,$$$ ... as none of the prefixes contain elements $$$>13$$$.
Also, $$$\sim a$$$ represents 1's compliment of $$$a$$$ inverting all 32 bits of $$$+a$$$, although (even the first 20 bits would work considering the constraints on $$$a_i$$$)

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the use of greater() in the sort function of the D problem?

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

    Its a comparator which defines how you want it be sorted. You can read more about it here

»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

In the problem E, trivial $$$O(n q)$$$ solution passes due $$$\mathrm{TL} = 6 \mathrm{s}$$$: 170297542

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

    I wonder how your fastIO works...My BF solution 170407110 could pass only when adding your fastIO code. (And on test 4, it is 15 times faster than simply using untie cin/cout). It seems impossible because IO shouldn't be the bottleneck of this problem. I'm really confused about this.

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

      We need optimize any constant in time complexity of solution. And it is fastest I/O (on Windows) that I have been seen.

      In it, I completely abandoned small buffers (usually ~2KiB) that lead to a lot of file operations, and also decided to completely abandon non-system I/O functions due to overhead. Large buffers allow your program to use two file operations during work.

      And when -O3 is specified, gcc inlines my function ReadInt32, but no printf and std::cin.

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

        I discuss this with some friends and get a weird conclusion. You can see the difference between 170435459 and 170435486. Seems that when we replace the last cin with a function (although we still use cin to read), the compiler will use SIMD to optimize the if statement. Replace function with inline function even macro gets the same result. But just using cin or scanf won't trigger optimization. I have no idea why this happens :(

»
22 months ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

I solved problem G quite differently from the editorial method utilising the property that XOR of consecutive numbers x and y is always 0 when x is an even number (if you didn't know this, it's easy to see why, by taking a few consecutive numbers and looking at their binary representation).

Let set a and b represent respectively the set of numbers at even positions and the set of numbers at odd positions. Then we break solution into 4 cases depending on the remainder of n on dividing by 4.

Case 1.) n%4 = 0
Case 2.) n%4 = 1
Case 3.) n%4 = 3
Case 4.) n%4 = 2

I think some of the cases can probably be combined for a simpler solution. Please let me know in the comments.

Not so elegant and repetitive implementation : 170369765

»
22 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Another way to solve F: L-shapes:

ref: https://mirror.codeforces.com/contest/1722/submission/170380611
Note that, a 2x2 grid will contain L shape if and only if there are exactly 3 '*' in it.

1)Firstly for all 2x2 subgrid that contain L-shape, check whether its surrounding has any '*' in it, if so, then the ans is NO. [except for the corner along void position(exactly one such position) of 2x2 grid ,
eg: '#' in below picture [and ^ is void position] ]

...#
.*^.
.**.
....

2)Now the only problem is, there can also be any other shapes than L-shapes. To find that,
In logic1, just whenever current 2x2 subgrid contain L,(ie:exactly 3 '*' in it) , mark those positions as #.
So that all L shapes will be marked, and if there exist any other shape than L shape then it will remain unmarked(ie:remains *).

So, atlast traverse the whole grid to find any such unmarked position,
if so, the ans is NO,
Otherwise YES.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My Solution for F

did the same thing as mentioned in the editorial but is easier to understand.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I got wa on F test 3 170393551 can somebody say the problem

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there anywhere I can view solutions in java?

»
22 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Here is a bit shorter code for F: 170427907

Spoiler
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any other way to solve #C without using a map?

»
22 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Problem E can also be solved with offline queries and binary search on segment tree, which gives O(t*n*logn) that satisfied arbitrary large height and width of the rectangles.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution for G:

xor of 2x (even no.) and 2x+1 is always 1.

Case 1: n%4 == 0: A simple solution would be 20,20+2n,21,21+2n,22,22+2n,....

Case 2: n%4 == 1: Just add a 0 at the end of Case 1

Case 3: n%4 == 2: Just add 4 1 2 12 3 8 this sequence at the end of Case 1 (Provided in sample input for n=6)

Case 4: n%4 == 3: Just add 2 1 3 this sequence at the end of Case 1 (Provided in sample input for n=3)

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem F can be solved easily using 8-directional floodfill

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

As a fun fact, you can solve G just by printing random numbers and equalizing Xor with the last two elements.

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

For problem G: After noticing we need n numbers such that their xor is zero, we can use https://oeis.org/A003815 as follows:

if n = 4k+1: print(0, 2,3,...,n); # that is print zero instead of 1 :)
if n = 4k+3: print(1,2,3,...,n); # already 0
if n = 4k+4: print(0,1,...,n-1); # that is converted to the 4k+3 case
if n = 4k+2: print(*[0,3,5],*[7,8,...,n+3]) # consider xor of (0,1,...,n+3). It will be 1. Now remove 1,2,4,6. We get n numbers with zero-xor.
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution to G.

basically xor of x,x+1,x+2,x+3 is 0 and also xor of their alternate indexes. so every n could be writtern in form of 4x,4x+1,4x+2,4x+3. we will be taking avantage of this as an extension

Code ``` vector<vector> arr(4); arr[0]={0,1,2,3}; arr[1]={2,0,4,5,3}; arr[2]={4,1,2,12,3,8}; arr[3]={2,1,3};

ll n,x=16;
cin>>n;

ll val=n%4,extra=n-arr[val].size();

for(ll i=0;i<(ll)arr[val].size();i++){
    cout<<arr[val][i]<<" ";
}
while(extra--){
    cout<<x<<' ';
    x++;
}
cout<<nl;

```

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it
»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In fact in G , we can choose any number from [18,30] as the lastbutone'th number as because the XOR of the (n-2) elements would atmost be (n+1) {by the consecutive XOR property of elements} and as elements range from 2*10^5 which is approximately < 2^18, but n+1 is less than 2^18 so we can use anything from 18 & beyond. Hope it helps