Recent actions
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 17 hours ago Created or updated the text
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 17 hours ago 0 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 17 hours ago 0 thank you very much!
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 17 hours ago +13 If you use tmp.erase(x), it will remove all the elements with value "x" from the multiset. You have to remove this "if", because of the following case:  if (ans[ans.size() - 1] < ans[ans.size() - 2]) { tmp.erase(l[i].second); tmp.insert(a); mus += a; mus -= l[i].second; } Case: 4 2 7000 5 1 5 8000 2 70000 1 https://codeforces.com/contest/1140/submission/51766475
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 18 hours ago 0 Hello!Can anybody expalin why my sol for problem C fails?Seems like it must work.Thanks! https://codeforces.com/contest/1140/submission/51763978
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 19 hours ago +3 When the editorial will be published?
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 19 hours ago 0 problem c was very nice,thanks for the problem author!!!
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 20 hours ago +3 Now it's Makki0UPD:
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 20 hours ago +4
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 20 hours ago 0 Let's create a graph with $n + 1$ vertices. $i$-th vertex will represent an edge between vertices $2i - 1$ and $2i$, and in the end, we want the distance from vertex $0$ to vertex $i$ be equal to the length of the shortest path between $2i - 1$ and $2i$.How can we find the shortest path between $2i - 1$ and $2i$? We either pick the edge between them, or go to some other neighbor of $2i - 1$ (let it be $2j - 1$), take the shortest path between $2j - 1$ and $2j$, and take the edge from $2j$ to $2i$.So, we need to create the following edges in our graph: $n$ edges going from $0$ to $i$ and having weight equal to $w_{2i - 1, 2i}$ in the original graph, and for every pair of odd neighbors $2i - 1$ and $2j - 1$ an edge going from $i$ to $j$ and having weight $w_{2i - 1, 2j - 1} + w_{2i, 2j}$.All that's left is to run Dijkstra from vertex $0$ in this graph, and that's how we get preprocessed weights.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 21 hour(s) ago 0 How can we made this part "To handle this, let's preprocess all edges of the second type in such a way that cost of each such edge will be equal to the shortest path between its endpoints. This can be done with a Dijkstra-like algorithm." ?
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 21 hour(s) ago 0 It’s unfortunate because I would’ve been stuck in a DP type solution if I wasn’t thrown off by the fact that many people were solving it within s few minutes, so I realized it must be some type of greedy solution. If it was a contest with a frozen scoreboard I think a lot fewer people would have solved it.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 21 hour(s) ago +12 Please, someone should steal bigbigbigbigbigbigbigbigbigcat111 to stop this unethical behavior!
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 21 hour(s) ago 0 Lmao, felt the same D:
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 21 hour(s) ago 0 Awesome, thank you!!
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 22 hours ago +1 Sure. dp[i][0] is the number of constructions for the first i elements such that the i’th element is not the same as v.back, and dp[i][1] is the number such that it IS equal to v.back.That is the base case, so if the first element is equal to the last, dp[0][0] will be 0 and dp[0][1] will be 1, and vice versa if they are not equal.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 22 hours ago 0 It's amazing. I have understood the algorithm and the code!))
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 23 hours ago 0 Thanks for the solution！
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 23 hours ago 0 I have a doubt , why don't we take k longest processed so far and do the all think you explained?
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 23 hours ago -6 System Testing ended.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 23 hours ago 0 It has started.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 23 hours ago +15 Firstly, suppose a vertex exists during $[2, 9]$. Then you can split the interval similarly to range query in segment tree, i.e. $[2, 9] \rightarrow [2, 3] + [4, 7] + [8, 9]$ (it may vary due to different implenmentations of segment tree/divide-and-conquer).Call the following function recursively. f(left, right): Add vertices with interval [left, right] and record every changes if left = right Output the current answer else mid := (left + right) / 2 f(left, mid) f(mid + 1, right) Undo the stored changes It is easy to see that: each answer is printed in correct order all vertices have the correct state (existing or not) when each answer is printed there are almost $\text{O}(n \log n)$ operations of adding vertices consequently, there are almost $\text{O}(n \log n)$ undo operations
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 24 hours ago +3 I can't believe people are upvoting this. Why would dotorya make a fake account and then compete with both of them in the same contest submitting same solutions? I don't think a legendary grandmaster would be that stupid. It must be a hacker's account, should be banned soon.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 24 hours ago +11 Why is system testing is so late?
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 24 hours ago 0 Probably after the System Testing gets completed I guess
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 24 hours ago 0 What about the System Testing, when it's going to start?
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 24 hours ago +2 What happened to cat111?
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 24 hours ago +13 Let's divide all edges into two types: edges of the first type connect vertices having different remainders modulo $2$, and edges of the second type connect vertices having same remainders.First of all, let's solve an easier version of the problem: we have to minimize the number of edges of the second type in our path, and minimizing the length of the path has lower priority. Then we can build one tree where each vertex is a union of vertices $2x + 1$ and $2x + 2$ in the original graph, and use something like binary lifting or centroid decomposition on this tree. For example, if applying binary lifting, we may maintain an array $up[N][LOGN][2][2]$, where $up[v][k][f1][f2]$ is the length of the shortest path that starts in vertex $2v + f1$ of the original graph, goes $2^k$ steps up the tree, and ends in the vertex having remainder $f2$ modulo $2$ in the original graph.Okay, but we can't use this approach in the problem from the contest, because sometimes it is better to traverse some additional edges of the second type, so we may choose cheaper edges of the first type. To handle this, let's preprocess all edges of the second type in such a way that cost of each such edge will be equal to the shortest path between its endpoints. This can be done with a Dijkstra-like algorithm.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 24 hours ago 0 When will the editorial come out?
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 24 hours ago 0 Probably there's alot of cheaters in this round that's why the system hasn't started testing.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 24 hours ago 0 ...Why hasn't it been rated yet?I've been waiting for a long time.Just be a little faster,OK?Thanks!
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 24 hours ago 0 Just like teja349 has written, I get rid of erase operations by applying divide-and-conquer on time axis (just like in classic Dynamic Connectivity Offline problem).
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 24 hours ago +1 Please do not refresh the ratings... I'm sad enough...
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 24 hours ago +1 Yes even I felt doomed
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 25 hours ago +16 Waiting for hours I've been. Painful it is.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 25 hours ago +88 It is really disappointing that some 2100+ rated players make fake accounts before the contest in order to participate officially. For example take a look at this account: bigbigbigbigcat111 This account was made just before the contest and ranked 30. I think this account was made by bigbigbigcat111 who is unable to participate officially because his rating is above 2100. Making fake accounts and stealing rating from other participants is unacceptable. Please remove him from the list of official participants. Upd: I noticed that he has account: bigbigcat111 and bigcat111 as well. All accounts are from China and they have similar rating.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 25 hours ago +9 I think system testing is still due
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 25 hours ago 0 Can you give more explanations? It's hard for me to understand your code))
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 25 hours ago 0 PLEASE UPDATE THE RATINGS!
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 26 hours ago 0 Why not charge in the rating?
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 26 hours ago 0 LOL XD I also missed it. Thanks bro
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 26 hours ago 0 Have refeshed my page hundreds of times.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 26 hours ago 0 From nishank.suresh You're allowed to remove characters only before you start performing operations on the string, so you can't reduce it first and then remove.It's even in boldface lol. Can't believe I missed that.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 26 hours ago 0 Ahh! Now it makes sense!! Thanks a lot!
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 26 hours ago -15 PLEASE UPDATE THE RATINGS !!!
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 26 hours ago -6 Please update the rating!
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 26 hours ago +15 Please update the rating.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 26 hours ago +26 Please update the rating.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 26 hours ago 0 You're allowed to remove characters only before you start performing operations on the string, so you can't reduce it first and then remove.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 26 hours ago +20 May be you are not dotorya and still personating him after hacking his account lol
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 27 hours ago 0 could you please explain this part of your code for problem E ... if(v[0] == back) { dp[0][0] = 0; dp[0][1] = 1; } else { dp[0][0] = 1; dp[0][1] = 0; }
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 27 hours ago 0 I think this is for incremental version. For dynamic version you have use the idea of dynamic connectivity combined with this.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 27 hours ago +3 When selecting a song, the total length and minimum beauty matters. So let's sort the songs by decreasing beauty, and process them like that. To make sure we have maximum length, we keep a multiset of the k-1 longest songs processed so far. Let's process song i. We do ans = max(ans, max_total_length*beauty[i]. If the multiset has size less than k-1, add this song's length to it and increase max_total_length. Otherwise, if this song's length is greater than the shortest length in the multiset, remove that length, subtract it from max_total_length, and add the current like previously.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 27 hours ago +4 Let $x = [(\text{beauty}_{k_{1}}, \text{length}_{k_{1}}), (\text{beauty}_{k_{2}}, \text{length}_{k_{2}}), ...]$ This array is sorted by beauty.Then if you pick $(\text{beauty}_{k_{i}}, \text{length}_{k_{i}})$ as minimum beautiful song, then you must pick up to $k-1$ songs from $[x_{i+1}, x_{i+2}, ..., x_{n}]$. You can use std::multiset or something to pick $k-1$ most longest songs.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 27 hours ago +8 I have the following observation but I didn't solved it.Consider vertex $(x, y)$ as an edge connecting $a_x$ and $b_y$. Then the answer is the sum of (number of $a_i$ $\times$ number of $b_j$) in each connected component. If we can maintain the connectivity supporting deletion efficiently, the original problem can be solved.Edit: I upsolved it by doing divide-and-conquer on time axis. Distribute the lifetime of each vertex to $\text{O}(\log n)$ time intervals. Then traverse the segment-tree-like structure with disjoint set union operations and restore operations.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 27 hours ago +3 [copied from above, since this thread seems to have more activity] How's the answer for <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> [2nd test case, 5th one] 50? I could choose the last < repeatedly until all characters before it are deleted, then choose the first > repeatedly until all characters after it are deleted. If you do that, the answer is 1. The problem statement doesn't place a restriction on the number of times you can choose a character, it only specifies that it must exist in the string. If repeated choices are not allowed, then how does >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> evaluate to 0?
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 27 hours ago 0 Can someone explain their approach in solving C, I dont know why I got hold of a very wrong track in solving it, and finally it became a mess.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 27 hours ago 0 How do you erase?
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 27 hours ago 0 Got it, thanks!
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 27 hours ago 0 I agree, It was trivial. I proved this after the contest was over. Always triangulating from vertex 1, works.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 28 hours ago 0 Got it. Thanks!
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 28 hours ago +6 For <<>> if i choose 2nd character('<') then the string will become <>> as choosing < will delete its preceding character. Now i can choose the first occurence of '>' which will delete the last character. The string becomes <>. Now delete any one of the characters will make it a good string. So there's only one deletion. How the ans is 2 and not 1? Please correct me if I am wrong
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 28 hours ago +32 please update the ratings.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 28 hours ago 0 What's the approach for F?
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 28 hours ago +1 Yes exactly, you would just pick the greatest $k$ lengths such that the beauty is greater than or equal to the minimum beauty.If you sort the songs according to beauty, then you can preprocess these $k$ lengths as juckter said below using a heap, and then iterate over all the possible minimum beauties and take the maximum answer.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 28 hours ago 0 Well, it's not that they must all be unique, it's that they must not have consecutive elements that are equal.For example, the array [1, 2, 2, 1, 1] is good, even though your approach would say it is not.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 29 hours ago 0 Example and Note are very useful to understand the problems.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 29 hours ago 0 My approach was all the elements at odd indexes must be unique and same for even indexes, what's wrong with this approach?
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 29 hours ago +28 Please update ratings :3
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 29 hours ago 0 made the same mistake :(
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 29 hours ago 0 It's not my account, and I think that my account was hacked. (Password leak or something) Now I changed my password, and hope it won't happen again.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 30 hours ago 0 Same with the first one...UPD: But the problems were great! :)
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 30 hours ago +26 Actually you can solve problem D in O(1) time complexity.Let S = 2 * 3 + 3 * 4 + ... + (n-1) * n3S = 2 * 3 * (4-1) + 3 * 4 * (5-2) + ... + (n-1) * n * (n+1-(n-2))3S = 2 * 3 * 4-1 * 2 * 3 + 3 * 4 * 5-2 * 3 * 4 + ... + (n-1) * n * (n + 1)-(n-2) * (n-1) * n3S = (n-1) * n * (n + 1)-6S = ((n-1) * n * (n + 1)-6) / 3P/s: I don't know how to use Latex :( So the signs and numbers may be ugly
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 31 hour(s) ago -8 Second problem ruined the whole contest for me. The problem statement must be properly written.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 31 hour(s) ago +7 How's the answer for <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> [2nd test case, 5th one] 50? I could choose the last < repeatedly until all characters before it are deleted, then choose the first > repeatedly until all characters after it are deleted. If you do that, the answer is 1. The problem statement doesn't place a restriction on the number of times you can choose a character, it only specifies that it must exist in the string. If repeated choices are not allowed, then how does >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> evaluate to 0?
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 31 hour(s) ago +1 if The CF-Predictor broken ? ( Chrome Browser)=> Use this Website=> About the Issue
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 31 hour(s) ago 0 This is beautiful.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 32 hours ago 0 Any hint for G?
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 33 hours ago 0 I thought the answer could be only "1" or "0",and it took me a while to understand the meaning of Before applying the operations in problem B. ;P
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 33 hours ago 0 Probably not since you would have (3*10^5)^2 states
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 33 hours ago +4 This comes in somewhat late, but I haven't seen a full proof in the comments yet.Let the value of a segment be the product of its endpoint. Then clearly the value of a triange is greater than or equal to the value of any of its sides. Moreover, unless one of the vertices is $1$, the value of the triangle is greater than or equal to the sum of any two sides. This is because $abc - ab - ac$ factors as $a((b - 1)(c - 1) - 1)$ which is non-negative unless $b$ or $c$ is $1$.Now note that every side of the polygon belongs to a triangle in the triangulation. If this triangle contains no other side then its value is at least the value of that side. If it does contain another side then the value of the triangle is greater than or equal to the sum of these two sides, unless one of the vertices is $1$. By adding up it follows that the sum of the values of all the triangles is at least the sum of the values of the sides, except for the two sides that include vertex $1$ (because they may be included in a triangle that has another side of the polygon).Triangulation $(1, 2, 3), (1, 3, 4), (1, 4, 5), \dots, (1, n - 1, n)$ gives exactly that sum of values, so that's our answer. Also note that the exact labels on the vertices don't matter, all that is needed is that exactly one label is equal to $1$.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 35 hours ago +16 How to solve G?
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 36 hours ago +3 it seems i have proved this solution. Suppose there isn't any diagonal from 1 in optimal triangulation. Then we can move this triangulation in clockwise and decrease the cost. So there is some diagonal from 1 to i. Let's consider triangulation of "1 to i" polygon. If there isn't any diagonal from 1 we can do how described above and so on. So, to minimaze the triangulation cost it needs that all diagonals starts in 1.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 36 hours ago 0 I think that the following problem resembles this one ?: link
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 37 hours ago +8 this is also pointed out above, but for some strange reason all the comments are heavily downvotes.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 37 hours ago +14 check this 0ahmad0makki0 is fake account of dotorya. Same solution and also same template.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 37 hours ago 0 Thanks. Got it now :)
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 38 hours ago +2 Assume there is an odd palindrome of length >1. Then the middle 3 characters are a palindrome of length 3.Assume there is a palindrome of length 3. Then obviously there is an odd palindrome.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 38 hours ago 0 Can u please provide some example or proof for your statement "_Note that there are no odd palindrome substrings of length > 1 if and only if there are no palindrome substrings of length 3_".
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 38 hours ago +1 but how can one came to know dotorya password
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 38 hours ago +5 After 4 minutes I went to read and solve B, then I came back to A. I don't know why, but reading the problem later helped me understand it.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 38 hours ago 0 That's true, some of the outer edges can be used together. The triangulation I'm saying is optimal is $(1,2,3), (1,3,4), (1,4,5), ..., (1,n-1,n)$. While intuitive that this is optimal, what I wrote was not a correct argument.
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 39 hours ago 0 don't trust how you understood the problem always read the Note that explain samples ... I did this mistake several times but now I will always read samples note
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 39 hours ago 0 while loop = div2B LMAOC is just a sorting lmao B is just implementation maybe u r right for D and E, but D is harder than div2a
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 39 hours ago +6 You're wrong as always. It was B B C A D
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 39 hours ago 0 The answer will be zero if string_var[0] == '>' or string_var[n-1] == '<' else answer will be min( after_how_much_chars_from_start_appears('>'), after_how_many_chars_from_end_appears('<'))Like for <<<<>>> Answer will be 3, Read the problem statement again and READ what is in BOLD
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 39 hours ago 0 you are right for once, but IMO, they were all easy(A, B, B, B, E)
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 39 hours ago 0 then when will be the answer non zero in which case? so according to you we will always get 0 or 1. but more the 1 values are also there in the output . please explain!!
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 39 hours ago 0 Codeforces Community is Strong. It was a nice contest by the way. Thanks
 On PikMike → Educational Codeforces Round 62 [Rated for Div. 2], 39 hours ago +8 That's not really true. We just greatly underestimated contestants. Personally, I thought that majority will stuck in some sort of dp, so after some discussion we decided to leave a place to a straightforward solution. In the end community surprised me in the good way.PS: linear is not a limit: OEIS/interpolation gives us closed formula and $O(1)$ solution.