Выложите, пожалуйста, разбор на русском.

$$$k[x][y] = \binom{x+y}{y} - \binom{x+y}{y+1}$$$ when $$$x \leq y$$$

Thanks for the fast editorial!

For D I found a crazy solution: Because substring '10' always contributes to the length of the longest subseq 1, so erase them doesn't matter. Thinking of doubly linked list. Improve the effiency with a queue.

Can somebody explain why SYSTESTS in C were so weak? 59156761 passed all tests, though it's wrong and stupid(don't look at dfs, it's not used here) Maybe rotavirus didn't expect that there will be another solutions?

Can someone explain why this statement is true? 1204D2 — Kirk and a Binary String (hard version) "If we change any 1 to 0 and the longest nondecreasing sequence of the whole string remains the same, then we are able to change it to 0."

D is very nice and the solution can be very short. Thanks to the problem setters. https://codeforces.com/contest/1204/submission/59185334

Hey, I'm new to graphs. Can anyone please elaborate 1204C ?

Simple solution for D using stack: 59187274

For C, I just iterated over the array P and checked if the there is a direct edge between vertex P[cur] and the vertex P[cur + 2], if there is direct edge then we can not ignore P[cur + 1] vertex from the final sequence, otherwise we can ignore it ( cur — current index). I am not sure about the correctness of this approach but it passed the system tests. Can anyone find a case where this fails or is it also a correct solution ?

What happened to the tags of problem C? BTW, I think dp should be added as a tag too.

Usually, when there are an easy and hard versions of the same problem, easy one could be solved in a way, which is not possible for the hard one. Could smb share their ideas on solving 1204D1, which will not work for 1204D2, pls?

11

1 2 1 2 1 2 1 2 1 2 4

problem C second test case

i got this answer for the second test case and it gives me wrong answer could someone tell me why it is wrong ?

I solved C with DP,it took O(n×m).

I have seen problem C somewhere before on Codeforces. Can't remember in which contest? Can somebody tell me?

Does anyone have a java solution in O(n^3 + m) because my solution TLEs on case 13.

Can anyone look into my code and tell me why I am failing 6th test case in 1204C - Anna, Svyatoslav and Maps problem? I think my approach was same as in the editorial. 59175116

I am not getting approach for problem D. Can anyone pls explain why for input 111000 Output is 111000 And not 001000

I solved D using a segtree from 145E - Lucky Queries. I started with the initial string and tried setting each 1 to a 0 and seeing if any of the longest nondecreasing sequences in the nodes were affected. I could not prove it is correct; however.

code: 59190439

C can't be solved without using Floyd Warshall (equivalently, BFS from all vertices)

Going through the solutions of problem C, I have observed a lot of people (including me), solve the question without using Floyd Warshall and deleting vertices in a greedy manner. Although the solution passes all the system test cases, I believe it is wrong.

People have used 2 approaches for greedily deleting the vertices.

Approach 1 :: Checking every window of size 3 without modifying the array.

This approach fails for this test case.

4
0101
0010
0001
0000
4
1 2 3 4

Expected 1 3 4
Output 1 4

Approach 2 :: Checking every window of size 3 (while actually deleting elements using stack).

This approach fails for this test case.
4
0100
0010
0001
0000
4
1 2 3 4

Expected 1 4
Output 1 2 4

rotavirus Can you add these test cases to the problem ?

I can't understand one thing in problem C. Let's look at the third example, expected output is $$$1, 2, 3, 1, 3, 2, 1$$$. But why output $$$1, 2, 3, 3, 2, 1$$$ is wrong? It is the subsequence of $$$1, 2, 3, 1, 3, 2, 1$$$ and because we don't have loops, one of the shortests paths passing through the vertexes $$$1, 2, 3, 3, 2, 1$$$ in that order will be $$$1, 2, 3, 1, 3, 2, 1$$$.

There is another solution for problem E that has O(n + m) time complexity and has pretty simple code. Consider for each array the following path: it starts at (0, 0) and for each element in array(in given order) goes right by 1 if current element if equal to 1 and goes 1 to top otherwise (notice every path ends at (n, m)). Then it's rather obvious that if this path intersects line y=x-k, array's maximum prefix sum is more or equal to k(in other words it has prefix with sum equals to k). Now let's notice that answer is equal to sum of amounts of pathes intersecting line y=x-k for each k=1...n. It's correct because each path(and therefore each array) will be counted as many times as its maximum prefix sum equals to. Now the task is following: count how many paths go from (0, 0) to (n, m) that moves only 1 right and 1 top and intersects line y=x-k. There are 2 different cases:

1. (n, m) lies below or on the line => each path from (0, 0) to (n, m) intersects the line, therefore answer is C(n + m, n)

2. (n, m) lies above the line. To count this paths let's make the following trick: let's find the first intersection point and reflect rest of the path from the line. Than we'll get path from (0, 0) to (m + k, n — k). Notice that each path from (0, 0) to (m + k, n — k) intersects the line, so the operation may be reversed for each such path, therefore there is a bijection between paths to (n, m) intersecting the line and paths to (m + k, n — k), so the answer for this case is C(n + m, m + k)

Finally we got solution that takes O(n + m) time to precalc some features to compute C(n, k) in O(1) and O(n) time to iterate through lines of type y=x-k for k=1..n and use formulas explained above.

PS. Sorry for my English

For the A problem.I want to ask a simple question.The largest upper limit 2^100 we should input is decimalism or binary?

[delete]

I got TLE on problem 1204C - Anna, Svyatoslav and Maps during contest but got accepted when I submitted the same code with C++.

TLE with C: 59165015

AC with C++: 59196569

What is the subtle difference between C and C++? I am really puzzled :(

for C i think the systests is too weak, many wrong program can passed all tests for example only one path

Isn't the logic for k[x][y] written in reverse order for the case x <= y? If we place x-1 ones and y minus ones in the prefix part, that would sum up to x - 1 - y, thereafter placing a 1 at the end wouldn't matter, as it would sum up to x - y, which is <= 0. Similarly, if we place x ones and y-1 minus ones in the prefix, they would sum up to x - y + 1, and placing a -1 at the end wouldn't matter, because it sums up to x - y, which again is <=0. Although the recurrence is correct, the intuition behind it seems a little incorrect to me. Correct me, if I am wrong rotavirus

I think solution 1204A is not correct. Because if s=10000 which is 16 in Decimal form, then Expected output is 3. But According to the given solution, it gives 2 because of l=5.

Anyone can help me to solve this problem.

In the problem 1204A,how does the author conclude "Basically, the problem asks you to count ⌈log4s⌉". Can someone clarify?

If we change any 1 to 0 and the longest nondecreasing sequence of the whole string remains the same, then we are able to change it to 0.

can somebody prove this for problem D please??

Also this approach says it is a sufficient condition. and does not talk about its necessity.

i am not getting the rules of problem D: in test case 4: 0111001100111011101000 why is the output 0011001100001011101000 and not 0001000100001000101000?

Can someone please explain what do in problem C after obtaining the shortest path matrix using Floyd-Warshall?

In the solution for D could someone please prove the last three "obvious" observations? I.e.:

1. if a string p is fixed, then the string 1p0 is fixed;
2. each fixed string contains the same number of ones and zeroes;
3. the length of the longest nondecreasing subsequence for any fixed string is equal to the half of its length, which can be obtained by taking all zeroes or all ones.

And do these observations provide a complete description of all fixed strings?

In C, why we are not checking the vertices in same path length. Like for the test-case: 4
0101
0010
0000
0010
3
1 2 3

Output: 2
1 3
According to what given in editorial But 1 4 3 is also the shortest path from 1 to 3. In this case, the answer should be 3
1 2 3

Correct me, if I'm understanding this problem wrong?

" k[x][y]=k[x−1][y]+k[x][y−1], because if we consider any array consisting of x−1 ones and y minus ones which maximal prefix sum is 0 then adding a minus one to the end leaves it equal to 0. " Here if we take x-1 one and y minus one then why we does not take a one at the end as there is now x-1 one? editorial says that we will take one minus one at the end but here already y minus one exist.

rotavirus Can you share your code for Problem D2 Solution 2 ?

sorry rotavirus but I think there was a mistake in the explanation of problem E in the sentence "because if we consider any array consisting of x−1 ones and y minus ones which maximal prefix sum is 0 then adding a minus one to the end leaves it equal to 0; also if we consider any array consisting of x ones and y−1 minus ones which maximal prefix sum is 0 then adding a one to the end leaves it equal to 0, because x≤y".

Shouldn't it be "because if we consider any array consisting of x−1 ones and y minus ones which maximal prefix sum is 0 then adding a one to the end ... of x ones and y−1 minus ones which maximal prefix sum is 0 then adding a minus one ..." ?

sorry ，I am a rookie,and I can't understand the problem C still now , Can a friend tell me the problem C means ? After using the floyd algorithm , I dont konw how to do in the next step , why should delete the 2 in the first example? In this answer,1->2->4 sequence,the vex2 is not link the vex4,thats why? thanks in advance.....

1204D2 - Kirk and a Binary String (hard version) I have a problem in D.. -> it is confirmed that 10 is fixed, but we can change 11 to 01 as it will not affect the length of nondecreasing series and also we want the maximum possible number of 0 in our output. So thus according to me, if the input string is 001110110, then answer can be 000010010. It follows all the necessary condition. Also if the last two digits are is 01, then it can be changed to 00. So the answer to 0111001100111011101000 can be 0001000100001000101000. Please someone can tell me if I am wrong.

1204C - Anna, Svyatoslav and Maps My answer to this problem to test case -

3

011

101

110

7

1 2 3 1 3 2 1

is coming as —

5

1 3 1 2 1

I can't understand where it is wrong.?

In question D's second solution's statement, "If we change any 1 to 0 and the longest nondecreasing sequence of the whole string remains the same, then we are able to change it to 0.", the word sequence is used, while looking at the DP solution it seems like we are talking about largest non-decreasing subsequence . Can anyone please clarify and explain what it is all about?

There is another solution for problem D. Let's go from end of string s to begin and calculate number of ones and longest nondecreasing sequence of substring s[i + 1...n]. If number of ones is less then longest nondecreasing sequence of substring s[i + 1...n] and s[i] = 1, then ans[i] = 1. Otherwise ans[i] = 0. But I don't understand why is it correct.

Questions to D2. Why is it true if p and q are fixed, pq also should be fixed?

In problem C description it says the graph is directed unweighted without loops but in sample test 3

3 011 101 110

doesnt this refers to graph image link which is a graph with loop

due to the binary string, we can calculate LIS in linear time.

You can look my submission

Can someone explain why this code I found works 59246266? It seems to be reusing the dp array (where dp[n][m] stores the number of ways for the maximum prefix sum to be 0 and m = # of 1's and n = # of -1's), but it swaps the order of parameters. Below is the part where it's confusing me. It seems to be that there's some kind of correspondence between dp[m][n — 1] and the ways to make a sum of n — m. The second part of the calculation of res makes sense, since you append something with maximal sum of 0.

for(int i=1;i<=N;i++){
    for(int j=0;j<=min(i-1,M);j++){
      ll res=dp[j][i-1]*dp[N-i][M-j]%MOD;
      res=res*(i-j)%MOD;
      add(ans,res);
    }
  }

Could someone give me the code of the first solution for problem D2?

How can I get obivous like D? I've saw some problems, but I never solved a problem.

For problem D why do we just take the LIS of the whole string and check if it changes or not? Isnt there a case where for some l to r the LIS changes but for the whole string the LIS remains same? Can someone please prove it?

I found that we can solve F without dynamic programming,mathematics is just enough.

Here's my submission.

Let $$$sum(p)=\sum_{i=1}^p a_i$$$ .

We can try to find the number of sequences that $$$f(a)=x$$$ and,if $$$k$$$ is the first position that $$$sum(k)=x$$$ ,the number of $$$1$$$ from $$$a_1$$$ to $$$a_k$$$ is $$$y$$$ .Let the number be $$$tmp$$$ ,then, $$$ans+=x\cdot tmp$$$ .

For $$$a_1$$$ to $$$a_{k-1}$$$ ,the number of $$$1$$$ is $$$y-1$$$ ,and the number of $$$-1$$$ is $$$y-x$$$ .Each prefix sum from $$$1$$$ to $$$k-1$$$ must be less than x,otherwise $$$k$$$ is not the first position that $$$sum(k)=x$$$ .Similarly to Catalans,the number of this part is $$$t_1={2y-x-1\choose y-1}-{2y-x-1\choose y-x-1}$$$ .

$$$a_k$$$ must be $$$1$$$ .

For $$$a_{k+1}$$$ to $$$a_n$$$ ,the number of $$$1$$$ is $$$n-y$$$ ,and the number of $$$1$$$ is $$$m+x-y$$$ .And $$$sum(p)-sum(k)$$$ cannot be positive,otherwise $$$f(a)>x$$$ .Also similarly to Catalans,the number of this part is $$$t_2={n+m+x-2y\choose n-y}-{n+m+x-2y\choose m+x-y+1}$$$ .

Then $$$tmp=t_1\cdot t_2$$$ .The solution above works in $$$O(n^2)$$$ time.

I did same as told in editorial of Problem C , still my solution is failing on test 6. Can anyone help me in debugging this . https://codeforces.com/contest/1204/submission/61395687

Problem C is exactly same as SECRETMI from codechef

Problem $$$E$$$ alternative solution:

$$$dp[n][m] = dp[n - 1][m] + dp[n][m - 1]$$$ whenever $$$n \le m$$$.

If $$$n > m$$$, then we can let $$$g[n][m] = dp[n][m] - dp[n - 1][m] - dp[n][m - 1]$$$.

Then, via observation, if $$$n > m$$$, $$$dp[n][m] = dp[n - 1][m] + dp[n][m - 1] + g[n - 1][m] + g[n][m - 1]$$$.

Base cases: if $$$n = 0$$$ or $$$n = 1$$$, answer is $$$n$$$. If $$$m = 0$$$, answer is $$$n$$$, and if $$$m = 1$$$, answer is $$$n^2$$$.