my mistake : (

very observational tasks....found c easier than a and b

Good contest

Enjoyed problem C. Good Contest

Forgot the case s[1] = ')' or s[n] = '(' ToT

Good contest and fast tutorial! But I can only solve one problem.

Video Editorial for B

Video Editorial for C

Credits to Dominater069 orz for C idea

fast editorial!

I've had this argument with quite a number of people, but can you explain how you can approach C without brute forcing random patterns?

A good idea about solving problem D! I didn't expect the implementation of D to be so simple.

I found it cool that problems were not that standard, unlike usual div2s.

Short solution of A — E. Impressive

I enjoyed solving C most, it was a nice problem !

Hit or miss forces

Almost solved E once again :(. Didn't notice that you don't need the values of array $$$a$$$ to count $$$dp$$$. Enjoyed the round, although I can see there are not so many people who have the same feelings

Anyone please help me out how to solve B and C questions in Div2. I got stuck many times in it.

I had practice many questions but still am facing this issue.

https://www.youtube.com/watch?v=GusESkLoLcA&ab_channel=tyroWhiz

Solutions from A-D and my insights on E

Is D well known trick? Why so many ACs...

Was I the only one to submit a brute-force recursion-with-backtracking solution for problem C?

The worst-case time complexity is high, but it runs fast in practice because the problem is not very constrained.

Perfect editorial

Is it just me who enjoys Ds that are more algorithm and implementation heavy and not Ds that are like "because math something something cout << i-am-clown is always the correct answer"

Can someone please explain why this brute-force idea for A is incorrect? 0) if there is a negative integer that is obviously the answer.

1) insert all the elements in the array in a set. This set keeps track of all the elements which is impossible to get through the absolute difference of any 2 elements in the array.

2) Use nested for loops(n^2) and iterate through the array(not set) and check the absolute difference of every 2 elements in the array. If this absolute difference is present in the set, remove this from the set.

3) the element still remaining in the set, this must be one of the possible answers because of the fact that this element was impossible to get through any 2 elements' absolute difference.

code link: https://mirror.codeforces.com/contest/1838/submission/208442311

Here's my thought process for ABC, hopefully it helps people understand how to come up with the solution. Sometimes it seems unintuitive but it is possible.

A: We notice that negative numbers are abit sus from the sample testcases, how come theres only 1 or 2 negative numbers? Then realise because we are taking absolute difference the rest of the numbers are positive, so negative numbers can only appear at the very start => meaning, if we see a negative number we just print it. Else, there is no negative numbers, what to do? If theres no negative numbers, because we are taking absolute difference we can just take the maximum value in the array, as we can only get smaller values in the future by taking absolute differences. Therefore: if min < 0 print min, else print max

B: Ok we want to minimise the number of permutation subarrays => What is the minimum value? Can we always get 1 and [1...n] as the only permutations? Ok idk if its possible, let me check the testcase: It seems that this is always possible after checking all the testcase. Therefore, we want only 1 and 1...n as the permutations, how to do so? See that if we place 1 and n beside each other, it may be good because every subsequent subarray afterwards that contains [1,n] will never be a smaller permutation. However we see from the testcase that ...2 1 n is still bad, because we only need 1 and 1...n as the permutations. 2 is pesky, so let us place it away from 1 so that we can never get 1,2 as a subarray. Ok how to do so? realise that 1, n, 2 and 2, n, 1 will be correct, so let us just make this pattern and we can ignore the rest of the subarrays. We can ignore the rest because we will always have [1,n] together without any other permutations formed

C: Constructive, seems that many people are able to solve in the contest => Solution must be quite simple, aka spot the pattern or trick and the rest will fall out. Ok, seems that we need to find a simple solution, do not tunnel vision into the first approach you have! Try out a few different approaches and see which one is the most simple to implement and easier to extend: For example, I tunnel visioned into grouping all the even / odd numbers together, and then at the border of odd / even we need to make everything 1. Seems complex, so lets discard that idea (unfortunately I tunneled too hard into random ideas). Ok let us think of a very naive solution, for 4x4, we can try out 1 2 3 4 ... 14 15 16. Wow seems like it works, is it simple? yes, is it easier to extend? Hopefully. Realise that for 5x5 this doesnt work. Key insight: Think of why it doesnt work instead of just trying out other random approaches. Ok it doesn't work because the next row is +m, and m is 5. Ok so how to make the rows better? If we just think of why it doesn't work, can we possibly modify or extend this idea to make it work? Turns out, if we make the rows +2m +2m and so on, it will not be prime. So: we can place the even rows at the top and the odd rows at the bottom to make sure this difference is indeed > m and a multiple of m.

Hope this helps

My solution for 1838D - Bracket Walk:

Observation behind the approach

Any even length sequence of the form ((...)) is always walkable because the beginning and closing consecutive brackets can always be retraced to make up a valid bracket sequence, no matter the content inside. Also this is the only format of incorrect bracket sequence which gives correct path on a walk. So we can take the largest possible string of this type and just check for the correctness of the prefix and suffix bracket sequence.

Also, the prefix and suffix string should be exactly of the form k*() for k>=0. Otherwise some consecutive brackets will occur which can't be corrected in a walk because consecutive brackets of opposing type won't cover for them.

Implementation:

Maintain two sets l and r storing indices of consecutive opening (( and closing )) brackets. Also maintain a data structure (segment tree) over the an array having +1 for ( and -1 for ). For every query, check the i-1 and i+1 index for index i being updated and update the sets l and r and sum-tree accordingly. To find the answer for each query:

• If n is odd, then answer is always NO as mentioned in solution.
• If both of l and r are empty, then check the whole array (index 0:n-1) for correct bracket sequence. Answer YES or NO accordingly.
• If one of l or r is empty, then answer is NO.
• Else consider the first index where (( occurs -say x (first element of l) and the last index where )) occurs -say y (last element of r):
• If x>y answer NO.
• If 0:x-1 and y+2:n-1 are correct bracket sequences, then answer YES, else NO.

To check the correctness of bracket sequence i:j, following conditions need to be checked:

• If j<i, then trivially correct.
• If odd sequence, then trivially incorrect.
• Else, check sum[i:j]==0 and i==1 using sum-tree in O(logn)
• Also check that none of indices of set l or r lie in range i:j, checking first and last elements suffice in O(logn)

Time Complexity O((n+q)logn)

Here's my solution using this approach, although I wasn't fast enough to implement during contest time: 208516428

Hey .. Can someone suggest me a video to understand D , having a hard time warping my head around it

Hi, is there to way to download the test data for problem C? Pretty sure the code should work for all inputs but it keeps finding an error, I often make some stupid mistake in code but already removed 3 problems from it and can't find another.

during contest:

WTF is this, I hate this contest.

After reading editorials :

what a beautiful problems. How much more stupid I can be !!!

can someone explain solution for c

in D, what is the point to go back and forth in the bracket sequence? why it will not be a valid walk otherwise? Can't I walk directly from 1 to n if it is a regular bracket sequence?

I feel so stupid right now, I got C solution but did not implement it because I was fixed on the fact that 1 is not composite and forgot that it is not prime either.

Yet again, so close to D. I knew it had something to do with two consecutive brackets but my mind went to prefix sums and segtrees to count the balance and I ended up ditching it

When solving E, got weird answers on the samples, after 20 mins of debugging, found that I forgot to read the input array...

Alternative solution for B: We only need to consider 1 and 2 as we want 1 and 2 far as possible. Because of that, there are at most 4 cases regarding choosing element 1 or 2 and swapping it with the element in position 1 and n.

My logic for 877D Problem D ( no segtree and all):

Basically, just maintain two sets left and right so that left stores the indices i at which we have i & i+1 consecutive opening brackets. Similarly, right stores indices i s.t. i & i+1 both are consecutive closing brackets. Now, I claim that we just need these two sets to see if our string is walkable or not.

Note that, updating these two sets after each query is simple. Since you just check the query index, the index before that and index after that and corresponding add or remove from both left and right sets.

For final answer at each query, just see if the lowest value in left set is smaller than the lowest value in right set, and similarly, the highest value in left set is also smaller than highest value in the right set. After all these checks are done, we can't simply say 'YES' as there can be strings starting with ) and ending with (, so just check for these two positions in the string and output YES and NO accordingly.

Here is the working run on input test case (most of it atleast ^_^):
String : (())()())) left: {1} right: {3,8,9} "YES"
switch position 9 String : (())()()() left: {1} right: {3} "YES"
switch position 7 String : (())()))() left: {1} right: {3,6,7} "YES"
switch position 2 String : ()))()))() left: {} right: {2,3,6,7} "NO"
switch position 6 String : ()))(())() left: {5} right: {2,3,7} "NO"
switch position 3 String : ()()(())() left: {5} right: {7} "YES"
switch position 6 String : ()()()))() left: {} right: {6,7} "NO"
switch position 7 String : ()()()()() left: {} right: {} "YES"

Here is my submission: 208584903

E's solution is so elegant!

I wonder what is the editor's solution for problem A to check ALL possible correct answers? Also, "If there are multiple solutions, print any of them" statement is not entirely clear. It could mean that you accept either of two numbers. But since editorial mentions that for 9 2 7 both 2 and 7 are correct answers (in addition to 9) that means that you accept all possible starting numbers, not only those actually used for the generation.

So you can't simply generate some sequence from 2 numbers and then only accept them. You need to accept all possible initital combinations. And in case of hacks, you even don't know how the hack was generated (but you need to check that this is correct sequence anyway).

So the editor's solution should include some algo to generate all possible initial states. Is that's why $$$n \le 100$$$ ? So for each initial pair of numbers you can greadily grow the set of all numbers ($$$O(n^4)$$$) or so?

This is just sad. Wait, no, not just sad. Sad and enraging.

Did someone else also found problem D ("Bracket walk") a little confusing. I can't even wrap my head around the editorial as well!

Solution for Problem A (I recommend watching it in 1.5X speed)

Codeforces Round 877 Solution A Blackboard List

I solve F in a constant number of queries

Firstly we do this queries (i mean n=10 here)

? 1 1

. >>>>>>>>>v

. <<<<<<<<<v

. v<<<<<<<<<

. v>>>>>>>>>

. >>>>>>>>>v

. <<<<<<<<<v

. v<<<<<<<<<

. v>>>>>>>>>

. >>>>>>>>>v

. <<<<<<<<<v

(. is not a belt...)

(and 7 similar queries for the different parity of n and different orientation of the table) (it is like a snake but with row/columns skips)

After this queries we should know three rows where the hidden belt is placed if its direction is ^ or v and three columns if its direction is < or > . (Or something like this)

And in one row we can check all the ^ or v directions of the belts by this pattern

? 2 1

^^^^^^^^^^

vvvvvvvvvv

vvvvvvvvvv

vvvvvvvvvv

vvvvvvvvvv

vvvvvvvvvv

vvvvvvvvvv

vvvvvvvvvv

vvvvvvvvvv

(i mean this is for the second row).

So we will do the constant number of queries

https://mirror.codeforces.com/contest/1838/submission/209006788

I solved E with an overkill solution that is worth mentioning using generating functions:

I arrived at the DP solution where (if we let $$$f(i, j)$$$ be the number of arrays of length $$$j$$$, such that the subarray of length $$$i$$$ in $$$a$$$ appears in it), then we get

and note that $f(n, m)$ is our answer.

Now, if we let $$$B_i(x) = \sum_{j \ge 0} f(i, j)x^j$$$, we can multiply the last equation by $$$x^j$$$ and sum for $$$j \ge 1$$$, and then we get

then we get

this means

And note that since we want $f(n, m)$, we just want the coefficient of $$$x^m$$$ in $$$B_n(x)$$$.

Now, note that by the generalized binomial theorem, we know

and so

and

and so (using the definition of power series multiplication, check this)

so let $h = m - n$, the answer to our problem is just

(be aware that this solution assumes $$$0^0 = 1$$$, so when $$$k = 1$$$, $$$(k - 1)^i$$$ shall produce $$$1$$$ at $$$i = 0$$$).

Let $$$d = (k - 1)/k$$$, and note that our summation is now

so we are only interested in finding the summation and disregard the $k^h$ for now.

Note that $$$\binom{n - 1}{n - 1} \cdot d^0 = [x^{n - 1}](x + d)^{n - 1}$$$, and $$$\binom{n}{n - 1} \cdot d^{1} = [x^{n - 1}](x + d)^{n}$$$, in general, the required sum is

but since there is no term with $x^{n - 1}$ in $$$(x + d)^i$$$ for $$$i < n - 1$$$, we that the above is the same as

or by the geometric series formula

now if we ignore the -1 in the denominator for a moment, we note that since

then the required coefficient is

which is finally a summation up to $n - 1$ which is computable in the given time limit!

We just have to be careful that when $$$i$$$ hits $$$n - 1$$$, we have to take care of the -1 in the numerator that we just ignored, because the constant term in $$$(x + d)^m - 1$$$ is $$$d^m - 1$$$ not $$$d^m$$$, and now we can just tweak this summation a bit:

is the same summation but going backwards, and multiplied by the $$$k^h$$$ or $$$k^{m - n}$$$ that we disregarded above, but we just note that we can compute all $$$\binom{m}{i}$$$ the same way we did in the editorial. Here is my submission.

P.S. I know, again, it is a very overkill solution, but I hope whoever read it all learned something from it :D

I think that 2500 rated. E problem is almost same as atcoder abc 171 F-Strivore and if you look at its editorial you get another elegant way to think about the problem

The editorial for $$$E$$$ came up with such a nice expression. For comparison's sake, here's the form I came up with:

(by the way, to make things simpler here, I decremented $$$k$$$ at the start)

It gets AC thankfully: 211182571

What a good E! The ignorance of the array $$$a$$$ is amazing!