thank goD!

As a participant, we already knew that

no u

You claim to be Java yet you solve using C++. Curious

Why does the last part make me a little .... scared .....

懂得都懂（

Remark: for those (non-Chinese and Chinese alike) who don't understand what Sparky_Master_WCH1226 is referring to, look at the date of the contest, June 4th. It's the 34th anniversary of the Tiananmen Square massacre.

waiting for system test now:))))))

Wrong contest :)

I believe in you!

It is my "Return to CM" round.

almost

was it !!!!!!

Standard Codeforces rules are applied. You can read them here (relevant section: judging).

TL;DR: An incorrect submission that passes test 1, i.e. the (first) example test, but fails on another pretest, deducts 50 points from the score you would get by solving the problem. This means that each wrong submission decreases your total score by 50 points, but these points are only removed if you solve the problem with the wrong submissions.

Perhaps, again, there are a lot of people who want to participate in the contest

There's randomly some 503 from codeforces.

I need to sleep!

is that your known fear?

If u click the bottom of go to the contest page, it will tell u "the contest didnt start" xd

Once you do click on enter, you get a notification saying "Contest has not started", so basically wait 5 minutes more.

You sent this comment with your other account 5 mins ago!

Welcome to codeforces

I was also stuck on problem C for a very long time, but I wouldn't call it unfair. It's just, unpleasant.

can i know what is the expected time complexity of D...i tried with O(n^2 * q) but it gave tle in pretest-9

I don't know how to solve E, but maybe this problem from AtCoder help you — it is the same problem, but $$$M \le 2 \cdot 10^6$$$.

video editorial for E: count supersequences

@diskoteka check out the time stamps in the description as this is a lengthy video

Yes. We just need to store all occurrences of two consecutive equal characters and update these every query. This can be easily done with std::set. 208498566

Just simple segtree with "find first non-zero element"

Look at string. It is corrent, if and only if it looks like this:

$$$()()()()()()()((-bla-bla-bla-))()()()()()()()$$$.

We will work with pairs of elements. We can track those $$$()$$$ as $$$0$$$ in segtree and all others $$$(($$$, $$$))$$$ and $$$)($$$ as $$$1$$$. Now, to answer query, ask segtree for position of first $$$1$$$, and check, that this is $$$(($$$. Do following with reverse direction.

same

I just got the idea, but you have to notice that the actual array isn't important at all. The expression you got is independent of it(you can also write a simple recurrence to see this independence). So you can assume that the array is made up of all 1s. So, now you have to count the number of m sized arrays which have <=n-1 number of 1s and subtract from the total.

Same. In the first n gaps created by ai's, you can put any value except the value of ai following the gap

Doing some substitution of variables to transform your expression into this gives the same summation as in the editorial.

ikr. C blows

btw how 2 solve c :(

Yes, The idea of the problem is too easy, but bad implementation with binary search.

My approach--> We can fill the matrix starting from 1,2,3... row wise. For ex-> for n=5 and m=5 it will be - 1 2 3 4 5 - 6 7 8 9 10 - 11 12 13 14 15 - 16 17 18 19 20 - 21 22 23 24 25

Now we see that difference between any two adjacent row elements is always 1 and difference between any two adjacent column elements is equal to m(i.e. number of columns). So we can just swap the rows or simply first we can write the even rows and then the odd rows.. doing any operation like this will make the difference between any two adjacent column elements, a multiple of m which will be non-prime.

there is an edge case for n=4 and m=prime in which we can just do the same thing with columns.

This is my approach

If m is not prime just go from left to right, top to bottom and increase one on each step

Horizontal difference will be 1 Vertical difference will always be m

If n is not prime just do the same but increase one from top to bottom (rotate the matrix)

If both of them is prime it doesn't matter if we work on rows or columns, so we will choose working on rows

The first row will be 1 to m Starting with the second row we will apply this approach:

Find the largest element in the last row, let it be x Insert x+1 exactly below it (let it be mn) Add x+m (max number in this row, let it be mx) to the left of mn

It is clear that the difference between mn and mx is always even because mn = x+1 mx = x+m mx-mn = m-1 (m is prime >= 4) Go from this mx to the left of the row decreasing one in each step Then go from mn to the right of the array increasing one in each step

Now the row is finished with all numbers between mn and mx (inclusive)

Now we need to prove that the vertical differences will always be either 1 or an even number

If we ignore the first row Every number will have different parity than the two numbers on their sides, except the smallest one which will have the same parity as the number on its left side

mn have difference of 1 with its top element which was x

Each element on the left side of the mx of the last row have difference parity than its neighbours So when we set mx to the same parity of its top element and increase 1 on each step going to left, each element on its left side will have the same parity with its top element

The right side of mn will always have the same parity with its top element because the mn have difference parity than its top element, its right side increase by one and its parent go one step with the same parity and then increase by one

Note: we can get the next mn position if we go from right to left in a circular way (decreasing one on each step and when we are at position 0, we go to m again)

How do such problems like C even get accepted?

I think B is easier than A.

You just need to take n Between 1 and 2.

idea: 1. if 1 and 2 are adjacent to each other, find relative position of n and swap thee one that lies in the middle acc to their position (1,2 and n)

1. if they're not adjacent, chhose any index b/w them and swap with index of n

Just think about:

n+1 n+2 ...

3n+1 3n+2 ...

...

1 2 3 4 ...

2n+1 2n+2 ...

...

So C<<A for me...

my thought process was

First, if m is even, then we can just print the numbers in order. numbers in the same row will have difference 1, and numbers in adjacent rows will have an even difference (and nonprime since n,m >= 4)

My second thought was if m was odd, then we could reorder the rows such that it goes (row 1, row 3, row 5. . . row 2, row 4, row 6 . . . ), but this didn't always work when n was even. For example with n = 4, m = 7 row 2 would follow row 3 and have a difference of 7 between them

But I realized that when n is even, I could instead just mirror my approach for when m was even, going along the rows instead of the columns. Combining the 3 ideas, a complete solution is reached

Congrats!

Generate multiple for n%2==0 like 2 4 1 3 Else for n odd 1 3 5 2 4

Linearly assign numbers from 1 to n * m. If m is non — prime, that would be your answer. If m is prime, reorder rows such that the difference is multiple of m.

I solved just after the round was over... I hope this is right... my approach:

let's consider three cases.. 1) when n and m both are non-prime then the solution is simple, just print

(1 2 3 4 5..m),

m+1 m+2....

because the neighbors will be {1,m,1,m}

2) when n is prime and m is prime then let for 5 7,

v[0]=1 2 3 4 5 6 7,

v[2]= 15 16 17 18 19 20,

v[4]....,

v[1]....,

v[3]....,

i.e. first even ones,then odd ones or vice-versa because the neighbors will be {1,k*m,1,k*m}

3) when n is non prime but m is prime try for 4 5 instead of horizontally like case 1, try it vertically

(1 5 9 13 17),

(2 6 10 14 18),

(3 7 11 15 19),

(4 8 12 16 20),

because the neighbors will be {n,1,n,1}

Important observation for D:

You can use the first (( inf times, and the last )) inf times +- something to adjust, so anything between them doesn't matter

Problem becomes symmetric as well

Different method to solve would be to optimize this (messier than Yocycraft's solution, but easier to come up with i guess): 208507662

is there a simple way to do D?

What i did is split into three separate check:

• . Prefix check, single open must follow single close until encountering a non single open.
• . Parity check (open and close must have the same parity)
• . Reverse the string and do the same for close, except pretend close is open. the answer to query is only yes if all three above is true.

I read that the idea was to put n between 1 and 2. I was trying to get the 2 away from the 1 as much as possible, but I dont know why that Idea didnt work, at least for me.

Your idea is correct. We need the max element ($$$= n$$$) to be between $$$1$$$ and $$$2$$$.

We can do the following:

1. If the array looks like $$$[\dots, 1, \dots, 2, \dots, n, \dots]$$$ or $$$[\dots, 2, \dots, 1, \dots, n, \dots]$$$ (i.e. $$$n$$$ is after $$$1$$$ and $$$2$$$), we can swap $$$n$$$ and the last one of $$$1$$$ or $$$2$$$.
2. If the array looks like $$$[\dots, n, \dots, 1, \dots, 2, \dots]$$$ or $$$[\dots, n, \dots, 2, \dots, 1, \dots]$$$ (i.e. $$$n$$$ is before $$$1$$$ and $$$2$$$), we can swap $$$n$$$ and the first one of $$$1$$$ or $$$2$$$.
3. If the array looks like $$$[\dots, 1, \dots, n, \dots, 2, \dots]$$$ or $$$[\dots, 2, \dots, n, \dots, 1, \dots]$$$ (i.e. $$$n$$$ is between $$$1$$$ and $$$2$$$), we can do nothing = swap $$$1$$$ and $$$1$$$, for example.

CLIST predicts 2200 (approx.)

Congrats!