Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

### BledDest's blog

By BledDest, history, 4 weeks ago, ,
Div2A
Div2B/Div1A
Div2C
Div2D/Div1B
Div2E/Div1C
Div2F/Div1D
Div1E
Div1F

• +54

 » 4 weeks ago, # |   -32 Nice editorial :)
 » 4 weeks ago, # |   -30 thank you for editorial
 » 4 weeks ago, # |   0 so unlucky with problem div.2 E ;( thanks for editorials. can someone check my code and find my bug? i was debuging for 2 hours and found nothing. my code
•  » » 4 weeks ago, # ^ |   +2 The test on which your code is failing is small in size(n=m=p=10) so you can use it as a counter-testcase and debug..
 » 4 weeks ago, # |   -9 I have a problem with 1321C - Удаление соседних. I don't really understand how the answer to the first test case is $4$ According to the problem, $1 \leq i \leq |s|$Let s = $bacabcab$ $1$) We remove $s_2$ = $a$ and we get $s$ = $bcabcab$$2) We remove s_2 = c and we get s = babcab$$3$) We remove $s_1$ = $b$ and we get $s$ = $abcab$$4) We remove s_3 = c and we get s = abab$$5$) We remove $s_3$ = $a$ and we get $s$ = $abb$$6) We remove s_2 = b and we get s = ab$$7$) We remove $s_2$ = $b$ and we get $s$ = $a$Which cannot be shortened further. So we removed a total of $7$ characters. Shouldn't that be the optimal answer?
•  » » 4 weeks ago, # ^ |   +5 'a' can never be removed as it has no previous letter (see problem statement)
•  » » 4 weeks ago, # ^ |   0 You cannot remove "a" because it was clearly mentioned that only those letters can be removed whose neighbor is previous letter of the alphabet.
•  » » 4 weeks ago, # ^ |   0 I think you misunderstood the meaning of this problem. You should read it again carefully.
•  » » 4 weeks ago, # ^ |   0 Look at the problem statement!'a'has no previous letters!
•  » » 3 weeks ago, # ^ |   0 We can't remove 'a'.it's mentioned in the problem.
•  » » 3 weeks ago, # ^ |   0 Actually i got very confused so according to question b is previous element of a, or y is previous element of z,but a is not previous element of d.I wasted a lot of time in this
 » 4 weeks ago, # | ← Rev. 6 →   +4 I'm confused by the editorial for Div2F/Div1D. When I tried to implement it I seem to always get WA buried somewhere in test case 6, and I don't really know how it handles the case of odd number of consecutive ones, or the case:$11010 \rightarrow 01110 \rightarrow 01011$Edit: Oh, I think you meant deleting the $1$ s from the string altogether. I turned out to be converting them into $0$ s instead, which is clearly wrongEdit 2: And now I fail at test 10. This is tough.Edit 3: Got it. Had to add special handling for "empty" strings.
 » 4 weeks ago, # |   +6 I don't understand this explanation for Div2C. Why is it always true? Suppose we remove the maximum letter i that can be used to remove some other letter j (it is obvious that si+1=sj in such case). If there are no other letters between si and sj then si is not the maximum letter, so we got contradiction with our algorithm. Now suppose that we can remove all letters between si and sj. Then we first choose sj and only after that si by our algorithm. Consider the last case — there is at least one letter sk between si and sj. Because we cannot remove sk then there are only two cases: sk>sj+1 or sk+1
•  » » 4 weeks ago, # ^ |   +7 For me that just proofs that for the lexicographically last letter (ie 'z') there is no letter after that one. Then it states that if such one is removed, all other possible removals still exist. So we can remove letters in reverse lexicographically order. Kind of induction.
 » 4 weeks ago, # |   +8 Please, add author solutions too.
 » 4 weeks ago, # |   +10 Hey, is there anyone here knows other problems that need to use the tree compression trick like D1E? I learned it before but I forgot :(
 » 4 weeks ago, # |   0 Can someone explain div1D please? I just can't get the point of what the tutorial is saying...
•  » » 4 weeks ago, # ^ |   0 In short, the tuition is like this. Since you have the transformation is to change "011" to "110" and vice versa, the parity of the number of "1" between any two consecutive "0"s remains. Therefore, if there is any "11" in our original string, the fact that you delete it would not change anything. Just delete all "11" in the original string, and you obtain a shorter new string. To answer queries, just pick the substrings of the new string that correspond to the substrings in the original, and compare if they are the same.
•  » » » 4 weeks ago, # ^ |   0 Thanks a lot bro! A lot nicer explanation!
 » 4 weeks ago, # |   0 In div2E as per my understanding we need to implement segment tree to support max query over cumulative sum. Am I right?
•  » » 4 weeks ago, # ^ |   0 For those like me — This problem requires segment tree with lazy update
 » 4 weeks ago, # |   0 In problem div2 D how is the minimum rebuild in example 3 0? why is not 1?
•  » » 11 hours ago, # ^ |   0 If you make the transposed graph (basically all edges in opposite direction) and calculate the shortest distance from the last node, you'll see that the given path is indeed the shortest path from 8 to 1. Therefore, if I take this path on node 8, I can continue with this. Question asked rebuilds not builds so first build is excluded.
 » 4 weeks ago, # | ← Rev. 2 →   0 Can anyone help me find which test case my code for DIV2-B fails.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 You have an error in overflowing values. The maximum value for n is 2*10^5, for each number 4*10^5. Multiplying these numbers we get 8*10^10. While int can store data up to 2*10^9. Replace the int with long long. P.S. And in general, I would recommend doing this task the way it is editorial, because on big tests you will get TL.
•  » » » 4 weeks ago, # ^ |   0 Tanx alot.
 » 4 weeks ago, # |   0 I couldn't understand the editorial of Div2C .It will be great if someone explain it to me. Moreover,I cannot figure out which case i am missing.here is my code:https://codeforces.com/contest/1321/submission/72240578
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 It is something as follow: We first try to remove occurrences of 'z'. Now if there any 'z' remaining that can't be removed. Then we remove occurrences of 'y' wherever possible. and so on.And here in each pass you can scan entire array. As there are only about 100 characters.Now, you may ask why we are not starting with 'a' then 'b' then 'c' and so on...?Because suppose you have following string — 'cbca'. Then if we had tried to remove 'b' then it would not be remove after it's pass gets over. But after removing 'c' string becomes 'ba'. So, we find out that we can also remove 'b'.And if you think a little bit than you will see that in our approach of removing characters in reverse alphabetical order once we find that we can't remove given character then we will never be able to remove that character in future.
 » 4 weeks ago, # |   0 Can somebody explain why my soln to div 2 D is giving WA ??. Submission Link
»
4 weeks ago, # |
-19

Why I time out on 1320A?I think I only use time O(N)!

# include<bits/stdc++.h>

using namespace std; typedef struct{ int val,id; }node; int main(){ int i,n; long long s,k,m=0; scanf("%d",&n); vectorb(n),a,c; for(i=0;i<n;i++){scanf("%d",&b[i].val);b[i].id=i+1;m=m>b[i].val?m:b[i].val;} while(b.size()){ a=c;//清空 s=0; k=b[0].id-b[0].val;//按id-val分组 for(i=0;i<b.size();i++){ if(b[i].id-b[i].val==k)s+=b[i].val; else a.push_back(b[i]); } b=a;m=m>s?m:s;//更新最大值 } printf("%lld\n",m); return 0; }

 » 3 weeks ago, # |   0 I am posting a bit unique solution for div2C remove adjacent. Hope you find it useful. https://codeforces.com/contest/1321/submission/73099847
 » 3 weeks ago, # | ← Rev. 2 →   0 My code is running on my system and many online compilers but giving different answer with codeforces compiler. Please help and tell me why am I getting different output with codeforces compiler. My code is Here.The problem statement is Here
 » 3 weeks ago, # |   0 Can someone help me out? My code for div 2 D(Navigation system) showing memory limit exceeded on test case 14. My submission link is https://codeforces.com/contest/1321/submission/73115697 . I am unable to debug my code.
 » 47 hours ago, # |   0 Div2C also has a $O(n^3)$ dp solution https://codeforces.com/contest/1321/submission/74736147