### vovuh's blog

By vovuh, history, 20 months ago,

All ideas except the problem C belong to MikeMirzayanov. The author of C is Rox.

Special thanks to _overrated_ for the invaluable help with the round preparation!

1272A - Three Friends

Tutorial
Solution

1272B - Snow Walking Robot

Tutorial
Solution

1272C - Yet Another Broken Keyboard

Tutorial
Solution

1272D - Remove One Element

Tutorial
Solution

1272E - Nearest Opposite Parity

Tutorial
Solution

1272F - Two Bracket Sequences

Tutorial
Solution

• +61

 » 20 months ago, # |   +35 Not hard, but still nice problems with nice solutions.
 » 20 months ago, # |   +22 Missing a '$|$' in the tutorial of 1272A. It should be $|na-nb|+|na-nc|+|nb-nc|$. Thanks for the nice problems and a neat editorial.
•  » » 20 months ago, # ^ |   +21 It's good when your eye doesn't put extra symbols while reading. It would be really helpful when debugging. :))
•  » » 20 months ago, # ^ |   +16 Thank you, fixed.
•  » » » 20 months ago, # ^ |   0 How to solve modified version of D i.e. if we can Remove at most K element. problem_link
•  » » » » 20 months ago, # ^ | ← Rev. 2 →   0 Firstly, try to find the longest increasing subarray without removing any of the element from the array. assign the maximum to variable ans. After that find the length of the longest increasing subarray ending at position i(from 0 to i), and length of the longest decreasing subarray from ending i.e. n-1 position to position i. store the lengths in two seperate arrays dp1,dp2 respectively. Then try to delete elements one by one from i = 1 to n-2 (we won't try deleting element at i = 0 or i = n-1 because it will not increase the length if we did so). If, we delete element at position i then we check if(a[i-1] < a[i+1]) then ans = max(ans,dp1[i-1]+dp2[i+1]) which basically means we are joining the maximum increasing left subarray ending at position i-1 to the maximum increasing right subarray starting at position i+1 subarray. EDIT : I did not read the problem carefully.
•  » » » » » 20 months ago, # ^ |   0 He is asking for the modified version, ie, suppose if we can remove at most K elements.
•  » » » » 20 months ago, # ^ | ← Rev. 2 →   0 Can this solution here be generalised by maintaining k+1 arrays? Solution link Can you look and get something? Trgt_2021_explosion
•  » » » » » 20 months ago, # ^ |   0 During the contest I have solved this problem by exactly same method you have discussed here_mine_one. And you know maintaining k+1 arrays sounds difficult/lengthy if K is of range 1000 or more.Actually I am having an idea just wanted to know others opinion..... My thought(might be wrong/modification might be needed) following with our previous method(I.e. maintain two arrays dp1 and dp2. Here dp1[i] denotes the length of longest subarray(without any deletion) ending at ith index and ith element inclusion is must, and dp2[i] denotes the length of longest subarray ending at ith index with at most k deleted element ith element inclusion is must. In previos case k was 1)Now just create an additional 3rd array say dp3 s.t dp3[i]= no of element deleted till now for dp2[i] result. And by this result we can construct for dp2[i+1] by looking at dp3[i] I.e. if no of deleted element at ith position is less than k then we still can delete otherwise not. I think we can do this by this method. or correct me if something else/extra needed.
 » 20 months ago, # |   +11 I didn't get the idea of why inversing the graph works
•  » » 20 months ago, # ^ | ← Rev. 3 →   +12 Okay, so let us put it this way. Let's consider the normal graph where you can go from an index $i$ to an index $j$. And you add an edge between $i$ and $j$ only if the values at those indices are of same [CORRECTED] parity, right, else you could simply put the answer for index $i$ as 1 and proceed for the other indices. Now we have a graph with out-going edges (from $i$ to $j$ means an out-going edge). It is clear that answer for index $i$ will be one more that the answer for index $j$, as $i$ and $j$ house the same parity elements, and you can go from $i$ to $j$ (if you can also go from $j$ to $i$ that's a different scene, not considering it here).For answer to exist for indices $j$ and $i$, there should be a path from $j$ to some index (maybe through a series of other same parity elements) with the opposite parity as $a[i]$, (this has to hold for a possible solution, i.e. two opposite parity reachable in one step values of array should exist). Say that index is $k$ and it came after traversing a path from $i$ to $j$ to some series of other indices of same parity as $a[i]$. This index $k$ goes to the queue as it is the source for all the elements coming to it. So, if you build the normal graph, that is add edge to k, not from k, during bfs, you won't go anywhere from $k$ (atleast not towards the indices $i$, $j$ and others on path from them to $k$). Hence building the normal graph fails to give a solution. (One may think of using DFS with the normal graph, but DFS doesn't guarantee a shortest path, and dealing with cycles will become very terrible)Thus building the inverted graph ensures that you start from a source (here $k$), and go back to the nodes you used to reach the source (here $k$) SpoilerThink of bfs as the traversal where an edge from $x$ to $y$ means you came to $x$ from $y$.Hope this helps !!
•  » » » 20 months ago, # ^ |   0 Thank you
•  » » » 20 months ago, # ^ |   +4 Or more simply put ; updation of ans[node] happens via dfs only in the back-track move of the dfs.It looks something like : for ( auto to : graph[node] ) { if ( vis[to] == false ) dfs ( to ) ; ans[node] = min ( ans[node] , ans[to] + 1 ) ; } So whatever we do ; we update answer only in the backtrack move of dfs. And if now we need to do something via BFS ( And keeping in mind that BFS is not a recursive algo ) ; its tough even to write a back-track.Hence its better to inverse the graph first ; and then proceed with BFS for the same purpose...This is highly informal way to explaining ; hope it helps biannaib
•  » » » » 20 months ago, # ^ |   +3 Since you're mentioning dfs here, I am curious as to whether it can be solved using dfs or any modification of that? ritesh1340
•  » » » » » 20 months ago, # ^ | ← Rev. 4 →   0 No I don't think that this problem can be solved via dfs ; because dfs is what I tried in the actual contest ; but I failed to receive an AC.Then actually I was confused as to why was I going wrong. By that time the editorial was not out ; so we were discussing the problems on the announcement page.Why I thought of dfs and how I came to know that it will not work can be found HERE. Special thanks to hellomotoAfter hellomoto explained that what is the problem in the logic ; I took several other attempts trying to make something out of dfs only ; however all of them failed...Some of those attempts I can share — My contest submissionMy first attempt after realizing mistakeAttempt 2Attempt 3So after trying enough ; most probably ; I think it can't be solved via dfs ( Or maybe some cool person reads this and suggests some better way on dfs itself ).So then I finally shifted to learn the concept provided in editorial ; and it gave me AC
•  » » » » » » 20 months ago, # ^ |   +3 The main issue with the DFS was that there might be back-edges in the dfs-trees ( or essentially, cycles) and hence the updates would probably be impossible.
•  » » » » » » » 20 months ago, # ^ |   +1 Yes ! And thus in my remaining attempts ; when I understood what was happening ; I tried to re-run dfs on the nodes that were not relaxed ( on nodes for which ( ans[i] = inf ).I had the intution before-hand that there can be many such nodes ; and it was highly probable that such solution could time out ( As it did on test case 12 ) ; but still it was worth a try.
•  » » » » » » 20 months ago, # ^ |   +3 $DFS$ works but will result in a TLE verdict. The problem is, in $DFS$ we may have to update each vertex more than one time (refer to $dp[u]$ in my code). This is not true in $BFS$, since its property is to expand the calculated vertices step by step, each $dp[u]$ is calculated only once and thus achieving $O(n)$ complexity.My DFS submission got TLE on test 19My BFS submission got AC
•  » » » » » » » 20 months ago, # ^ |   0 Yeah... an already relaxed vertex using some dfs can be relaxed more...Hence we will return to the same node more than once...But in BFS ; only one relaxation is enough to update dp[u] ; hence BFS ensures a strict O(n) time ; whereas time of DFS will depend on the structure of the graph ; it will pass a few graphs... but will time out !
•  » » » 20 months ago, # ^ |   +1 Nice explanation. By the way, do you know similar problems where you need to invert the graph to solve it? :)
•  » » » » 20 months ago, # ^ |   +1 Finding strongly connected components in a directed graph :)
•  » » » 19 months ago, # ^ |   +3 Thank you for such a detailed explanation. But I dare to assume there is a mistake: "And you add an edge between i and j only if the values at those indices are of opposite parity, right, else you could simply put the answer for index i as 1 and proceed for the other indices." Should it be "if the values at those indices are of same parity" instead of "opposite"?
•  » » » » 19 months ago, # ^ |   0 Ah right, didn't realize the mistake earlier. Edge will be between indices having same parity elements. FIXED !!
•  » » » 15 months ago, # ^ |   0 Could you please tell where am i going wrong in this question80077469Thanks in advance.
•  » » 19 months ago, # ^ |   +3 Yet another pattern of reasoning for this might be the following one: We do not know what the shortest distances from, e.g. even-to-odd nodes are (we are asked to find them), but we know for sure that the shortest distances from odd nodes to odd nodes are all 0s.Based on that we traverse the graph backwards to get the final answers for even nodes. Repeat the same for odd-to-even nodes. Took me a while to understand this.
 » 20 months ago, # |   +5 In F problem in the tutorial its written that bal can have max length 200 , ok no problem but then in code why have we taken bal as 2*N shouldnt it be just N or say to be on a safe side N+5
•  » » 20 months ago, # ^ |   +3 It can be $N$, I just wrote the solution earlier than editorial and didn't notice that I used $2N$ instead of $N$ in the code.
 » 20 months ago, # |   +6 In problem A answer is just max(|A-B|+|A-C|+|B-C|-4, 0). I don't know why, but it's true.Also problem D could be solved with dynamic programming. Let dp[i][0] be the answer for prefix i, and the element wasn't erased. dp[i][1] — the answer for prefix i, element was erased. Formula is:1) if (a[i-2]=a[i]) dp[i][0]=max(dp[i][0],1LL), dp[i][1]=max(dp[i][1],1LL);
•  » » 20 months ago, # ^ |   +5 Do you mean dp[i][1] is the maximum length of subarray of the prefix until index i, after an element between 0 and i inclusive has been deleted?
•  » » » 20 months ago, # ^ |   0 Yes, but not between 0 and i inclusive, but between 0 and i-1 inclusive.
•  » » » » 20 months ago, # ^ |   0 Ah, I understand the solution now, thanks.
•  » » » » » 15 months ago, # ^ |   0 hey,didnt expect to see you here
•  » » 20 months ago, # ^ | ← Rev. 2 →   +7 For problem a, let's assume that a <= b <= c, so |A-B|+|A-C|+|B-C| is equal to 2 * |A-C|.so we just need to consider the value of |A-C|. If |A-C| <= 2 then you can always move point a, b, c to a same point, temp answer is 0. If |A-C| >= 3 then the minimun temp answer is |A-C|-2.temp answer times 2 is the answer.
•  » » 20 months ago, # ^ |   +5 It is because |A-B|+|B-C|+|C-A| represent twice the length of the line joining the three points on number line. You can think of this problem as trying to shorten the length of the line. Since you can move the endpoints at most 1 unit towards each other, you can at at most shorten the length by 2 units. Now, since the answer asks for twice of length of the new line segment, the answer is basically oldLength — 4, which is equal to |A-B| + |B-C| + |C-A| — 4. But we are missing one case, when the length is less than or equal to 2, we can simply reduce the line to a single point. So the answer simply becomes max(2 * oldLength — 4, 0).
•  » » 20 months ago, # ^ | ← Rev. 3 →   +5 In problem A, assume a<=b<=c, the pairwise sum=(|b-a|+|c-b|+|c-a|). Now since a<=b<=c, we can open the absolute/mod signs, therefore sum=(b-a+c-b+c-a)=2*(c-a). Now we have to minimize 2*(c-a), so we increase a by 1 and decrease c by 1, therefore minimized sum=2*((c-1)-(a+1))=2*(c-a-2). Now we have to handle 2 cases, when (c-a)=1 and c=b=a, in both the case answer will be 0. My submisiion: 66774673
•  » » 20 months ago, # ^ |   0 Wind_Eagle i solved it using iterative approach . But How to solve using recursive dp ?? i've been getting stuck while thinking how many state i've to assume in recursive approach .. Please help . It would be the best if you provide a code of recursive approach . Thanks .
•  » » » 20 months ago, # ^ |   0 I don't know how to solve it using recursive dp, because I used iterative approach, too.
•  » » » 20 months ago, # ^ |   0 Not the most elegant but This was my recursive solution. Pretty sure you don't need the map if you manage the function calls well enough
•  » » 13 months ago, # ^ |   0 why in part 2) dp[i][1]=max(dp[i][1],dp[i-1][1]+1) ? If i am deleting i-1th element then i will not delete any previous oneit should be same as anser for previous one not erased so dp[i][1]=max(dp[i][1],dp[i-1][0]);Help me out.I am getting wa in test 4
 » 20 months ago, # |   +3 I am not able to understand problem F's solution i know dp will be used but still Can somebody please give a well comented solution describing each step , why its done please
•  » » 20 months ago, # ^ | ← Rev. 3 →   0 vovuh please reply to this as well༼ つ ◕_◕ ༽つ
•  » » 20 months ago, # ^ | ← Rev. 2 →   +22 I can try explaining,Let's forget about bracket sequences and just construct a string $A$ that is a supersequence of these two strings $S$ and $T$ ($A$ contains both $S$ and $T$ as a subsequence). This problem can be solved with following DP: compute shortest supersequence for all possible pairs of prefixes $S'$ and $T'$. Instead of storing explicit strings we store lengths of matched prefixes and length of resulting sequence. Let $dp_{i,j}$ be minimum possible length of supersequence for prefix $S'$ with length $i$ and prefix $T$ with length $j$. For empty prefixes empty string matches both $dp_{0,0} = 0$. Suppose we have have calculated $dp_{i,j}$, now we can append new character $c$ to the end of this string, length of the string will be increased by $1$, and size of matched prefixes also can be increased by $1$, it depends whether new character is equal to first unmatched character in strings: $i$ will increase if $S_i = c$ and $j$ will increase if $T_j = c$. This works in $\mathcal{O}(|S| \cdot |T|)$.Now coming to the fact that we have bracket sequences instead of arbitrary strings. Bracket sequences have a concept of balance, I will call it depth. This is actually amount of opened but not yet closed brackets (difference of opened and closed brackets). For some bracket sequence to be correct, balance of any prefix must be non-negative (we cannot put more closing brackets than opening) and must be $0$ at the end (each opening bracket must have a pair of closing one). Sequence properties as a prefixes only depend on it's depth. So we can add one more parameter to our DP, let $dp_{i,j,d}$ be length of shortest correct supersequence for prefix $S'$ with length $i$ and prefix $T$ with length $j$ with depth equal to $d$.So we actually need to store this information about prefixes and be able to continue any prefix with either opening bracket or closing bracket (if it is possible). Generally we say that empty string has depth $0$ and matches empty prefixes: $dp_{0,0,0} = 0$. All other states are not calculated yet. Then we can extend all states with ( and ) possibly getting to new states and updating these states. About order of calculations: each extension increases length of sequence by $1$, and as we are seeking for minimum there is no point trying to update some states that already have a lower value than current state. So we can do this process in BFS-style. Firstly use $0$-result state to find all states that can have result of $1$. Then use all $1$-result states to get all possible $2-$result states, etc. Depth parameter $d$ can be safely capped at $max(|S|, |T|) = 200$, if we just concatenate sequences we can get sequence with depth $|S| + |T|$, but when both strings have large amount of opening (or closing) brackets they will be matched simultaneously.Answer will be stored in $dp_{n,m,0}$. Minimum-length supersequence that has zero bracket depth and completely matches both sequences $S$ and $T$.Also we need to actually restore the answer: for each state we can save last character and another DP state that was preceding for current state (last state that was successfully extended to current one), then restore string one character at a time: add last character to the answer and move to previous state until you get to $dp_{0,0,0}$.So we get $\mathcal{O}(|S| \cdot |T| \cdot \max(|S|, |T|))$Here is my solution 66725721 . All the logics of state extension is incapsulated into state struct. Firstly, it prepares all the DP states to have not-reached-yet status and $dp_{0,0,0}$ to be the starting point and the only state with $0$ result. Then it starts the process, at step $k$ of the process all states with result equal $k$ are extended forming list of states that are $(k+1)$-result states and putting them into next list. When all states are processed target state $dp_{n,m,0}$ must be reached. We can start recovering answer starting at the end and moving to a previous state character by character.Hope it helps.
•  » » » 20 months ago, # ^ |   0 Thanks a lot (∩_∩)
•  » » » 20 months ago, # ^ | ← Rev. 2 →   0 What is S = 228 in your code? And why 228? Also, there are mentions of using BFS in DP, and of backtracking also. Could anyone explain what they are referring to here?
•  » » » » 20 months ago, # ^ |   +1 Constant S is actually shorthand for Size and refers to general size of arrays in solution. So, it is used as three dimensions of $dp$ array. Constant SL stands for SizeLarge and represents amount of waves in BFS-like algorithm.Why exactly $228$ and what is it? I don't think that this number is somewhat specific. I've used this just as a number that is not much greater than $max(|S|, |T|)$. Just added some reserved elements to make sure that I can use some prefix of $\{n, n+1, n+2, \dots\}$ indexes if some of them are needed. Why not usual (at least for me usual) $200+5$? That was chosen at very early stages of solution, when I wasn't sure in all the details. For some non-important reason I've chosen to have more additional elements than usual and $228$ was the first number that come to my mind. Just as $SL = 10 \cdot S$ is much greater than actually needed: $3 \cdot S$ or even $2 \cdot S$ would've been enough. Overall solution turned out to be memory-hungry, so these extra limits put it dangerously close to MLE (480+ MB, but it is easy to optimize if needed). Short story of 228, not related to programming at allArticle 228 of the Criminal Code of the Russian Federation. Illegal acquisition, storage, transportation, manufacture, processing of narcotic drugs, psychotropic substances or their analogues, as well as illegal purchase, storage, transportation of plants containing narcotic drugs or psychotropic substances, or their parts containing narcotic drugs or psychotropic substances.So, it is more or less associated with drugs or similar illegal substances in Russia.BFS part of the solution is loop that starts in line $102$: for (int len = 0; len+1 < SL; len++) { It passes layer by layer forming next layers, where each layer contains all DP states that have result equal to len.Backtracking part comes right after BFS part, starting at line $148$. It starts from position $dp_{n,m,0}$. And uses backtracking information of $dp$ states: state::last state::prev_pa state::prev_pb state::prev_depth These are used to put one bracket into answer and move to previous state that allows to put one last character to the answer and move further backwards.Hope it helps.
 » 20 months ago, # |   0 In the tutorial for problem D, the explanations for array l and r seem to be swapped. li records the max length of increasing sequence ending at i and ri records the max length of increasing sequence starting at i. This way the explanations would be coherent with the code.Otherwise, the final update can be changed into li+1 + ri-1
•  » » 20 months ago, # ^ |   0 Yes, the code and explanation differ. The remove at ith index part needs to be swapped.
 » 20 months ago, # |   +3 Can we do E with DFS? I tried solving it but getting wrong answer 66719636. My approach:- Suppose dp[i][odd/even] represents the distance of odd/even bit from the ith element. Do dfs and update the result.  if(child is even){ dp[parent][even]=1; } else if(dp[child][even]!=INT_MAX) dp[parent][even]=min(dp[parent][even],dp[child][even]+1); if(child is odd){ dp[parent][odd]=1; } else if(dp[child][odd]!=INT_MAX) dp[parent][odd]=min(dp[parent][odd],dp[child][odd]+1); But the problem is with the case when there is loop, like A->B->A. First I go from A to B. Then since I have already visited A, then I try to update my results for B. But since I have not got the final answer for A(as it is still in the stack), my answer for B will be wrong. Can anyone help me how can I overcome this problem??
•  » » 20 months ago, # ^ |   0 I don't think we can do this easily by DFS
 » 20 months ago, # |   -9 My CF predictor was showing +10..But after the hacking in my rank decrease -10... :( Can anyone tell me what is the problem...Is CF predictor is wrong??
 » 20 months ago, # |   +1 My solution over problem 'A' was a bit different. I think it will be proved that the amount we are trying to minimize is being lowered only '4' units for each query and we only need to output max (0 , |a-b| + |b-c| + |a-c| — 4) p.s:This solution passed the test data :)
•  » » 20 months ago, # ^ |   0 I solved it the same way although it took me some time to find it. Thats why I think the best solutions is bruteforce.
 » 20 months ago, # |   0 can someone explain a DP approach to problem D. PLZZ
 » 20 months ago, # |   0 I had a slightly different approach for question D. I had first calculated the array dp[n] where dp[i] holds the longest increasing subarray ending at i. The next thing I did was to find all the endpoints of the blocks of increasing subarrays. One can prove that the answer to the question is the max of the following two cases: 1. The maximum value in dp. 2. The maximum value of dp[endpts[i]]+dp[endpts[i+1]]-1. There are two possibilities in this case,removing the last element of the current block and joining the current block with the next, or doing the same by removing the first element of the next block. Of course we must run the check that the pair of elements crossing the two resultant blocks after removal of an element are still strictly increasing. Submission for reference: Submission #66717570.
•  » » 20 months ago, # ^ |   0 its a nice solution , but i dont think we can call it dp.
 » 20 months ago, # | ← Rev. 3 →   0 An alternative solution for D, using DP, is as follows : Store two arrays subs and subs_rem, indexed with 0. Here subs[i] denotes the length of longest subarray ending at ith index, and subs_rem[i] denotes the length of longest subarray ending at ith index with a deleted element, whose index <= i-1.subs[0] = 1; subs_rem[0] = 0;Also, subs[i] can be calculated easily using dp. For subs_rem[i] do the following: Knowing subs[i], we know the index j from which the longest subsequence ending at i begins.Giving some thought, we realise that the only two elements which can be deleted and the length of sequence would grow, is either jth element or (j-1)th element.Two cases arise: Suppose j-1 and j-2 are both indexes of the array(j-2 >= 0), this means that a[j] <= a[j-1] , where a array is 0 indexed, if a[j] > a[j-2] then we could remove the a[j-1] and then val1 = subs[i]+subs[j-2]; , since we have already deleted a[j-1] element no other element can be deleted. Again suppose j-1 and j+1 are both indexes of the array(j+1 <= i and j-1 >= 0), this means again that a[j] <= a[j-1], if a[j-1] < a[j+1] then we could remove the a[j] element and then val2 = subs[i]-1+subs[j-1]; , since we have already deleted a[j] element no other element can be deleted. Now, subs_rem[i] = max(val1,val2,1); 1 because we could simply delete the a[i-1] element. The final answer is the max of all values of subs array and subs_rem array.My implementation here : 66725589
•  » » 20 months ago, # ^ |   0 And I missed the second case during the contest and hence messed up :(
•  » » » 11 months ago, # ^ |   0 good work
 » 20 months ago, # | ← Rev. 5 →   0 66806946 for D is incorrect, and it's giving me some funny errors (I understand my WA error, but not the uninitiaized value usage on the line 32) Can anyone explain what's going on?
•  » » 20 months ago, # ^ |   0 Declaring arrays outside main function gets rid of the error 66809101
•  » » » 20 months ago, # ^ |   0 Ah, thank you so much!
 » 20 months ago, # |   0 In the writer's solution of F, he/she restores the answer string by the memo when he/she calculated DP table. can I restore the answer string only by its recurrence's transition? For example, dp[i][j] = min(dp[i — 1][j] + x, dp[i][j — 1] + y) is the target. Only using its recurrence's transition means that finding the before situation of dp[i][j] is by checking both dp[i — 1][j] + x == dp[i][j] and dp[i][j — 1] + y == dp[i][j], and decides the correct before situation(satisfied the either equals). If both of them are OK, I can choose any of them. In this way to restore, can I accept problem F?
 » 20 months ago, # |   +1 Can anyone explain problem E??
•  » » 20 months ago, # ^ | ← Rev. 2 →   0 To find the minimum number of moves of opposite parity. We construct a graph(g) in the following manner.g[i] is a vector containing all indexes which reaches to position i in one move only. Now we traverse the graph(for odd and even values separately).For instance, traversing with odd values.First push all the nodes in a queue. Now while traversing the graph if any even value node is encountered. Then the number of moves required = number of moves required by the parent + 1 and then push it into the queue. In this process all the even nodes with moves required 1 is encountered first, then 2,3,4.....Same is done for the even value nodes.For better understanding refer to my solution. link
•  » » » 19 months ago, # ^ |   0 Thanks, got it!
 » 20 months ago, # |   0 Can someone please tell me the issue with my code for PROBLEM C . I used a similar logic but implementation is a bit different from the editorial. Submission : 66825640 It gives a wrong answer for test case 12 ( n = 2*10^5 ) .int main() { #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif int l,k ; cin>>l>>k; string s; cin>>s; map m ; char a= 'a'; for(int j=0;j<26;++j) { m[a] =0; a++; } for(int i=0;i>a; m[a]=1; } ll n=0 ; // max useful substring length ll ans =0; for(int i=0;i
•  » » 13 months ago, # ^ |   0 i got same , 12 th test case failed
•  » » » 13 months ago, # ^ | ← Rev. 2 →   0 java.util.*; // Warning: Printing unwanted or ill-formatted data to output will cause the test cases to fail public class bsol { public static long comb(int pos,int size) { return pos*(size-pos+1); } public static void main(String args[] ) throws Exception { Scanner scan = new Scanner(System.in); int tc = 1; while(tc--!=0){ int n = scan.nextInt(); int k = scan.nextInt(); if(k==26) System.out.println("20000100000");else { char[] s1 = scan.next().toCharArray(); HashSet hm1 = new HashSet<>(); for(int i = 0;i(); int last = 0; int flag = 0; for(int i =0;i
 » 20 months ago, # |   0 For problem A, why the answer (|A-B|+|A-C|+|B-C|-4, 0) is true? How come the solution is this? I dont understand how it's deduced?
 » 20 months ago, # |   0 Is it possible to solve problem E using DP (DP is not there in the problem tags) ?
 » 20 months ago, # |   0 I guess the tutorial for problem D has a mistake. Where it's said "The array l can be calculated in order from right to left ". I think array l should be calculated from left to right and array r vice versa.
•  » » 20 months ago, # ^ |   0 No, it is correct. Think once again. Unless, you see the elements on the right side of the index i, you can't compute l[i] that is why you compute l[i] by traversing the array from the right to the left.
•  » » » 15 months ago, # ^ | ← Rev. 2 →   0 can you explain answer to Problem D?
 » 20 months ago, # |   0 Can anyone explain the working of D.
 » 20 months ago, # |   0 Problem F is very good in the sense that this was the first time i calculated dp using bfs.
 » 20 months ago, # | ← Rev. 3 →   0 I am getting wrong answer in test case 4 in problem D Here is my code, What am i doing wrong?include typedef long long int ll; typedef unsigned long long int ull; define fast ios_base::sync_with_stdio(false);cin.tie(NULL); using namespace std; int main() { fast; // your code goes here ll n; cin>>n; vector v(n); for(ll i=0;i>v[i]; } vector dp(n,0); dp[n-1]=1; if(v[n-2]=0;i--) { dp[i]=(v[i+1]>v[i])?dp[i+1]+1:1; dp[i]=max(dp[i],(v[i+2]>v[i])?dp[i+2]+1:dp[i]); maxi=max(maxi,dp[i]); } cout<
 » 20 months ago, # |   0 In problem D, I have traversed the list and found out the length of the subsequence by removing at most 1 element and at end of the subsequence, started to search for another subsequence from the element which i removed in the previous iteration. Here is the code https://ideone.com/xL5oax. Can someone please help me understand the fault in my logic?
 » 20 months ago, # |   0 In c problem, the time complexity is O(n*k) right???
 » 19 months ago, # |   0 In the problem C — Yet Another Broken KeyboardThe solution is correct but memory limit keeps exceeding. I don't think it should.My Submission
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 The problem is in this part: // Generate substrings for(int i=0; i
•  » » » 19 months ago, # ^ |   0 Thanks for the answer. I solved the question using the approach mentioned in the tutorials. But I didn't knew the reason behind my submission exceeding memory limit. Thanks for explaining.
 » 19 months ago, # |   0 Can anyone provde solution for problem D with dp? :)
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 You can check mine. 81844897 or 81848247 Solved it using two pointer and basic implementation
 » 19 months ago, # |   0 Need dp idea for Problem C.
 » 19 months ago, # |   0 Thanks for a definitive editorial!Minor problem E note: I was confused by a variable name in bfs function: for (auto to : g[v]). Shouldn't it be from instead of to? Since we are dealing with the inverse graph here. So mentally you would read it as iterate over vertices _from_ which we can go to vertex v
 » 16 months ago, # |   0 75963478 ///////////////////////////////////////////////////////////////////// import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException {  Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int[] inp=new int[n]; for(int i=0;i=inp[u+1] && u-1>=0) { if((inp[u]>=inp[u+1] && inp[u-1]=inp[u+1] && u+2=inp[u+1] && inp[u]maxlength) { maxlength=length; } } System.out.println(maxlength); } } ////////////////////////////////////////////////// Problem — D Can someone tell me why the above code for java doesent work I got wrong ans for test 4 but for all simple cases it works
 » 15 months ago, # |   0 For C, wouldn't it be a lot simpler to just have a streak variable and add the streak to count each step? Then you don't have to do any extra math. I solved it like this: for (unsigned long long i = 0; i < s.length(); i++) { if (a.find(s.at(i)) == a.end()) { streak = 0; } else { streak++; count += streak; } } `
 » 14 months ago, # |   0 Dp solution of D ( recursive ) submission
 » 14 months ago, # |   0 Can someone explain, why we can not apply recursion in problem E. I have tried applying it but got wrong ans at testcase 2. I am not able to understand what is happening. If someone can give a shorter testcase which proves my submission is wrong. That would be really helpful. Thanks Here is my submission:- https://codeforces.com/contest/1272/submission/82418760
 » 13 months ago, # | ← Rev. 2 →   0 i am not able to find the bug in my code please help me problem E https://codeforces.com/contest/1272/submission/84568253 getting wrone answer on test case 2
 » 12 months ago, # |   0 I am not understanding this part of the editorial of problem C. Can anyone please help me to understand this:If we are staying at the position i and its value is zero, just skip it. Otherwise, let's find the leftmost position j such that j>i and the j-th value is zero. Then we have to add to the answer the value (j−i)⋅(j−i+1)2 and set i:=j.
 » 12 months ago, # |   0 Can E be solved with DP? https://codeforces.com/contest/1272/submission/88624220 Can't figure out what is wrong, even if there is a cyclic dependency (idx i depends on idx A and A depends on i), I think this should work
 » 4 months ago, # | ← Rev. 4 →   0 problem D : what is wrong here https://codeforces.com/contest/1272/submission/112119176