### rotavirus's blog

By rotavirus, history, 2 years ago,

• +95

 » 2 years ago, # | ← Rev. 2 →   +87 $k[x][y] = \binom{x+y}{y} - \binom{x+y}{y+1}$ when $x \leq y$
•  » » 2 years ago, # ^ |   +2 true
•  » » 2 years ago, # ^ |   +1 Is there a good combinatorial proof for this?
•  » » » 2 years ago, # ^ |   +24 it is the same as for catalans
•  » » » » 2 years ago, # ^ |   +18 Nice, I understood it. Thanks. To the people who downvoted rotavirus's comment, you should read https://en.wikipedia.org/wiki/Catalan_number#Second_proof.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Для тех кому удобно почитать на русском вот тут все очень доходчиво Решаете для прямоугольника с высотой Х и шириной Y
 » 2 years ago, # |   +10 Thanks for the fast editorial!
 » 2 years ago, # |   +48 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.
•  » » 2 years ago, # ^ |   +4 A great obeservation. Thanks to it I understood how to solve this problem as opposed to the solution in the editorial. I don't understand why it has so many down-votes.
•  » » » 2 years ago, # ^ |   +4 People thought it was a bad joke, though I AC D with this solution. So I turned out to be a victim
•  » » 2 years ago, # ^ |   0 This is a great solution. Very easy to understand and implement as well. Why so many downvotes?
•  » » » 2 years ago, # ^ | ← Rev. 3 →   +9 Me: proposing a easy solutionProblem D:
•  » » 2 years ago, # ^ |   +10 Are you saying that we erase all '10' and change all remaining '1' to 0 and chug '10' back to reproduce the answer?
•  » » » 2 years ago, # ^ |   +6 Yup, that's the idea
•  » » » » 2 years ago, # ^ |   0 what should the answer for this test case beq. 0111001100111011101000a. 0001000100001000101000?
•  » » » » 16 months ago, # ^ |   0 Hi, regarding problem d, if you remember it.....why did you pop the the indices of '1' position, why don't you just remove all the '1' whenever you see see a next '10' like this: Q. 0111001100111011101000A. 0001000100001000101000
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Although, I think using a stack is more intuitive and neater than using a queue. Like in some solutions that people posted here and in mine: https://codeforces.com/contest/1204/submission/59214979
•  » » » 2 years ago, # ^ |   0 Appreciate that! During the contest, I thought about the idea of making erasing characters fast(doubly linked list), then make it efficient by using queue.
•  » » » » 2 years ago, # ^ |   0 Like in one of the solutions posted under this editorial you can even solve it in constant space not counting the size of the input without using a queue nor a stack by iterating through the string from the end. Here is my code for it: https://codeforces.com/contest/1204/submission/59222973
•  » » » » » 2 years ago, # ^ |   0 That's very good !
•  » » » » » 2 years ago, # ^ |   0 how he get this?
•  » » 17 months ago, # ^ |   0 This is the same as the editorial's solution.
•  » » 16 months ago, # ^ |   0 Great Solution.Very easy to implement.
 » 2 years ago, # |   +33 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?
•  » » 2 years ago, # ^ |   -14 dude, the humans' idiotism, retardness and stupidity don't have limits.obviously i cant foresee all the stupi solutions
•  » » » 2 years ago, # ^ |   +28 i understand you man, that's not your fault, but testers suck.
•  » » 2 years ago, # ^ |   0 You should hack my solution too, it's the same idea :D
 » 2 years ago, # |   0 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."
•  » » 2 years ago, # ^ |   -7 It follows from the first solution
•  » » 2 years ago, # ^ | ← Rev. 2 →   +2 (this answer was logically wrong and I am not sure how to delete it)
•  » » 2 years ago, # ^ |   +1 You could also think of solution 2 as alternative implementation of solution 1:Let's call a string p fixed if there isn't another string t of the same length which satisfies the first condition of the statementSo when you change some one to zero:If one belongs to fixed substring: SpoilerIt changes LIS of its fixed substring as well as for the whole string. Why does it change the LIS of the whole string?Its obvious that for some fixed substring you either add ones or zeroes from it to LIS.When you change some one to zero it decreases number of ones in this substring and increases number of zeroes.So in both cases it's contribution to the LIS will change.So the LIS will change! If it does not: SpoilerSuppose we found one at some index: Since if we remove all fixed substrings we'll get string that looks like this:0001111 and we've replaced all ones before current we can choose 0 in all fixed substrings before it and 1 in fixed substrings that occur before this index and 1 in all fixed substrings after it(remember, for fixed substring, number of 0s and 1s is equal) and no matter whether this index contains 0 or 1 we'll get the same LIS and its obvious that it will be optimal.So setting it to one won't change the LIS!So the we can check if this one is a part of fixed substring by checking if the LIS of the whole string changes.So it's essentially just another way to find all ones which don't belong to any fixed substrings and set them to zero.
 » 2 years ago, # |   +8 D is very nice and the solution can be very short. Thanks to the problem setters. https://codeforces.com/contest/1204/submission/59185334
•  » » 2 years ago, # ^ |   +2 Another short solution of D without stack (just simple loop, string and two int variables) https://codeforces.com/contest/1204/submission/59193063
•  » » 2 years ago, # ^ |   0 how does it work can u explain
 » 2 years ago, # |   0 Hey, I'm new to graphs. Can anyone please elaborate 1204C ?
•  » » 2 years ago, # ^ | ← Rev. 3 →   +8 I will tell you how I approached it. You should now floyd warshall as a pre requisite(3 nested loops, very intuitive). Now the moment you have all pairs shortest paths in a matrix, follow this.Consider two arrays: steps and successor. Step[i] stores the number of steps required to reach the last node from the $A_i th$ node, and successor[i] will store the index of the next position to go from i. Remember that we want a subsequence so successor can be any index greater than i. Now let us start from the back and construct both these arrays. So, for every node starting from the last you check whether it is in the path that was given to us as input at $d$ steps back, here d is distance of the node (varies from 1 to n) from the current node(ith node). If it is then it followed the shortest path since all edge weights are same(so take 1 as edge weight). Now, $step[i - d[j][i]] = min(step[i] + 1, step[i - d[j][i]])$ and to make the successor array simultaneously, update the $successor[i - d[j][i]]$ to i whenever $step[i - d[j][i]] > step[i] + 1$. Obviously $step[n - 1] = 0$ (you reach last node from last node using 0 steps). If a node that is k distance away and is at index k away from the $n - 1$th node, then it's step will be 1. And so on we will know how many steps will first node need to reach the last node and successor array will lead the way and since I have used the minimization in reaching the ultimate node, the answer will be correct, very similar to the $n^2$ Longest Increasing Subsequence solution if you want the intuition. I know it will be difficult to understand in the beginning, but try hard that's the learning curve.
•  » » » 2 years ago, # ^ |   0 very intuitive? was it sarcasm or you find it that way. lol
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 If you want the intuition, here it is. Let us say i is the outermost loop, j is inside i and k is inside j. So we will minimize the distance between j and k and how will we ensure that it is the minimum, by considering all possible paths where we go from node j to k via all possible intermediate nodes. If there was a direct connection which was the optimal path then it simply wont change because of the fact that it is the minimum. Refer to PrinceOfPersia's blog on graphs for refernce.
 » 2 years ago, # | ← Rev. 3 →   +13 Simple solution for D using stack: 59187274
•  » » 2 years ago, # ^ |   0 Can you explain your code?
•  » » » 2 years ago, # ^ |   +8 Sure! It's essentially solution 1 described in the tutorial.Let's process the string in order. If we come across a 1, push the current index to a stack. Otherwise, we are at a zero. If the stack is not empty, then there is a 1 before us which has not been popped. In this case, we pop it from the stack. By the rules in the tutorial, a "fixed" string exists iff there exists such a 1 on the stack. Further, as described in the tutorial, we must keep all of the "fixed" strings in the final answer. Therefore, any time we pop a 1 from the stack, we "fix" that index as a 1 in the answer. The optimal answer is the one where everything else is 0.
 » 2 years ago, # |   +3 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 ?
•  » » 2 years ago, # ^ |   0 i dont understand why 1-4 is not a good subsequence, could you help me with that? what's wrong with passing through 1−3−4
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 1-3-4 is not a good subsequence in Test 1 because there is a direct edge from 1 to 3, so the shortest way to go from 1 to 3 does not passes through 2, which would make the given sequence P i.e 1 2 3 4, not good because the shortest path is not passing through 2 if 1-3-4 is considered good. Hence 1-3-4 is not a good subsequence.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 oww ok so basicly we only removing numbers from P that obviously will be passed even we didnt mention it.... thank you
•  » » 2 years ago, # ^ |   0 lazyneuron does this approach would also work?
•  » » » 2 years ago, # ^ |   0 His solution has been hacked, so no.
•  » » 2 years ago, # ^ | ← Rev. 4 →   +1 Your code fails on this test case.4010000100001000041 2 3 4 The expected answer is of length 2, but your code outputs a sequence of length 3.
•  » » » 2 years ago, # ^ |   +1 Thanks
•  » » 2 years ago, # ^ |   0 afterwards，can your approach pass all the test? my approach same as yours，but i didnot write ....
•  » » 2 years ago, # ^ |   0 5 01010 00100 00010 00001 00000 5 1 2 3 4 5 We need to check for all i's>curr(whether edge exists between p[i] and p[curr].
 » 2 years ago, # |   +21 What happened to the tags of problem C? BTW, I think dp should be added as a tag too.
 » 2 years ago, # |   0 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?
•  » » 2 years ago, # ^ |   +4 Solution 2 , but recount the LIS of the whole string manually in linear time
 » 2 years ago, # | ← Rev. 2 →   0 111 2 1 2 1 2 1 2 1 2 4problem 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 ?
•  » » 2 years ago, # ^ |   0 There is an arc from 3 to 1
 » 2 years ago, # |   +1 I solved C with DP,it took O(n×m).
•  » » 2 years ago, # ^ |   0 What was your approach for it?
•  » » » 2 years ago, # ^ |   +3
 » 2 years ago, # |   +1 I have seen problem C somewhere before on Codeforces. Can't remember in which contest? Can somebody tell me?
 » 2 years ago, # |   0 Does anyone have a java solution in O(n^3 + m) because my solution TLEs on case 13.
•  » » 2 years ago, # ^ |   +9 Spoilerimport java.io.*; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.StringTokenizer; public class RoundC implements Runnable { private static final int INF = (int) 1e9; private void solve() throws IOException { final int n = readInt(); int[][] dist = new int[n][n]; for (int i = 0; i < n; i++) { Arrays.fill(dist[i], INF); dist[i][i] = 0; String s = readString(); for (int j = 0; j < n; j++) { if (s.charAt(j) == '1') { dist[i][j] = 1; } } } for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]); } } } final int m = readInt(); int[] p = new int[m]; for (int i = 0; i < m; i++) { p[i] = readInt() - 1; } List ans = new ArrayList<>(); ans.add(p[0]); for (int i = 1; i < m; i++) { final int prev = ans.get(ans.size() - 1); int j = i; while (j + 1 < m && dist[prev][p[j]] + 1 == dist[prev][p[j + 1]]) { j++; } ans.add(p[j]); i = j; } if (ans.get(ans.size() - 1) != p[m - 1]) { throw new AssertionError(); } out.println(ans.size()); for (int x : ans) { out.print(x + 1); out.print(' '); } out.println(); } /////////////////////////////////////////////////////////////////////////////////////////////////////////////////// public static void main(String[] args) { new Thread(null, new RoundC(), "", 128 * (1L << 20)).start(); } private static final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null; private BufferedReader reader; private StringTokenizer tokenizer; private PrintWriter out; @Override public void run() { try { if (ONLINE_JUDGE || !new File("input.txt").exists()) { reader = new BufferedReader(new InputStreamReader(System.in)); out = new PrintWriter(System.out); } else { reader = new BufferedReader(new FileReader("input.txt")); out = new PrintWriter("output.txt"); } solve(); } catch (IOException e) { throw new RuntimeException(e); } finally { try { reader.close(); } catch (IOException e) { // nothing } out.close(); } } private String readString() throws IOException { while (tokenizer == null || !tokenizer.hasMoreTokens()) { tokenizer = new StringTokenizer(reader.readLine()); } return tokenizer.nextToken(); } @SuppressWarnings("unused") private int readInt() throws IOException { return Integer.parseInt(readString()); } @SuppressWarnings("unused") private long readLong() throws IOException { return Long.parseLong(readString()); } @SuppressWarnings("unused") private double readDouble() throws IOException { return Double.parseDouble(readString()); } } 
•  » » » 2 years ago, # ^ |   0 Well that sucks, looks like I drastically underestimated the power of PrintWriter vs System.out.print. I'll be sure to keep that in mind going forward. Thanks!
 » 2 years ago, # |   0 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
 » 2 years ago, # |   +1 I am not getting approach for problem D. Can anyone pls explain why for input 111000 Output is 111000 And not 001000
•  » » 2 years ago, # ^ |   0 LIS for 001000 is 00 1 000 and it's length is 5While for 111000 its either 111 000 or 111 000 and its length is 3.(Bold part is LIS)
•  » » » 2 years ago, # ^ |   0 I got it. Thanks
 » 2 years ago, # |   +3 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
»
2 years ago, # |
Rev. 3   0

### 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 ?

•  » » 2 years ago, # ^ |   +13 i can
•  » » 2 years ago, # ^ |   0 We can use two pointer method to iterate over the path and delete as much as we can
 » 2 years ago, # |   0 Can someone please explain the approach for the first problem in detail i didn't get it, thanks in advance. <3
 » 2 years ago, # | ← Rev. 2 →   0 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$.
•  » » 2 years ago, # ^ |   0 But the shortest paths of "3,3" is "3,1,3".You can't go through the points from themselves to themselves.There is no a edge from "3" to "3".
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 Output for the task is not path in graph, it's only subsequence of given path. Because $3, 3$ is subsequence of $3, 1, 3$ and one of the shortest paths passing through $3, 3$ is $3, 1, 3$, so $1, 2, 3, 3, 2, 1$ might be answer for third example.
•  » » » » 2 years ago, # ^ |   +6 This made me confuse also. If you read the output description, it says that continuous vertices of the answer should be different. It's weird because the statement asks for shortest answer first but not asking for this condition
•  » » » » » 2 years ago, # ^ |   +8 my common sense said that if you want to go from 3 to 3 then you may just not to move
•  » » » » » » 2 years ago, # ^ |   0 Oh man. My bad. I thought the loop of a vertex should be the shortest path between it and itself
•  » » » » » » » 2 years ago, # ^ |   0 Yeah, me to
•  » » » » » » » 2 years ago, # ^ |   +2 sorry for not pointing at it in the statements. i hope you liked other problems
•  » » » » » » » » 2 years ago, # ^ |   0 Don't worry, About 2000 people solved it so it wasnt a big problem.
•  » » » » 2 years ago, # ^ |   0 sorry for not pointing at it in the statement, but i think that the shortest path going through 3,3 is a single 3 without any moving even there are not any loops. sorry once again, i hope you liked other problems
•  » » » 2 years ago, # ^ |   0 the shortest path of 3,3 is just a single 3. sorry for not pointing at it in the statement
•  » » » » 2 years ago, # ^ |   +8 That's how skipping the main character's name could accidentally skips the common sense of the problem.
 » 2 years ago, # |   +75 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: (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) (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
•  » » 2 years ago, # ^ |   0 Sorry, but Can you explain two cases more clearly ? I'm quite confused when reading to that ! Thank you so much.
•  » » » 2 years ago, # ^ |   0 Case 1: (n, m) is below or on the line, coz y=x-k is above (0, 0), so (n. m) and (0, 0) lies on different sides of the line, any path that connects these two points must intersect y=x-k. Case 2: (n, m) is above the line. Then we reflect the (n, m) with regard to y=x-k, it becomes (m+k, n-k), and it's below the line. After we draw a path between (0, 0) to (m+k, n-k), we find the first intersection point between the path and y=x-k, call it q. Then we reflect the path between q and (m+k, n-k), the end point becomes (n, m) again and the path intersects y=x-k.
 » 2 years ago, # |   0 For the A problem.I want to ask a simple question.The largest upper limit 2^100 we should input is decimalism or binary?
•  » » 2 years ago, # ^ |   0 You should use string.
•  » » » 2 years ago, # ^ |   0 emm..I know,I have used string to solve the problem.so the 'S' is in base decimalism?
 » 2 years ago, # | ← Rev. 8 →   +10 [delete]
•  » » 2 years ago, # ^ |   +1 Can you please explain your solution?
•  » » » 2 years ago, # ^ |   0 Sorry, I made a mistake,fixed now!
•  » » » 2 years ago, # ^ |   0 Do you understand now?
•  » » » » 2 years ago, # ^ |   0 no :(
•  » » » » » 2 years ago, # ^ |   +1 Sorry,I personally feel that my own ideas are too unclear.Let me think for a while.....
•  » » » » » 2 years ago, # ^ |   0 Maybe I'm too sleepy when solving this problem during the contest using my another handle.
•  » » » » » 2 years ago, # ^ |   0 Do you understand now?After correcting a lot of mistakes.....
•  » » » » » » 2 years ago, # ^ |   0 No, I found the editorial more understandable :/
 » 2 years ago, # |   0 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: 59165015AC with C++: 59196569What is the subtle difference between C and C++? I am really puzzled :(
 » 2 years ago, # |   0 for C i think the systests is too weak, many wrong program can passed all tests for example only one path
 » 2 years ago, # |   +2 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
•  » » 2 years ago, # ^ |   0 yes, sorry, there was a typo
 » 2 years ago, # |   0 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.
•  » » 2 years ago, # ^ |   0 You need to find the number of trains departed strictly before time s. That's why the value to be considered is 15, not 16.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 ok let s=1111 which is 15, here length is 4, then according to the given solution answer is either (length-1)/2 or length/2, it means the answer is 2 but the correct answer is 3.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 it should be +1 not -1, i think its a typo, +1 if there's a 1's before the leftmost bit
 » 2 years ago, # |   0 In the problem 1204A,how does the author conclude "Basically, the problem asks you to count ⌈log4s⌉". Can someone clarify?
•  » » 2 years ago, # ^ |   0 By definiton $\lceil \log_4 s \rceil$ is the number of distinct powers of 4 strictly lesser than $s$ with nonnegative integer exponents $4^0, 4^1, 4^2$ and so on.Problem A asks you to count the number of trains which arrive before given time. Time is represented as a binary number $s$ and $i$-th train arrives on $4^i$-th moment, so every power of 4 strictly lesser than $s$ corresponds to exactly one missed train and every missed train corresponds to exactly one power of 4 strictly lesser than $s$, so by counting all powers of 4 strictly lesser than $s$, you equivalently count all trains, that arrive before time $s$.
•  » » » 21 month(s) ago, # ^ |   0 Thank you for shedding more clarity!
 » 2 years ago, # | ← Rev. 2 →   +2 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.
•  » » 2 years ago, # ^ |   0 Almost the same question has already been asked and there are some answers to it: https://codeforces.com/blog/entry/69244?#comment-536761 . If you don't understand the first solution, maybe this discussion will help: https://codeforces.com/blog/entry/69244?#comment-536965 but I think this observation is probably better for understanding the first solution: https://codeforces.com/blog/entry/69244?#comment-536750 .
 » 2 years ago, # |   0 i am not getting the rules of problem D: in test case 4: 0111001100111011101000 why is the output 0011001100001011101000 and not 0001000100001000101000?
•  » » 2 years ago, # ^ |   0 in test case first four symbols 1100 (length of good subsequense — 2) in your solution there is a 0001 (length of good subsequense — 3)
•  » » » 2 years ago, # ^ |   0 oh okay thank you but why did you skip the first 2 0s in there solution 0011001100001011101000 but did not skip them in my answer 0001000100001000101000 aren't we supposed to compare both using same left and right?
•  » » » » 2 years ago, # ^ |   0 Yes, Seville got it wrong. It should be 0100 instead of 0001 as the substring from your solution. But also, we are comparing the test case input with your solution, not the test case output with your solution, which is what seems you have just done.
 » 2 years ago, # |   0 Can someone please explain what do in problem C after obtaining the shortest path matrix using Floyd-Warshall?
•  » » 2 years ago, # ^ | ← Rev. 5 →   0 firstly — last_vertex = P[0]how to check if we can add vertex P[U] to answer?if distance between P[U] and last vertex in path == distance in graph (which getted by floyd) we can see next vertex (U++)So, when it become false -> it means we need add P[U — 1] in answer because there is a last good vertex. now last vertex = P[U — 1], and we can check vertexes, while there are vertexes.
 » 2 years ago, # | ← Rev. 2 →   +3 In the solution for D could someone please prove the last three "obvious" observations? I.e.: if a string p is fixed, then the string 1p0 is fixed; each fixed string contains the same number of ones and zeroes; 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?
•  » » 2 years ago, # ^ | ← Rev. 4 →   0 Let the string "1p0" be not fixed. Then there is a string "s" that matches the first condition of the statement. Obviously the string "s" looks like this ?p?, because otherwise the string "p" is not fixed. But the first character of the string "s" cannot be 0 as well as the last character cannot be 1, because otherwise length of the longest nondecreasing sequence of the whole string will be different. Now consider all the strings formed in this way. They meet this condition "each fixed string contains the same number of ones and zeroes". Note that these strings can be compared with the correct bracket sequences. Here we need to take first a few closing brackets (x) and then a few opening (y). But each of these brackets has a pair, so x + x + y + y <= n, x + y <= n / 2. If you delete all the lines obtained in this way, then a few 0 will remain, and then a few 1, because after 1 only 1 can go. We can replace all the remaining 1 with 0, since: 1) a fixed line is a correct bracket sequence, therefore the number of 1 on the prefix is ​​greater (or equal) than 0, and vice versa on the suffix. 2) as the largest non-decreasing sequence of the entire fixed row, you can choose all 0 or all 1. The remaining 1 cannot be replaced since they are part of a fixed substring.
•  » » » 2 years ago, # ^ |   +1 But if a longest non-decreasing subsequence of "1p0" consists of only 1s and there are more 1s than 0s in "1p0", then the length of a longest non-decreasing subsequence of "0p0" is the same as of "1p0". Analogically, I don't see why the last character of "s" cannot be 1. OK, strings formed in this way meet this condition. But how do we know that ALL fixed strings meet this condition?
•  » » » » 2 years ago, # ^ |   +1 To solve the problem, it is enough for us to delete only the lines formed in this way. It's possible that these are not all fixed strings.
•  » » » » » 2 years ago, # ^ |   0 Yeah, I think the solution should say that we define recursively a family of fixed strings, which could be viewed as all the correct bracketings, and make some observations about this family. Then at the end I think we could note that these are in fact all the fixed strings because for any string that is not in this family we could remove all strings from this family from it and obtain something where we can change something.
 » 2 years ago, # | ← Rev. 2 →   0 In C, why we are not checking the vertices in same path length. Like for the test-case: 4010100100000001031 2 3 Output: 21 3According 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 31 2 3 Correct me, if I'm understanding this problem wrong?
•  » » 2 years ago, # ^ |   0 Because $p$ is one of the shortest paths, not only shortest path.
•  » » » 2 years ago, # ^ |   +3 Oh, sorry. Got it. Thanks.
 » 2 years ago, # |   0 " 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.
 » 2 years ago, # |   0 rotavirus Can you share your code for Problem D2 Solution 2 ?
 » 2 years ago, # |   +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 ..." ?
•  » » 2 years ago, # ^ |   +5 why did you need to register a new account to say it to me
•  » » » 2 years ago, # ^ |   0 Because I wasn't sure if it is me who didn't understand well your explanations or it was actually you who made a mistake in the explanation :) sorry for that !
 » 2 years ago, # |   0 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.....
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 basicly we only removing numbers from P that obviously will be passed even we didnt mention it, at the frist example the path is 1 2 3 4, if our answer is 1 4 we will missed vertex 2 bcs the route that we take would be 1 3 4 (we need to visit every vertex on the given path on exact same order). so if our answer is 1 2 4 ( we walk from 1 to 2, then from vertex 2 we only have 1 way to go and that is 3, so we dont have to include 3 on our answer, at vertex 3 we continue going to vertex 4 (because of the path said so)). :D
•  » » » 2 years ago, # ^ |   0 thanks for your reply.I have read the problem carefully ago,now I have already know what the problem means,the given sequence A is a shortest path in some "good" sequence,you have to find a sequence B when visit all the elements of the B,the given sequence A will be the shortest path,after using floyd algorithm,you can get correct answer by greedy algorithm.
 » 2 years ago, # |   0 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.
•  » » 2 years ago, # ^ |   0 s=0111001100111011101000t=0001000100001000101000l=3,r=6s[3:6] is 1100, its longest nondecreasing subsequence is 11 or 00t[3:6] is 0100, its longest nondecreasing subsequence is 000
•  » » » 2 years ago, # ^ |   0 Oh sorry.! I misunderstood the question. I thought that the non-decreasing series should be a continuous one. Thank you.
 » 2 years ago, # |   0 BFS is actually enough to solve problem C......
 » 2 years ago, # |   0 I have a doubt in D. I used this algorithm: In a set I store all positions in the binary string where 1 is followed by 0. (Meaning the non-decreasing sequence breaks). I keep the 1 at that place and the rest positions I fill with zeroes. Where is the fallacy in this?
 » 2 years ago, # |   0 1204C - Anna, Svyatoslav and Maps My answer to this problem to test case -301110111071 2 3 1 3 2 1is coming as — 51 3 1 2 1I can't understand where it is wrong.?
•  » » 2 years ago, # ^ |   0 All vertices has two-side relation.from 1 to 3 shortest path = 1 (from 1 to 3 directly), and you can't remove 2 from 1-2-3, because you can only delete when 1-x-3 shortest path from 1 to 3.
 » 2 years ago, # |   0 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?
•  » » 2 years ago, # ^ |   0 It's all about subsequences
 » 2 years ago, # | ← Rev. 2 →   0 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.
 » 2 years ago, # |   0 Questions to D2. Why is it true if p and q are fixed, pq also should be fixed?
 » 2 years ago, # |   0 It's difficult to understand the tutorial of DIV2C problem. Please someone help.
 » 2 years ago, # |   0 In problem C description it says the graph is directed unweighted without loops but in sample test 3 3 011 101 110doesnt this refers to graph image link which is a graph with loop
•  » » 2 years ago, # ^ |   0 i call this a cycle
•  » » » 2 years ago, # ^ |   0 Thanks, completely get it
 » 2 years ago, # |   0 due to the binary string, we can calculate LIS in linear time.You can look my submission
 » 2 years ago, # | ← Rev. 3 →   0 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); } } 
 » 2 years ago, # |   0 Could someone give me the code of the first solution for problem D2?
 » 2 years ago, # |   0 How can I get obivous like D? I've saw some problems, but I never solved a problem.
 » 2 years ago, # |   0 For problem D, if i follow the given tutorial, im getting 0011001100001000101000 for 4th test case 0111001100111011101000...But the answer is 0011001100001011101000... I'm first initialising a resulting string to zero for all index,then I'm finding all the fixed string and putting that fixed string into their respective index in the resulting string.. my code::https://codeforces.com/contest/1204/submission/59356798
 » 2 years ago, # |   +3 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?
 » 2 years ago, # |   0 For the 1204B - Mislove Has Lost an Array problem, I've gone through the tutorial. But can anyone tell how should I approach for such kind of solution during the contest?
 » 2 years ago, # |   0 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.
 » 2 years ago, # |   0 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
•  » » 2 years ago, # ^ |   0 your bfs is wrong
•  » » » 2 years ago, # ^ |   0 That was a terrible mistake . Thanks for pointing out _/_
 » 23 months ago, # |   0 In tast D last example is "0111001100111011101000" and the output is "0011001100001011101000", but wouldn't the correct answer be "0001000100001000101000" ?
 » 19 months ago, # |   0 In A: can anyone plz explain how log2(s)==(l-1)/2 or l/2? what's the logic here?
 » 17 months ago, # |   0 Problem C is exactly same as SECRETMI from codechef
 » 16 months ago, # | ← Rev. 3 →   0 deleted