Hello, Codeforces!

Hope you enjoyed the round! Editorials for all problems are out now. I hope this editorial be informative and helpful.

## 1557A - Ezzat and Two Subsequences

**Hint 1**

The average of a group of numbers always has a value between the minimum and maximum numbers in that group.

**Solution**

Since the average of a group of numbers always has a value between the minimum and maximum numbers in that group, it can be proved that the best approach to obtain the maximum sum of averages of two subsequences is to put the maximum number alone into one subsequence, and the rest of the numbers into the other subsequence. A proof by contradiction follows.

Assume a sorted array, so $$$a_1 \le a_2 \le \ldots \le a_n$$$. Assume that there exists a bigger answer if you take the two greatest numbers (instead of only one) in one subsequence. Therefore, we need to prove that:

$$$\sum_{i=1}^{n-1} a_i / (n - 1) + a_n < \sum_{i=1}^{n-2} a_i / (n - 2) + (a_{n-1} + a_n) / 2$$$

By simplifying the inequality:

$$$a_n < 2 / (n - 1) \cdot \sum_{i=1}^{n-2} a_i / (n - 2) + (n - 3) / (n - 1) \cdot a_{n-1}$$$

Assume $$$avg_1 = \sum_{i=1}^{n-2} a_i / (n - 2)$$$, so $$$a_1 \le avg_1 \le a_{n-2}$$$ as stated at the beginning of the tutorial. The inequality becomes:

$$$a_n < (2 \cdot avg_1 + (n - 3) \cdot a_{n-1}) / (n - 1)$$$

The right-hand side of the inequality is also an average $$$avg_2$$$, such that $$$avg_1 \le avg_2 \le a_{n-1}$$$ (which can be further simplified to $$$a_1 \le avg_2 \le a_{n-1}$$$).

This means that $$$a_n$$$ is strictly less than $$$avg_2$$$. In other words, it states that $$$a_n$$$ is strictly less than a certain number between $$$a_1$$$ and $$$a_{n-1}$$$. This is a contradiction as we stated at the beginning of the proof that the array is sorted ($$$a_n \ge a_{n-1} \ge \ldots \ge a_1$$$). Summing things up, taking at least one number along with the maximum number will never yield a greater answer.

**Code**

## 1557B - Moamen and k-subarrays

**Hint 1**

You can ignore the $$$k$$$ given in the input, try to find the minimum $$$k$$$ you need to sort the array (let call it $$$mnK$$$).

If $$$mnK$$$ $$$\le$$$ $$$k$$$ then you can split some subarrays to make it equal $$$k$$$, so the answer is will be "YES". otherwise, the answer will be "NO".

**Hint 2**

You need to split the array into the minimum number of subarrays such that each subarray is sorted.

**Solution**

This problem can be solved for \textbf{at least} $$$k$$$ subarrays as it is easy to just add extra subarrays (if needed) to achieve \textbf{exactly} $$$k$$$ subarrays. To solve this problem, you need to know what are the numbers that can be grouped into the same subarray. This can be done by maintaining the sorted array along with the non-sorted array.

As the numbers are distinct, we can iterate over the non-sorted array, and just add each element $$$a_i$$$ to the subarray ending in $$$a_{i - 1}$$$ IFF they follow each other in the sorted array, or start a new subarray if they do not follow each other.

For example, if the (non-sorted) array is $$$[$$$ $$$2$$$, $$$3$$$, $$$ -1$$$, $$$1$$$], the sorted array will be $$$[$$$ $$$-1$$$, $$$1$$$, $$$2$$$, $$$3$$$ $$$]$$$. If we iterate over the non-sorted array, we will add $$$2$$$ to a new subarray, then we will add $$$3$$$ to the same subarray as they follow each other in the sorted array. After that, we will start a new subarray at $$$-1$$$ as $$$-1$$$ and $$$3$$$ do not follow each other in the sorted array. Finally, we will add $$$1$$$ to the subarray containing $$$-1$$$. It should end up like this: { $$$[$$$ $$$2$$$, $$$3$$$ $$$]$$$, $$$[$$$ $$$-1$$$, $$$1$$$ $$$]$$$ }.

Using this approach, you can get the smallest number of subarrays needed. If it is strictly greater than the given $$$k$$$, the answer is ''NO''. Otherwise, it is ''YES''.

**Code**

## 1557C - Moamen and XOR

**Hint 1**

We don't care about the values in the array to know it's valid or not, we just need to know for every bit how many numbers have this bit on or off.

**Hint 2**

Try to build the array from the most significant bit ($$$k-1$$$) to the least significant bit $$$0$$$ using dynamic programming.

**Hint 3**

Can you optimize dynamic programming code with some combinatorics?

**Solution**

From now on, I will use $$$And$$$ to describe the result of the bitwise AND operation over all the elements in the array, and $$$Xor$$$ to describe the result of the bitwise XOR operation over all the elements in the array.

Let's call the array is valid if the value of $$$And$$$ $$$\ge$$$ $$$Xor$$$.

We don't care about the values in the array. We just need to know, for every bit, the number of indices at which this bit is on or off.

So let's build the array from the most significant bit ($$$k-1$$$) to the least significant bit ($$$0$$$) using dynamic programming and combinatorics optimization.

Define an array $$$dp$$$ where $$$dp_{i, equal}$$$ $$$=$$$ the number of ways to build the array from the $$$i$$$-th bit to $$$0$$$-th bit. $$$equal$$$ is $$$true$$$ if $$$And$$$ $$$=$$$ $$$Xor$$$ in the previous bits, and $$$false$$$ if $$$And$$$ $$$>$$$ $$$Xor$$$ ($$$And$$$ $$$<$$$ $$$Xor$$$ is not a valid state).

Our base case is $$$dp_{-1,0}$$$ $$$=$$$ $$$1$$$, and $$$dp_{-1,1}$$$ $$$=$$$ $$$1$$$.

If $$$equal$$$ is $$$false$$$ at any moment, then you can choose any subset of indices to contain $$$1$$$ in the $$$i$$$-th bit.

Therefore, $$$dp_{i,0}$$$ $$$=$$$ $$$2^n$$$ $$$\cdot$$$ $$$dp_{i-1,0}$$$.

Now if $$$n$$$ is odd there are $$$2$$$ possible choices:

- You can make $$$i$$$-th bit $$$=$$$ $$$1$$$ in an even number of indices, then $$$And_i$$$ will be $$$0$$$ and $$$Xor_i$$$ will be $$$0$$$ too.
- You can make $$$i$$$-th bit $$$=$$$ $$$1$$$ in all indices, then $$$And_i$$$ will be $$$1$$$ and $$$Xor_i$$$ will be $$$1$$$ too.

You Don't have any other valid choices. So $$$dp_{i,1}$$$ $$$=$$$ $$$dp_{i-1,1}$$$ $$$\cdot$$$ ({number of ways to choose number of indices from $$$n$$$} $$$+$$$ $$$1$$$). ($$$+1$$$ for the second choice).

If $$$n$$$ is even there are $$$2$$$ possible choices:

- You can make $$$i$$$-th bit $$$=$$$ $$$1$$$ in an even number (less than $$$n$$$) of indices, then $$$And_i$$$ will be $$$0$$$ and $$$Xor_i$$$ will be $$$0$$$ also.
- You can make $$$i$$$-th bit $$$=$$$ $$$1$$$ in all indices, then $$$And_i$$$ will be $$$1$$$ and $$$Xor_i$$$ will be $$$0$$$. and now $$$equal$$$ will be $$$false$$$.

You Don't have any other valid choices. So $$$dp_{i,1}$$$ $$$=$$$ $$$dp_{i-1,1}$$$ $$$\cdot$$$ (number of ways to choose number of indices from $$$n$$$ ) + $$$dp_{i-1,0}$$$.

We can precalculate the factorial, to get $$$nCr$$$ in $$$\mathcal{O}(1)$$$, and then calculate the number of ways to choose an even number from $$$n$$$ before starting the $$$dp$$$. The total complexity will be $$$\mathcal{O}(k + n)$$$.

**Code**

## 1557D - Ezzat and Grid

**Hint 1**

Try to count the maximum number of rows that makes a beautiful grid, and remove the others.

**Hint 2**

Can you get some dynamic programming formula, and then optimize it with some ranges data structures?

**Solution**

We can use dynamic programming to get the maximum number of rows that make a beautiful grid.

Define the 2d array, $$$dp$$$, where $$$dp_{i,j}$$$ $$$=$$$ maximum number of rows (from row $$$1$$$ to row $$$i$$$) that make a beautiful grid, and has $$$1$$$ in column $$$j$$$ at the last row I have in the biggest beautiful grid. the last row in the biggest beautiful grid is the not necessary to be $$$i$$$

Form the definition:

$$$dp_{0,j}$$$ $$$=$$$ $$$0$$$.

$$$dp_{i,j}$$$ $$$=$$$ $$$1$$$ $$$+$$$ $$$\max_{k \in C_i}$$$ {$$$dp_{i-1,k}$$$} if $$$grid_{i,j}$$$ $$$=$$$ $$$1$$$.

Otherwise, if $$$grid_{i,j}$$$ $$$\neq$$$ $$$1$$$, then $$$dp_{i,j}$$$ $$$=$$$ $$$dp_{i-1,j}$$$ .

where $$$C_i$$$ is that set of columns that contain $$$1$$$ in row $$$i$$$.

As you know, the set $$$C_i$$$ contains the intervals, so we just search in some intervals for the maximum, or update some intervals in the previous layer in $$$dp$$$. We can do it faster using Segment tree.

**So the algorithm will be as follows:**

Define an array $$$prev$$$, where $$$prev_i$$$ $$$=$$$ the previous row of $$$i$$$ in which maximum beautiful grid end with $$$i$$$-th row. We will use it to get the rows that will not be removed.

Build a segment tree of pairs ($$$value$$$, $$$index$$$) initially with { $$$0$$$ , $$$-1$$$ }.

Then for each $$$i$$$ from $$$1$$$ to $$$n$$$:

- Get the maximum value in all the ranges $$$[l_j,r_j]$$$ that contains $$$1$$$ at the $$$i$$$-th row. Let's call it $$$mx$$$.

- Store $$$prev_{i}$$$ $$$=$$$ $$$mx.index$$$.

- Update all the ranges $$$[l_j,r_j]$$$ of this row like this: $$$seg_j$$$ $$$=$$$ $$$max($$$ $$$seg_j$$$ $$$,$$$ { $$$mx.value$$$ $$$+$$$ $$$1$$$ $$$,$$$ $$$i$$$ }).

- Finally, get the rows that have the maximum value using the $$$prev$$$ array, and remove the others.

The total complexity will be $$$\mathcal{O}(n + m\log{}10^9)$$$ or $$$\mathcal{O}(n + m\log{}m)$$$ if you make a coordinate compression to the values.

**Code**

## 1557E - Assiut Chess

**Hint 1**

Try to force the king to move into one of the corners down.

**Hint 2**

If you put the queen in a row $$$x$$$, move the queen to the left of the row, then start swiping the row right, one square at a time. If you've visited all $$$8$$$ squares on the row and the king never made a vertical move, it means $$$|$$$ current king row $$$-$$$ current queen row $$$|$$$ $$$\ge 2$$$ (if the king were on row ($$$x + 1$$$\$$$x-1$$$), he would've been forced to move $$$1$$$ square (down\up) at some point).

**Solution**

This is one of many possible solutions. We need to force the king to move into one of the four corners (bottom right or bottom left corner in this solution) to ensure that the king will be trapped (cannot move anymore).

Place the queen on the top row. After the king makes a $$$1$$$ move, he should be below the queen's row.

Suppose the queen is on the row $$$x$$$ with the king below it (row $$$x$$$ $$$+$$$ $$$i$$$ where $$$i$$$ > $$$0$$$).

If $$$i$$$ $$$=$$$ $$$1$$$, we cannot move down to the next row as the king may move up and we will not be able to trap it. Otherwise, we can move down by one unit.

To ensure that the king is not on the next row, scan the current row, $$$x$$$, by moving the queen from the leftmost column to the rightmost column one square at a time. Therefore, you can move the queen as follows:

During the scan, if you have visited all $$$8$$$ squares of the current row and the king never made a vertical or diagonal move, it means that $$$i \ge 2$$$ and you can go down by one row. It is now guaranteed that the king is still below the queen.

If the king were on row $$$x$$$ $$$+$$$ $$$1$$$, he would have been forced to move $$$1$$$ square down at some point. If he ever goes down, move the queen down by one row.

If the king moves up, start scanning the row again. This can only happen a limited number of times without the king moving into a check.

In total, the queen needs to apply step $$$2$$$ up to $$$8$$$ times. At each row, step $$$1$$$ needs to be applied, so it takes $$$8$$$ moves. Step $$$1$$$ also needs to be applied every time step $$$3$$$ is applied, which can happen at most $$$8$$$ times. In total, that is $$$8$$$ $$$\cdot$$$ $$$(8$$$ $$$+$$$ $$$8)$$$ $$$=$$$ $$$128$$$ moves.

**Code**

Auto comment: topic has been updated by AhmedEzzatG (previous revision, new revision, compare).even though the round has many problems, but no one can disagree that the problems were great and beautiful.

So there is no explanation on how this wrong solution passed the system tests?

ok. It's maybe wrong. but it's just hard to make an Interactor counter all such solutions I guess. We tried to kill all the wrong solutions of the testers. actually, there were only 2 testers who could solve the problem.

Good idea,but weak interactor :(

I think using math formula in C more beautiful and easier than editorial

My solution using some binomial theorem and flt 125416610

It faster than editorial solution

can you explain what did you do?

$$$\binom{n}{0}+\binom{n}{2}+ \cdots = 2^{n-1}$$$

You can calculate this by using Binomial Theorem, which you subtract $$$(1+1)^n$$$ with $$$(1-1)^n$$$

However, there's an exception. When $$$n=0$$$ , the left part is 1. That's because $$$(1-1)^n$$$ will become undefined.

Don't ignore that during exam :)

explain please, I solved it pure math too, you can look at my 125416186 to see what things I already understood so that you could skip them if you want to.

flt is Fermat's little theorem?

Ah, I got it. To calculate mod divide you have to find the inverse of the denominator where Fermat's little theorem is used.

thanks

thx!

Dude, your logic for when n is even was really funny. Good one!

can somebody tell me abt my WA https://codeforces.com/contest/1557/submission/125416469

m[max_ele] = 0

and 0 can be a valid element in your input array.

so thats reducing your cnt1 by 1 in test 3. and hence a WA.

thnks broo

If input array have duplicates your m[a[i]] will be over written and hence some data is lost this will produce an error suppose that array is 2 2 2 2 then always a[i]=2 and m[2] will be over written 3 times and eventually will store the last value and previous will be lost

Back to back segtree problems for the past 3 rounds.

Can you share the interactor as well? Would be interesting to know how does it decides where to move the king.

We try a lot of strategies for each cell, some greedy (for example, we try to make the king stay in the mid cells, Or try to go Up\downs if possible), and others random. maybe I will share the code later.

Randomized approach for E:

It seems that this solution uses far less than $$$130$$$ queries, or can you kill my solution?

my code

We can actually checkmate the king in 5 (4 if the queen stays out of the edges) moves by checkmating on the edge!

https://imgur.com/a/mwBV1Zk

I think that can get rid of the randomization part as if we place the queen at (4, 4), there are at most 31 squares the king can initially occupy. Thus, we have an upper bound of 4 * 31 = 124 queries.

However, in practice, the solution generally uses <10 queries.

Code: 125423506

Whoa this is genius O_o

Just in case this helps anyone, I tried to implement a cleaner and commented version of the code above. The zig-zag idea is really nice!

127869222

Can someone elaborate what are the leaves of seg tree used in D? If rows would have up to 10^5 columns the seg tree would be trivial, but with 10^9 I wasn't able to come up with seg tree structure and editorial didn't help neither.

Even the "dpi,j = maximum number of rows (from row 1 to row i) that make a beautiful grid, and has 1 in column j at the last row." doesn't make much sense to me, as there can be up to 10^9 j indexes.

yes they didn't wrote it explicit, but in the end they wrote you can use coordinate compression.

that would reduce columns from $$$10^9$$$ to $$$2m$$$.

Exampleyou have segments: $$$[1,10],[2,20],[3,30]$$$

you can process them as $$$[1,4],[2,5],[3,6]$$$

i will still yeild the same answer for the problem.

and you only $$$\text{dp}[i-1]$$$ to compute $$$\text{dp}[i]$$$ . so you can use one single row of $$$2m$$$ size and use segment tree to maintain it. all m updates in $$$\log{n}$$$ time.

i did got the idea in the end and also implemented but i am getting WA at test 4.

if anyone can help be debug.

I used the same approach and got AC. I think you made a mistake in the update function. While updating the segment tree we need to check whether a higher value is updated to lower value. 125463800

thanks, yes i did that check with

`ppgt()`

function which will propagate any changes that were made along the path we need for query/update, i missed a part in`ppgt()`

to reset current root's lazy value to null after upddting its children. silly mistake, took me hours to find out.Solution for first three questions. https://www.youtube.com/watch?v=vBqSLVoXYsI

Love this round. Hoping to have more lovely rounds like this in the future. (◍•ᴗ•◍)❤

My heart starts bitting faster every time I see 5 problems in a contest. I was at the top of my abilities to solve C today

SegmentTree for D is such an overkill.

Can you please brief your approach without segment tree for D.

Do you mean you can do it without segment tree?

We can get every set of rows $$$i$$$ that for each column $$$j$$$, $$$grid_{i,j}=1$$$. Then construct a DAG by connecting the edges of each row in the sets from the first to the last, and find the longest path on the graph. The comlexity is $$$O(n+m)$$$.

How did you do it without a log factor?

Yes you are right. It's difficult to get rid of a log factor on the work before DP. I mean you can find the longest path on the DAG in $$$O(n+m)$$$.

how does this work tho? doesnt longest path in dag have complexity O(V + E), how do you make sure there aren't too many edges cause then i would assume it becomes O(N^2). I looked at your code and it looks like there are only N edges but I don't get how something like that would work unless you are compressing the dag?

Can you explain how to generate the graph in O(n+m)?

Hello , I didn't get the logic behind 2nd problem .

https://ide.geeksforgeeks.org/8684Y9kbwQ

I'd suggest you clean out your code a little before asking for help!

Sorry .

You can check this one .

https://ide.geeksforgeeks.org/8684Y9kbwQ

I have cleaned unnecessary things.

What is your thought process exactly for this question?

First I determined the number of increasing subarrays and stored each and every segments' first and last number in a vector (vv). Then , checked if the number is greater than given number (m) or not . If yes , then output (NO) [the number i determined , that is the minimum number of breaks].

else { sort the vector (vv); then checked vv[i].first > vv[i-1].second (i>0) , because only then we can merge the whole thing and get sorted array (final and).

If at any point , this condition gets violated , simply output(NO). else at the end print(YES).

}

AhmedEzzatG, Can you check why it is showing wrong answer ?

Try for this testcase 5 3 2 5 4 7 8

Output:No

Yeah , it's giving NO

Why do I get WA on pretest 2? https://codeforces.com/contest/1557/submission/125391145 Brief explanation: If $$$n$$$ is odd, the answer is just $$$(2^{n-1}+1)^k$$$. Otherwise, if $$$A_n(j)$$$ is the number of ways for the bits from 0 to $$$j$$$ such that $$$And\geq Xor$$$, I get the recursion $$$A_n(j+1)=2^{nj}+2^{n-1}A_n(j)$$$, which solves to $$$A_n(k)=2^{nk-k}+2^{kn-n+1}-2^{nk-n-k+2}$$$. Where is the flaw?

EDIT: found it, wrong recursion, it should be

AhmedEzzatG Do you mind looking into why this solution fails on D? I used the approach described in the editorial during the contest, but really have no clue why the 4th pretest is failing. It's giving me headache. Thanks.

125401562

Hi, sorry for delay. you have a small bug in segment tree code in line 68.

`return tree[v] = max(query(2 * v, l, m, ql, qr), query(2 * v + 1, m + 1, r, ql, qr));`

it must be

`return max(query(2 * v, l, m, ql, qr), query(2 * v + 1, m + 1, r, ql, qr));`

Thank you so much, I appreciate it. A dumb mistake that yet again cost me -200 delta.

Regardless, I liked D very much (the only problem I attempted, so I can't say for others) and I had a great time solving it, although it gave me some trouble. Thanks for the round!

really quick pure combinatorics sol for C:

We'll look at each bit independently. The bit for the LHS will be 1 iff all the bits are 1 and 0 otherwise. For the RHS, the bit will be 1 iff the number of bits that are ones is odd, and 0 otherwise. In order to handle both at the same time, you need to split into cases based on the parity of $$$n$$$.

Suppose $$$n$$$ is odd. Then, you can never have the case that the LHS is strictly greater than the RHS, because if the AND is equal to 1, then the number of bits that are 1 is odd, meaning the XOR is 1. Thus, you must have equality.

If both the LHS and RHS is 1, then it must be all ones so that is 1 way. Then if both sides are equal to 0, we must have exactly an even number of ones, or

which is equal to $$$2^{n-1}$$$. Thus, in the odd case, the answer is $$$\left(2^{n-1}+1\right)^k$$$.

Now suppose $$$n$$$ is even. This time, it is possible to have the strict inequality by taking all ones. You then must consider two cases: when we have equality for both sides and when we have the strict inequality.

We tackle the first case. Both bits can not both be equal to one, as that would require all the bits to be one, for an even total, and an odd number of ones, contradiction. Thus we need both to be 0, meaning not all bits are equal to 1, and we must have exactly an even number of ones. This corresponds to

Again, this can be seen to be equal to $$$2^{n-1}-1$$$ through whatever method you want. Thus, there's a total of $$$\left(2^{n-1}-1\right)^k$$$ arrays in this case.

Now suppose we have a strict inequaltiy. What we'll do is fix the bit where we have a 1 on the LHS and 0 on the RHS, and iterate over the positions for that bit: suppose the $$$i$$$'th bit will satisfy this. For the $$$i-1$$$ bits before it, we must have equality, which gives $$$\left(2^{n-1}-1\right)^{i-1}$$$ from the analysis of the previous case. Then, we have exactly 1 way to get the $$$i$$$'th bit, which is to take all ones. Then, the remaining $$$k-i$$$ bits don't matter, so there are $$$\left(2^n\right)^{k-i}$$$ choices here.

Putting both cases together and summing over all $$$i$$$, we have

different arrays in the case that $$$n$$$ is even. Compute this now however you want.

If you wanted a closed form for this, you can see that the summation is actually equal to

where you use the factorization

EDIT: sorry for the typoes oops as you can tell i am terrible at proofreading

hey, I implied your method: can you tell me, why I'm getting the wrong answer my submission: 125428860

could you please amend it as well?

if n is even,it should be

Yes, of course... thanx This dickhead has wasted my 3 hours posted the wrong solution. And I was thinking something is wrong with my modular template.

something is wrong with your mindset.

In the 4th paragraph, "we must have exactly an even number of

zeroes" => "we must have exactly an even number ofones"Nice comment, however be careful with the case: $$$2^{n - 1} + 1 \equiv 0 \mod M$$$.

In this problem

it won't occur, but it could happen if $$$M = 998244353$$$, for example:and the answer is $$$2^{n k} + k \cdot 2^{n(k - 1)}$$$ for this special case.

How did you conclude that for M = 1e9 + 7, ((2^(n-1) + 1) mod M) won't ever be 0. And why is the answer 2^{n k} + k * 2^{n(k — 1)} for this case?

Also, I'd be glad if anyone could recommend learning resources (preferably text) for the same.

compute all $$$2^n, n = 0, \cdots M - 1$$$ or some primary number theory.

You may need to learn

`markdown`

,`mathjax`

or`tex`

.Use contradiction.Assume that there exists an $$$n$$$ such that

Assume that $$$n$$$ is the smallest root of that equation.

Assume that $$$m$$$ is the smallest root of the equation

It's easy to see that $$$m|10^9+6$$$ and $$$m\mid 2n$$$ but $$$m\nmid n$$$.

So we can know that $$$2|m$$$ and $$$\frac{m}{2}\mid n$$$ and $$$\frac{2n}{m}$$$ is an odd number.

It's easy to see that

However

So we can know that $$$2^\frac{m}{2}\equiv -1\bmod 10^9+7$$$.

According to $$$m|10^9+6$$$ we can know that $$$\frac{10^9+6}{m}$$$ is an odd number.

So we can know that

In other words

However

Contradiction.

Sorry for my bad English :(

hey, can u tell me that in your even n case, in sub-case of inequality, while setting i bit as most significant, for k-i bits answer should be (2^n)^(k-i) because we do not have to set any specific bit in all n numbers as same (in those k-i bits)..

and in your case of 2^(k-i), we imply that ith bit is same in all n numbers(in those k-i bits), which is not necessary..

Could you explain how exactly did you arrive at the closed form equation?

It's is a geometric series so one can get it by applying the formula for summing a geometric series and then simplifying; however I actually got it by working through all the steps:

Divide by the ratio of consecutive terms (one would normally multiply, but dividing seems simpler here):

Take the difference between the sum from 1 to k and the sum from 0 to k-1:

Simplify:

could some one tell me why this is wrong https://codeforces.com/contest/1557/submission/125421372

You could have a contiguous subarray but you might have a value that splits that contiguous array into parts E.g- 1 2 3 7 4 and k=2 your solution would give yes but the answer is no because 1.2.3.7 is contiguous but 4 needs to be put in between 3,7 so it needs 3 subarrays

Could someone explain why time limit is exceeded on this, https://codeforces.com/contest/1557/submission/125366350

`double`

s instead of`float`

s.Fixed solution: 125475544

Okay that makes sense, thank you

Np, have a nice day!

PLEASE help with this I was unable to find my mistake WA on testcase 3

https://codeforces.com/contest/1557/submission/125378949

try case 1 4 7 3 with K =2 , i think your solution would give yes but the answer is no

thats not the case .... anyhow I got my mistake ->it is map is initialized with 0 for the last element in sorted it should be initialized with a element we cannot expect in the array I now changed it with INT_MIN _>it worked THANKS FOR REPLLYING

I think it's meaningless to set the space of problem D so tight…… It's hard for $$$O(m\log10^9)$$$ to get pass, since it's easily getting MLE.

But also great problems, thanks for the contest!

Discretization please! Codeforces Round NEVER set space limits tightly!

But a time complicity of $$$\mathcal{O}(n + m\log{}10^9)$$$ was given by the problem writer as a accepted one.

I think

`#define int long long`

is the culprit here. Maybe try removing that line and see it fits inside the memory limit or not.I have a different solution for E.

In the beginning the possible positions for KING is the whole chessboard. And if the king do a move , some positions will become impossible. So you can do $$$30$$$ random walk , to make the possible positions become very few(may be greater than one).

And for each possible position , you try to checkmate it .

You can do it for a known position in at most 8 steps :

And remember to maintain the possible positions after every move .

It seems that it use only about total $$$40$$$ moves for a test case.

code

we cannot rely on random walks what if the king is oscillating back and fro in two squares and doing random walks yr queen doesn't give check I know that probability of this is less but is not 0 so this approach can fail once in a million

In fact if you try to checkmate a position , you can also find some positions impossible .

So I think it is impossible to be hacked .

if the king only oscillates in two squares then the possible positions will be 64-16=48 and if u are unlucky enough u can exhaust 130 moves

I mean if you try to checkmate the positions one by one , you will continue finding some impossible positions .

yaa makes sense

I find the interactor for E a little "dumb": in all testcases, I made no more than 20 moves to kill the king lol (if the output of the testcase is the number of moves)

Thanks a lot for a detailed editorial.

problem E was super cute and I recommend everyone to just take a look at it :)

Well, D is a good problem. I solved many problems that can directly construct schemes through dp arrays before. But problem D ISN'T such problem, so I got Wrong answer on pretest 4. This is a good reminder to me that the record transfer is used to construct the scheme, rather than backward pushing according to the dp array.

But I'm still disappointed that I didn't passed D in the round. I am so close to the correct solution!

why I'm getting the wrong answer my submission: 125428860

could you please amend it as well?

thank you for the nice editorial

What would be the rating of Div2C question?

1700 maybe

Yeah. Thanks!

AhmedEzzatG Thank you, Sir, The problems were really Good, We can learn a lot from them.

i did this in D problem: if the first and second row have something in common(which I am precomputing) then we can just move on to next row and set previous column as current index and if they don't have anything common, then we have to find the minimum of the two cases: removing the first row and removing the second row. So I call for two functions, with previous values as current index for one and the previous index for the other.

Recursive Code:

But I am doing isMerging step in O(n), can we do it in less than that? Also, I was not able to print the rows deleted.

on what concept problem c is based upon.?

Dynamic Programming and Combinatorics

Can Anyone please figure out mistake in my C- problem code....

hello everyone In Problem B is showing runtime error in testcase 2 but the code seems to be fine have a look guys. https://codeforces.com/contest/1557/submission/125441413 kindly help if you can. Thanks

See you are not taking the vector as input when k is equal to n, therefore it results in a runtime error but even though your approach is wrong.

1

5 4

1 2 4 3 6

for the above input, your count is 2 but it should be 4 to make it sorted.

even if n==k u have to take whole input :-)

Problem C Video Editorial

I solved it in contest and I show my thought process so it might help some of you

can someone help me explain why I am getting TLE on test 78 when there are 64*60 operations at max Link to submission : https://codeforces.com/contest/1557/submission/125445885

In the solution for question C, how did he/she make the base case: dp(-1, 0) = 1 and dp(-1, 1) = 1?

not sure, I am using dp(-1,0)= 0, and dp(-1,1)= 1 (Java solution)

Can someone explain my WA? All my tests is AC, but here WA on pretest 2. https://codeforces.com/contest/1557/submission/125395144

try for

1

4 3

2 4 3 5

it should print "NO"

I understand, thank you.

How my approach is wrong for the submission of

1557B — Moamen and k-subarraysproblem ? Please help 125447732try for

1

4 3

2 4 3 5

it should print 'NO'

Got it now thanks spidermonkey

Hey, In problem

Awe proved that taking the maximum number in one subsequence is better than taking the two greatest numbers (instead of only one) in one subsequence.My question is how we can generalize this argument for the whole problem as there might be the other cases except for taking the two greatest number.AhmedEzzatGI proved it a bit differently:

Suppose the array is split into 2 sub-sequences: $$$A$$$ with $$$k$$$ elements and sum $$$S_A$$$, and $$$B$$$ with $$$n-k$$$ elements and sum $$$S_B$$$, and further assume that $$$k \leq n-k$$$.

Step 1. We can show that if $$$x \in A$$$ and $$$y \in B$$$, then $$$x \geq y$$$.

Proof by contradiction. Assume that $$$y > x$$$, then we can swap $$$x$$$ and $$$y$$$ to get a larger result:

Step 2. If $$$A$$$ has more than 1 element, we can move the smallest element of $$$A$$$ to $$$B$$$ and increase the result. Let $$$x$$$ be the smallest element of $$$A$$$. By the previous step, $$$x$$$ is larger than any element of $$$B$$$, so after moving $$$x$$$ from $$$A$$$ to $$$B$$$ both the average of $$$A$$$ and average of $$$B$$$ will increase.

I had the same problem with the editorial proof, but I easily understood yours. Truly elegant. Thanks

Editorial "proof" should be in quotes. :)

One interesting observation — if both subsequences have the same length ($$$k = n - k$$$) then the result does not depend on how we do the split and is equal to twice the total average.

Thanks for the help.You are amazing!!

The proof is not so trivial to be arrived at during the contest for div2 problem A. So, I think, most of the participants just made a guess and hoped for the best.

On the other hand, it's still problem A of div2, so if you get a hunch and go over some examples to "convince" yourself that it's the right observation, it's probably OK to trust your intuition and submit fast, and only try to prove it formally later.

For most problems of this level the challenge is to figure out the answer, and once you've done it the proof is trivial.

A correction — the statement in the first step is true only if $$$k$$$ is strictly less than $$$n - k$$$ (otherwise $$$\frac 1 k - \frac 1 {n-k} = 0$$$).

If $$$k = n - k$$$ the result is the same no matter how we split, and if $$$x \geq y$$$ for any $$$x \in A$$$, $$$y \in B$$$ it is as good as any other split.

Thank you, bro. Very helpful!

I do three problems only just a little.~~~QAQ

Problem C，forgot to add enough mod,and failed twice.100 points T T

In problem D,why adding $$$ dp[i][j] = max_{k\in C_i} {dp[i - 1][k]} $$$ step as call

`modify(1,1,N - 1,mx)`

is useless and wrong? In my opinion,tutorial's definition points out that $$$ grid[i][j] = 1 $$$ so the transfrom $$$ dp[i][j] = max_{k\in C_i} {dp[i - 1][k]} $$$ is not exist.And that's why add`modify(1,1,N - 1,mx)`

will casue wrong?:/In Problem E, this is a false promise:

after 30+ submissions of getting RTE and TLE I realized that my code making a move of the type : $$$(6, 1)$$$ -> $$$(6, 1)$$$. I should have got WA verdict but didn't.

But I got a "Wa" verdict. 125371395

It is a bit random. I got many TLEs. There is no reason I should get TLE.

I also wasted a lot of my time trying to debug why my code was getting TLE, when it should be getting WA. Honestly, this E should have been tested more, I don't know how it got published with such a weak and inconsistent interactor

Are the n and k the opposite way round in solution C than they are in the question?

Hello and Hi!, I am new to DP and tried to write a solution for C after contest. My (wrong) approach is as follows:

If $$$k$$$ is $$$0$$$ print $$$1$$$ otherwise define a $$$dp$$$ such that $$$dp[i]$$$ is the number of ways to arrange bits till the $$$i$$$ th position and win. Thus,

Now I have $$$3$$$ possible cases when Moamen wins at $$$i$$$ th bit. When the bitwise-and and xor of $$$i$$$ th bits are both $$$1$$$, when they are both $$$0$$$ and when they are $$$1$$$ and $$$0$$$ respectively. I deduced a formula using these $$$3$$$ cases

I have read the edi and also saw the combinatorial method in the comments but cannot figure out the falsity of my method. Please do tell.

Did you figure it out?

No :(

I can't understand "You can make i-th bit = 1 in an even number of indices, then Andi will be 0 and Xori will be 0 too." only one position is 1, then the xor could 1 why is 0?

maybe it means you choose even number of 1

i know it means by the author's code,but thank you

For Problem C, I think the editorial is wrong because $$$dp[i][0]$$$ is just a product of $$$2^n$$$ which corresponds to all possible cases.

Let's define two vectors of size $$$k$$$ :

Then for allcases:

And for dp:

@ustaritz in both the odd and even cases, why not also consider all 0. if all 0 , XOR = 0 and AND = 0. That is also a valid case, right?

The all 0 case is considered. It corresponds to an even number of 1 equal to 0.

I got WA on test 43 125484134 , test 43 seems random...., can somebody tell me why

I just change min() to max() and AC,why

I dont know what someone expected for when trying to copy code to on top of the leaderboard of virtual participation. Lmao

I hope that each example of the problems can be more valuable.

To be honest，the author's solution expression is not so clear,it give me some troubles. I don't know what some nouns mean, no clear explanation ，as a newboy i really sad。

Build a segment tree of pairs (value, index) initially with { 0 , −1 }.i want to know what’s the value's mean,index's mean and what they can do.having many unclear expressions,it's not only me can't understand.I can give some suggestions? I hope the author can explain clearly what those nouns can do in solutions. gaussing the means by reading code is not a good thing.

And the author's code have many details,it really wast time

In the bit manipulation question for the odd number case , I am having 2 approaches : dp[k] = (y+1) *dp[k-1]; -(1) instead of dp[k] = (y*dp[k-1]) + dp[k-1] ; — (2)

where 'y' = nc0 + nc2 + nc4 + ....+nc(n-1),basically number of ways we can have even 1s.

The 1st one is giving wrong answer, the 2nd equation is giving right answer, aren't they both the same,or is it because of some modulo properties,it is changing?

The test case where it is failing :

5 200000 200000 24567 23423 1 200000 200000 1 200000 0

My Code : https://ideone.com/RZAe22

Could somebody take a glance at this:

125611384

Do you have any idea, why this getting TLE?

AhmedEzzatG For your dp solution of problem C, when n is even, why

dp[i][1]addsdp[i-1][0]in the end? I thought the definition ofdp[i][1]is the number of ways from 0-th bit to i-th bit to buildAnd = Xor, then ifdp[i][1]addsdp[i-1][0], how's the lattercntEven * dp[i-1][1]gonna work? really confused.The editorial for problem C seems to be incorrect and definition of dp[i][] was also quite vague. Lost so much time due to this. Anyway, dp[i][0] is for AND > XOR for the

ith bit onlyi.e AND[i] > XOR[i], where AND[i] means ith bit of AND and vice-versa for XOR. Similarly for dp[i][1] AND = XOR forith bit only. Also one correction that`dp[i][0] = 2*n * dp[i−1][0]`

should actually be`dp[i][0] = 2^(n*i)`

.In the solution of D it said:

What does it mean here "last row"? Is it the row number $$$i$$$ or it is the last row of the biggest beautiful grid?

If it is the row number $$$i$$$ then the following doesn't make sense. It should be just 0.

Otherwise $$$dp_{i, j}$$$ should somehow depend on $$$j$$$, but the right hand side doesn't contain $$$j$$$ in any way

The tutorial of problem D truly has confused me a lot. Now I've figured it out:

The

last rowis not necessarily $$$i$$$ or $$$i-1$$$, it means the last row of the biggest beautiful and in that row at index $$$j$$$ it stores $$$1$$$.The

Otherwisepart is also not correct. It should be $$$dp_{i,j}=dp_{i-1,j}$$$Why is this blog getting so many negative votes, Codeforces community doesn't appreciate the authors' effort!

That's just because the terrible interactor of problem E.

I don't know any other reasonable causes.

I'm really sorry that this happened but we did everything we could to make all the wrong solutions fail. But it is difficult to find a general way for all solutions. But now I've worked on it and it's a bit better. We apologize once again for that.

Because the tutorial is badly written... and some of the problems' pretest is

tremendouslySTRONG.In the tutorial of problem D, the following statement is not correct:

Should be: If $$$grid_{i,j}\not=1$$$, $$$dp_{i,j}=dp_{i-1,j}$$$.

Yes, I am confused about this, thanks.

Sorry for this mistake, I have modified it now.

Is the solution for problem A wrong? I think we can not sum things up like that

What do you mean?

If we devide sequence to the biggest number and the others. He proved that moving second biggest num to the group of biggest number wont have better solution. But this does not mean its true for other cases, I know there is another solution, you can read comments above

Yes, this has been pointed out above.

You can generalize the proof to any size of the sequence, not just 2. However, I think the proof in this comment is better than the editorial proof.

Maybe you can, but you did not. :)

The first edi that has -100 downvotes :/

This is not the worst, the worst is the announcement of a contest with several hundred downvotes :/

Can somebody please help me figure out, why my code, which quite literally implements the solution described in the editorial (except that I am scanning from left to right instead of top to bottom), not work? It gives runtime error because my queen somehow enters the 8th column, whereas it should be able to checkmate while it is in the 7th column. Any help in figuring out the error (either in the solution or the implementation) would be appreciated.

CodeWhy so much hate around this contest? It wasn't bad at all, C and D were interesting enough and the other tasks were good, maybe only E wasn't finally prepared but it's not the point to hate the whole thing :\ what a heck

Can somebody pls explain what's wrong with if statements in B solution 125803557? 3 tests passed succesfully, but on the 4th test i got an execution error. i have already implemented my own solution 125803196, but it also got an execution error on 4th test case, so after many unsuccesful tries to figure out what's wrong (i'm pretty sure that everything is correct) i deсided to check author's solution and just rewrite it (first attachment) but i left if statements (which i think are correct), sent the code and again got execution error and only when i removed if statements all tests passed correctly. how and why? i'll be grateful for any explanations.

AhmedEzzatG I don't understand the following part:

`If equal is false at any moment, then you can choose any subset of indices to contain 1 in the i-th bit.`

You could select the odd number of indices to contain the i-th bit and then And would become less than Xor.

If $$$equal$$$ $$$=$$$ false that mean $$$And$$$ > $$$Xor$$$ in the previous bits. Therefore, whatever the value of $$$And$$$ or $$$ Xor $$$ in i-bit, $$$And$$$ will remain greater than $$$Xor$$$.

I have a solution to problem E that only needs 16 moves in worst case, verified by DFS.

https://codeforces.com/contest/1557/submission/125862124

I believe it can be made better, but that means slower runtime and will be hard to verify.

A simple random solution for E: 126166286. Just do random moves and try to keep a list of valid starting positions for the king each time. When just one starting cell remained, simply trap the king.

Why this entry has so many downvotes?

About B,I use map<int,int> nxt,directly link the next value,but I failed Test3 in 58th case,I don't know why,anybody can find the mistakes in may code?It will help me a lot,thanks so much!

same for me if u can help me i my code in a post i failed in 3rd one why ?

guys for problem number 2, my solution it seems right but don't get AC, it is like i got vector of pair<int, int> then first part i put {number, index} then i sort them for every number index i go right and left in array and check if it is the next number in sorted array, plz help me to see my mistake, thanks , sry for my English.

Can someone please help me in B, I can't figure out what's wrong in this approach My Solution.

Edit: I figured it out.