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.

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

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?

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

topic 2

There exists a randomized solution.

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

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

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

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

Weak pretests for A , so many solutions got hacked.

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

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

Problem F can be done using

:D

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.

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

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.

fst

Is it only Me or anybody else also noticed that F was comparatively easy E for those who till now havent encountered problem based on 2-D PREFIX Sum . I am feeling very frustrated as I spent more than one hour on E and also during the contest F have least successful submission so I just dont focused on F

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

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

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

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.

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

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.

My Solution for F

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

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

Is there anywhere I can view solutions in java?

Here is a bit shorter code for F: 170427907

.*.
*.*
.*.

.**.
*..*
*..*
.**.

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

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.

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)

Problem F can be solved easily using 8-directional floodfill

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

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.

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;

```

E :solution with 1d prefix sum https://mirror.codeforces.com/contest/1722/submission/265651414

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

E can be solved in $$$O((n+q)\log(max(h_i))\log(max(w_i)))$$$ with the same amount of memory (if you choose the container as nested hash tables) or $$$O(max(h_i)max(w_i))$$$ (if you choose arrays which are faster) if you used 2D BITs. The solution is 2x faster than the normal solution: https://mirror.codeforces.com/contest/1722/submission/267849082, https://mirror.codeforces.com/contest/1722/submission/267849782.