### BledDest's blog

By BledDest, 7 months ago, translation,

Hello everybody!

Today, on March 1st, 2020 the final round of Technocup olympiad for Russian-speaking high school students is held. The round starts at 13:00 Moscow time.

For those who want to compete on the same problems, we will host two Codeforces rounds: one for the first, and one for the second division. The rounds will start at 13:05 UTC, don't miss them! The round will start just after the onsite contest ends, so it can be postponed slightly if the onsite event timetable changes.

If you compete in the Final Round today, you can't compete in the Codeforces round #625.

The problems are prepared by MikeMirzayanov, Endagorion, tourist, Roms, vovuh, voidmax, adamant and me. Many thanks to KAN, AndreySergunin, antontrygubO_o, kuviman, MrPaul_TUser, Stepavly, artsin666, Pavs, AdvancerMan, Stresshoover, Peinot, geranazavr555, defolaut, sladkayaKlubnichka, cannor147, PrianishnikovaRina and Pavlova for testing the problems!

P.S. Because of the onsite contest, some Codeforces features may be disabled today.

Good luck!

Congratulations to the winners of the round:

Div1

1) ksun48

2) maroonrk

3) jijiang

5) Um_nik

Div2

5) cml

• +132

 » 7 months ago, # |   +106 Good luck with editorial this time)
•  » » 7 months ago, # ^ |   +3 Bad luck...
 » 7 months ago, # |   +4 Good luck everyone!
 » 7 months ago, # |   +11 How many problems will be?
 » 7 months ago, # |   0 Who was the last year's winner ?
•  » » 7 months ago, # ^ |   +25 Ildar 300iq Gainullin
 » 7 months ago, # |   0 Make the editorial with you.
 » 7 months ago, # |   +53 I believe the timing clashes with ABC 157.
 » 7 months ago, # |   +21 How many problems there will be? And what's the score for each problem?
 » 7 months ago, # |   0 why The round will start just after the onsite contest ends?
 » 7 months ago, # |   +5 So can we still hack in this round?
 » 7 months ago, # |   0 is this a rated contest?
•  » » 7 months ago, # ^ |   +33 Probably not.
•  » » 7 months ago, # ^ |   +58 All the rounds containing the name "Codeforces Round #XXX" are rated.
•  » » » 7 months ago, # ^ |   -22 you mean that the round on Mar.03 is not?
•  » » » » 7 months ago, # ^ |   +11 Negation of RubenAshughyan's statement : -->Some of the rounds containing the name "Codeforces Round #XXX" are not rated.or-->Some of the rounds not containing the name "Codeforces Round #XXX" are rated.
 » 7 months ago, # |   +49 There might be unethical and ugly behavior! Be prepared to downvote it!
 » 7 months ago, # |   0 will there be an interactive problem?
•  » » 7 months ago, # ^ |   +4 At Technocup Final Round 2018 and 2019, there was no interactive problem. So probably ...
 » 7 months ago, # |   +86 Hope there will be no online analysis of problems during the contest.
 » 7 months ago, # |   0 I have not competed for a long time, so good luck for me ^_^
 » 7 months ago, # |   +21 This contest is "Hello March 2020".
 » 7 months ago, # |   +68 May I ask which features will be disabled?
•  » » 7 months ago, # ^ |   +23 Maybe user profiles)
•  » » » 7 months ago, # ^ |   0 as well as others submission
 » 7 months ago, # |   +10 Score distribution?
 » 7 months ago, # |   +16 what's the score distribution?
•  » » 7 months ago, # ^ |   +16 Maybe that is what the blog said to be disabled today :D
•  » » » 7 months ago, # ^ | ← Rev. 3 →   +33 it is said that problem setters and testers are very busy checking whether their problems are readable, their tests are strong enough etc, and also the score distribution (but I don't believe that :D )
 » 7 months ago, # |   +77
•  » » 7 months ago, # ^ |   +3 but it isn't infact.
•  » » 7 months ago, # ^ |   +94 This was so cool and then he said "question"...
•  » » » 7 months ago, # ^ |   +15 What's the problem with that word?
 » 7 months ago, # |   0 Will the difficulty of this two contests equals to usual Div.1 & Div.2 respectively?
•  » » 7 months ago, # ^ |   0 Who knows?
 » 7 months ago, # | ← Rev. 2 →   -55 Two legends MikeMirzayanov and tourist have prepared this contest. It will definitely be a great contest. Thank you codeforces :)
 » 7 months ago, # | ← Rev. 2 →   -11 as usual, these contests with suffix "based on ..." are always good.
 » 7 months ago, # |   -47 Can I get ratting?
 » 7 months ago, # |   +48 CF-visualiser doesn't work.
•  » » 7 months ago, # ^ |   +5 Yes.Me too
 » 7 months ago, # |   -20 Why did administrator block my me ? Now I can't submit in the Round #625 QAQ
•  » » 7 months ago, # ^ |   -8 P.S. Because of the onsite contest, some Codeforces features may be disabled today. (The last line of the blog post)
•  » » » 6 months ago, # ^ |   0 Thanks
 » 7 months ago, # |   0 How to solve Div.1 C (Div.2 E) within TL?
•  » » 7 months ago, # ^ |   -11 try fast io ios_base:: ... worked for me.
•  » » 7 months ago, # ^ |   0 You can sort them and compute the contribution of each one.Use binary search and segment_tree.
•  » » 7 months ago, # ^ |   +20 Let's for each armor keep the balance you can achieve (initially it is -cb_i). Sort the weapons according to their attack modifiers, and process them one by one. Each time you process a weapon, add all monsters (also pre-sorted) with defense levels lower than current attack modifier. For each added monster with attack y_i, for all armors with defense modifiers > y_i add the reward for this monster (you can do this in a binary tree). Then just keep track of price of current weapon + maximum of balances for all armors, and remember the best sum.
•  » » » 7 months ago, # ^ |   +8 Just a little curious, why downvotes for all replies? Are they wrong or wtf happened here?
•  » » 7 months ago, # ^ |   0 Using lazy segment tree(range-add and range-max), which has 10^6 element
 » 7 months ago, # |   +398 This is one of the most boring contests I've participated in.
•  » » 7 months ago, # ^ |   +180 I wholeheartedly agree. Nothing interesting at all in ABCE (div1) and F almost made me rage quit. D had some potential but it was lost in a sea of boredom.
•  » » » 7 months ago, # ^ |   -10 What is wrong with F? (Except a quite long statement)
•  » » » » 7 months ago, # ^ |   +18 A culmination of uninterestingness? Its statement aside, the task itself feels very repulsive to me. Maybe it would be even okay if it went together with some other problemset, but this felt like a "cherry" on the "cake".
 » 7 months ago, # |   +7 How to solve Div-2 B problem? :)
•  » » 7 months ago, # ^ |   +1 Each place can only be in a tour with other places that have the same value of j — b[j]. Just count the frequencies for each value of j — b[j] and output the highest one.
•  » » » 7 months ago, # ^ | ← Rev. 2 →   +1 This solution is beautiful. What thought process is leading to it? I mean how to come to "minus index" idea in the first place?
•  » » » » 7 months ago, # ^ | ← Rev. 2 →   +9 $b_{i+1} - b_{i} = c_{i+1} - c_{i} \Leftrightarrow b_{i+1} - c_{i+1} = b_i - c_i$This implies that the $b_i-c_i$ values of all cities in a journey are equal.
•  » » » » 7 months ago, # ^ |   -10 If you want to take (x1, y1), (x2, y2) then they belong to the same line with slope (y2 — y1) / (x2 — x1) since (y2 — y1) = (x2 — x1) then slope = 1 using line equation m * x + b = y since m = 1 then x1 + b = y1, x2 + b = y2. You can imagine x is the index in the array and y is the beauty.
•  » » 7 months ago, # ^ | ← Rev. 2 →   -8 I dont know how to say but here it is HintYou shift the value to value - positionthen you add the value to map[value - position]than the final answer will be max of the map pseudo solutionres <- 0 for i = 1 -> n -- input >> x -- map[x - i] += x -- res = max{res, map[x - i]) output << res 
•  » » 7 months ago, # ^ |   +1 for each element in the array we see what is its difference between its index and its value. because if some differences are equal then it means these elements can be used together as a possible answer. just like if the array was: 1 2 3 4 5 since each element's difference between its index and value is 0 they can all be used together to create an answer. map each possible difference and the map's answer would be the sum of all of these values. then print the maximum answer by iterating over the map.
•  » » 7 months ago, # ^ |   +3 create a array "ans" of size n and intialise it to 0. and also define a mapmp iterate form 0 to n if the value of a[i]-i not exist in map then ans[i] updated to a[i] and if it exist then update the value of ans[i]=a[i]+ans[mp[a[i]-i]. and also update mp[i]=a[i]-i every time Now print the maximum value of ans.
 » 7 months ago, # | ← Rev. 2 →   0 Thanks for the contest <3 AskHow to solve C the string problem AskHow to solve D the graph problem ?
•  » » 7 months ago, # ^ |   0 Ctry to delete all 'z' that satisfy the condition then all 'y' then all 'x' and so on to 'b' .. when you try to delete some char x from string you can iterate over all subsegment that equal to x let us say from L to R (indexes) then if (s[L-1]==x-1 or s[R+1]==x-1) you can delete all segment [L,R]
•  » » » 7 months ago, # ^ | ← Rev. 2 →   +3 Oh, thanks <3Is that O(n * k) solution where k = 26 ?
•  » » » » 7 months ago, # ^ |   0 yes it is
•  » » » » » 7 months ago, # ^ |   0 WishIf I werent late for the contest...
•  » » » 7 months ago, # ^ |   0 sorry my solution is wrong (i got wrong answer) :( i don't know the correct solution
•  » » » » 7 months ago, # ^ | ← Rev. 2 →   +4 Your idea is correct, probably just an implementation issue
•  » » » 7 months ago, # ^ |   0 CYour idea is good, I did the same. As |s| is small, it is easy to solve with text-processing language (here is Perl solution — 72183066, used look-ahead and look-behind inside regex).
•  » » 7 months ago, # ^ |   0 I solved C this way: while there is symbol that can be deleted, I check for all symbols how much symbols going in the alphabet after this symbol is in string(let it be help), and then delete symbol with smallest help.
•  » » 7 months ago, # ^ | ← Rev. 4 →   +5 Dyou can solve it by bfs from t to other vertices (you reverse the edges then start bfs from t) then for(i=1;i
•  » » » 7 months ago, # ^ |   0 I did the same but still got WA on pretest 4. Curious to know what went wrong once the test is released! 72197623
•  » » » » 7 months ago, # ^ |   0 i can't see the submission :(
•  » » » » 7 months ago, # ^ |   0 You are not checking edge between path[i — 1] and path[i] before updating max_routing number value in the else part.
•  » » » » » 7 months ago, # ^ |   0 No, that is not the reason. I am failing in the 4th test case which has answer is "3 3" where as I output "5 5". The else part just increases the max_builds, it should not effect the min_builds
•  » » » » » » 7 months ago, # ^ |   0 Another Error which is causing wrong min_routing(and max_routing as well) is that you are comparing dist[path[i]] with K — 1 — i but instead it should be compared with (dist[path[i-1]] — 1). If both are not equal, only then we should increase min_routing.
 » 7 months ago, # |   -8 why does even second question of div2 have such hard time contrainst and test cases( tc 8)??i skipped all repeated elements still it contains test cases where worst case give n^2, case where all elements are different and not included in any series.
• »
»
7 months ago, # ^ |
-80

# include<bits/stdc++.h>

using namespace std; int main() { int n; cin>>n; int a[n]; for(int i=0;i<n;i++) cin>>a[i]; int ans[n]={0},maxa=0; for(int i=0;i<n;i++) { maxa=max(maxa,a[i]); ans[i]=max(a[i],ans[i]); for(int j=i+1;j<n;j++) { if(a[j]-a[i]==j-i) { ans[j]=max(ans[j],ans[i]+a[j]); } } } for(int i=0;i<n;i++) maxa=max(maxa,ans[i]); cout<<maxa; } I think this solution is good.

•  » » » 7 months ago, # ^ |   +8 You should use The Spoilerand The Block to show your code
•  » » » » 7 months ago, # ^ |   +25 In fact I kinda like the first line. So bold and confident with what you should include.
•  » » » » » 7 months ago, # ^ |   +1 So why dont you bold your sentence :D
•  » » 7 months ago, # ^ |   0 You can do it in O(n)
 » 7 months ago, # | ← Rev. 3 →   +16 Can anybody suggest me what the test is like in test 4 of problem D div 2. :<
•  » » 7 months ago, # ^ |   +1 Me too, WA on test4 countless times :(
•  » » 7 months ago, # ^ |   0 I kept getting hit by at TLE on test 7 :(
•  » » 7 months ago, # ^ | ← Rev. 2 →   +1 Think is something like test5 51 22 33 44 53 551 2 3 4 5Because when i solved that, it was WA on test 5Then i looked at test6 71 22 33 44 53 51 66 451 2 3 4 5And when i solved that, it was AC.
•  » » » 7 months ago, # ^ | ← Rev. 2 →   0 Are the answers on your tests are 1 1 and 1 2? My solution outputs this answers and still fails in Test 5. 72205820 Don't know, if it was intended, that Test 4 and Test 5 contents are hidden.
•  » » » » 7 months ago, # ^ |   0 We can't see others' submission in this contest. Please try another way to show your code.
•  » » » » » 7 months ago, # ^ |   0
•  » » » » 7 months ago, # ^ |   0 A very stupid mistake was found, finally AC.  for (size_t i = 0; i < k; i++) { const size_t v = p[i]; const size_t currMinDistance = distances[v]; bool canRebuild = false; bool mustRebuild = false; if (isAmbigous[v]) { canRebuild = true; - } else if (i + 1 < k) { + } + if (i + 1 < k) { const size_t nextMinDistance = distances[p[i + 1]]; if (nextMinDistance + 1 != currMinDistance) { canRebuild = true; mustRebuild = true; } } if (canRebuild) { maxCount += 1; } if (mustRebuild) { minCount += 1; } } 
•  » » » 7 months ago, # ^ |   0 Thanks for your data, even though I also made another stupid mistake :(
 » 7 months ago, # |   0 Pls help how to solve D div 2 (B div 1)
 » 7 months ago, # |   +36 Is it only me that E was straightforward and D was undoable?
•  » » 7 months ago, # ^ |   +8 I just read E after the competition after being stuck at D, and immediately regretted not doing so earlier. I reckon the main reason D is solved more is just the (questionable) order.
•  » » 7 months ago, # ^ | ← Rev. 2 →   +20 For me it's the opposite shrug
 » 7 months ago, # |   0 How to solve Div 1 C?
•  » » 7 months ago, # ^ |   0 You can read the comment above.
•  » » 7 months ago, # ^ |   +5 it seems that creating events for the second stuffs and the third sorting by their first entry and using segment tree to maintain the answer is enough for this task. (Though it may involves some details I guess)
 » 7 months ago, # |   +18 About problem D1C. I came with this approach. First use only useful weapon and defense. (Higher attack cost more money). Then sort all monsters on their defense and lets add them one by one. When we are adding monster we should increase our attack to kill him, and find minimal needed defense to kill him(using upper bound). Then for all defenses higher then found we will get reward for him also. Lets maintain segtree on the array $a$, where $a_i$ = amount of money you get using i-s defense item. Firstly $a_i = -d_i[cost]$ Then when adding a monster k we add $z_k$ on the segment $[pos, m - 1]$ (pos is minimum defense needed). And update ans. So the question is, has someone submitted solution using same approach? Or whats wrong with this approach? Code: https://pastebin.com/jZyVajPi
•  » » 7 months ago, # ^ |   +18 My approach is the same, and my solution passed all pretests.
 » 7 months ago, # | ← Rev. 3 →   +3 How to solve problem D div2?pls give me sone hint....
•  » » 7 months ago, # ^ |   0 Dijkstra(O(mlogm)) Count the number of minimum paths as well.
•  » » » 7 months ago, # ^ |   +58 I think " bfs " is enough .
•  » » » » 7 months ago, # ^ |   0 thanks you.If I had been calmer than I would have done it. So sad
•  » » 7 months ago, # ^ |   +1 When standing in an intersection a, if the direction ploycarp is going, is not on the shortest path within the neighbours of a to the work, then we have to rebuild no matter what. If the shortest path from the way polycarp is going is the shortest path within all paths from neighbours of a to work, then if there are no other paths as short, we dont need to rebuild, and if there are other paths as short, then the maximum number of rebuilds should go up by one, but the minimum should stay the same
•  » » » 7 months ago, # ^ |   0 thanks you.
 » 7 months ago, # |   0 It's quite weird that my solution can't pass sample test(Runtime error), since it passes sample test on my laptop, and I didn't do anything may lead to RE. (Since I have a WA 3 submission)And when I just changed my modulo, and it passed sample test, but get RE on test 2.Can anyone explain why? Here are my many other submissions:
•  » » 7 months ago, # ^ |   +8 ppow has maxn size, which is 2e5+7. And on line 99 you run loop on 4e5 elements, so it is out of bounds access to array. You can easy catch such errors if you compile your code with -fsanitize=address
•  » » » 7 months ago, # ^ |   0 Thank you!It seems that I have never gotten rid of those stupid mistakes :(
 » 7 months ago, # |   +12 Thanks mr. Endagorion for letting this problem from your past contest into this contest.
•  » » 7 months ago, # ^ |   +41 What's the same?
•  » » » 7 months ago, # ^ | ← Rev. 2 →   -19 div1E, it's not 100% the same but after building the virtual tree it's trivial.
•  » » » » 7 months ago, # ^ |   +62 It's not the same problem, it's the same technique. I'd argue it's not interesting and doesn't deserve to be an E, but it's definitely not the same problem.
•  » » » » » 7 months ago, # ^ |   +36 Agree with Encho, it's just the same technique.
•  » » » » » 7 months ago, # ^ |   0 Fair enough, I don't remember what the problem is about. For me this problem all about the technique and the rest is not important/easy.
•  » » » » 7 months ago, # ^ |   -19 It is trivially similiar.
•  » » 7 months ago, # ^ |   +23 Ugh, I would definitely not call it the same problem. Compressing the induced tree is very common trick and that is basically whole intersection of solutions.
•  » » 7 months ago, # ^ |   0 I don't see how this is the same problem as E.
 » 7 months ago, # |   +35 why the system tests didn't start ?
 » 7 months ago, # |   +8 How to solve div1 D?
•  » » 7 months ago, # ^ |   0 You can remove "11" substring. Then reduced strings should be the same.To find a reduced string of a substring I used rolling hash along with the segment tree.
•  » » » 7 months ago, # ^ |   +16 Why this is enough?
•  » » » » 7 months ago, # ^ |   0 You can imagine that '0' stands for a coin and '1' stands for an empty position. So for each move, a coin is moved across two empty positions backward or forward. In this move, for every two adjacent coins, the parity of distance between them will not change. So you can keep moving the coins to the left, and finally you will find the sequence that no two adjacent coins have a distance greater than one. That's the same as the result of removing all '11' substring.
 » 7 months ago, # |   +2 Why can't I submit a task during system testing?
 » 7 months ago, # |   0 How to solve div2 E (div1 C)?
•  » » 7 months ago, # ^ |   +14 Sort armor by incresing b. Create segement tree and update it with -cb for every armor piece.Then do a sweep on monsters(by their x) and weapons(by their a): if current event is weapon, update solution to sol = max(sol, -ca + (max element in segment tree)) else find first armor set with b > y (denote it as pos) and update interval [pos, m - 1] in segement tree with +z You can implement additions in segement tree with lazy propagation, and finding first armor set with binary search or lower_bound
 » 7 months ago, # | ← Rev. 5 →   0 I can't seem to understand why am I getting RE in [problem:https://codeforces.com/contest/1321/problem/A] on pretest 5. Spoiler Code 72185248int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin>>n; vector r, b; int r_1=0, b_1=0; for(int i=0; i> tmp; if(tmp==1) r_1+=1; r.push_back(tmp); } for(int i=0; i> tmp; if(tmp==1) b_1+=1; b.push_back(tmp); } if(r_1==b_1){ cout << -1 << endl; }else if(r_1>b_1){ cout << 1 << endl; }else{ int or1=0, sr1=0; for(int i=0; i
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 We cant read your code now. Use this SpoilerAnd this Block to show your code
•  » » » 7 months ago, # ^ |   0 Can't seem to make it work. Can you see the code now?
•  » » 7 months ago, # ^ | ← Rev. 5 →   0 //if it is test case 5 then you have divide by 0. //for example may be you have calculated int count_r = if(r[i] == 1 && b[i] == 0); int count_b = if(r[i] == 0 && b[i] == 1); and for answer you may have done cout << (count_b/count_r) + 1; //here count_r can be zero `
•  » » » 7 months ago, # ^ |   0 Oh yes! Can't believe I didn't think of that case. :/Thanks!
•  » » » » 7 months ago, # ^ |   0 i wasted nearly 20 min looking at my code and then looked at the result and released it was runtime error rather than wrong answer :(
•  » » » » » 7 months ago, # ^ |   0 Did you pass test case 10?
•  » » » » » » 7 months ago, # ^ |   0 yes
 » 7 months ago, # | ← Rev. 2 →   +1 How to solve div2 B?
•  » » 7 months ago, # ^ | ← Rev. 2 →   +5 Let's say you want to go from $i$ to $j$ such that $i < j$.The given condition is that $j - i = b[j] - b[i]$So rearranging that: $j - i = b[j] - b[i] \Leftrightarrow$ $j - b[j] = i - b[i]$.So now for every equal value of $i - b[i]$, get the maximum sum of all $b[i]$ (you can do that using a map).
•  » » » 7 months ago, # ^ |   0 I got it now Thanku :)
•  » » » 7 months ago, # ^ |   0 appriciate your answer
•  » » » 7 months ago, # ^ |   0 Thank U.
 » 7 months ago, # |   +26 Hi! The tests, practice and some functionality are hidden because of the onsite event. We will open it after the official award ceremony in Moscow. Please be patient a little!
•  » » 7 months ago, # ^ |   +14 do they livestream?
•  » » » 7 months ago, # ^ |   +11
 » 7 months ago, # |   +156 It's possible to have O(log) in div1 D only because of one modular division (and have no segment trees at all).We know that we can move two adjacent ones. Due to the statement, we can swap them with an adjacent zero and of course, we can imagine swapping them with an adjacent one.So, when we have a string, let's imagine turning it into its canonical form — let's pull all the pairs of adjacent ones to the left: 011101111010->111111010010. This new string has a prefix which consists of an even number of ones and then some suffix which has no neighboring ones (but can start with a one).As we are asked if two string of the same length are reachable from each other, we can assume that we want to compare only these two suffixes. If these two strings have different number of mentioned pairs, then the suffixes will have different lengths, so we'll know that they are not reachable from each other. If the suffixes have the same length, we'll just compare them as strings.So, we need some hash function, which will "skip" adjacent pairs of ones. I'll use linear functions as the hashes of zeroes and ones, let's call them $f_0$ and $f_1$. The hash of a concatenation of two strings will be the composition of the two functions. The only condition is that $f_1(f_1(x))=x$ must hold for every possible $x$. Let's then set $f_0=random \cdot x+random$ and $f_1=-x+random$.The composition is associative, so we can calculate the composition for every prefix and then calculate the function for an interval with one modular division.
•  » » 7 months ago, # ^ | ← Rev. 2 →   +37 I think you can calculate more straightforward hash for each prefix, for example, consider a string: the number of ones modulo 2 before the fixed zero. And after that you should binary search for each query, to find the set of zeroes. Then you should check that two substrings are equal (or check that one substring is inverse of another one, if parity is different). Also you can change binary search to some straightforward linear time precalc, and solve the problem in linear time.
•  » » » 7 months ago, # ^ |   +54 Yea, there are different solutions, but I think that mine is quite educational, so I've described it.
•  » » 7 months ago, # ^ | ← Rev. 2 →   +88 It is possible to have O(1) in div 1 D.I couldn't find the observation that we need to remove pairs of 11 during the contest. Instead of it, I found other pairs of observations:1) numbers don't change the parity of their positions2) If one zero was before another zero, they should store the order.It is actually identical to removing 11.But these lead to the solution, that because the number can change their position, but can't change the parity of position. Let's just compare the parity of positions where zeros are located.101011 -> 2 4 -> 0 0010111 -> 1 3 -> 1 1Now let's just remove all ones from the initial string, and just store the parity of positions of zeros. And build hash over this string.To answer query just compare hashes of this new string in compressed positions. To solve the problem of different parity of initial start, we need to build hashes of two string, where second just inverse of first. I had O(log) just to find the position of beginning new interval in the compressed string. But it can be done in O(1) with O(n) preprocessing just store position of start for each index.P.S. my code is a bit messy, because I wrote another solution and only then added this idea. Better refer to the text.72206443Better version of code here -> 72212662
•  » » » 7 months ago, # ^ |   0 Do you have a solid proof for why just comparing parities of zero positions works?
•  » » » » 7 months ago, # ^ | ← Rev. 2 →   +17 Yes, I would try to explain. it can be easily transformed into removing 11 and comparing the rest of the string by equality.What information we are losing, the pairs of 11 between zeros. Because removing 11 didn't change the parity of positions. 0110 -> 0 1 and 00 -> 0 1 But as it was described above it is redundant information, it didn't change anything.Then we can lose some lonely ones :010 01010, But actually we are not losing because knowing the parity of two consecutive zero, we can understand if it was 1 between them010 -> 0 000 -> 0 10010 -> 0 1 1000 -> 0 1 0 So storing the parity of zero's position is the same as storing the whole string of 0s and 1s (where there is no two consecutive 1)
•  » » 7 months ago, # ^ |   +18 Yep, one of solutions we had for this problem works in a similar manner, but we substitute $0$ and $1$ by some matrices $A$ and $B$ such that $B^2=k \cdot I$ for some number $k$ and unit matrix $I$. We check that matrix products on corresponding segments are equal, which may be done in $O(1)$ per query with a bit of prefix and suffix products. You may also solve this problem in a similar manner.Though I still think that one should solve this problem in a deterministic way.
•  » » 7 months ago, # ^ |   0 Hey! Don't quite understand how to "inverse" the prefix for the substring in that case. So, as I understand $prefix_i = f_{s_i}(prefix_{i-1})$. Having that, we need to take $prefix_r(prefix_{l-1}^{-1}(0))$ and this requires to maintain the polynomial. Probably I got it wrong. Could you elaborate please on that?
•  » » 7 months ago, # ^ |   0 Really cool! Do you know how to reason about the probability of error?
 » 7 months ago, # |   0 did anyone think to solve C div 2 using 0/1 dp? i was trying to solve it like knapsack but didn't get it right..any suggests will be highly appreciated
•  » » 7 months ago, # ^ |   +26 For C you could've just used basic greedy solution that uses bfs. Just try some cases and see that greedy solution works all the time and try to implement it with bfs.
•  » » » 7 months ago, # ^ |   0 i am trying to upvote you after a stupid mobile misclick on the downvote but it seems i cant undo my stupid mistake, please accept my appology and if you reply to this i will upvote so you dont get negative upvotes, and thanks for your response i will try it out, iam kinda new in here, once again i am very sorry
•  » » 7 months ago, # ^ |   0 remove biggest possible option until you run out of options.
•  » » 7 months ago, # ^ |   +1 Using knapsack DP is invalid because your state has to indicate which indices have been deleted (using bit-masking or similar) which can't be done given that the size is 100, same principle applies to back tracking or any permutation technique I can think of. HintThink of some brute force solution where you start by deleting each occurrence of some alphabet that does not affect the solution (the alphabet that does not contribute in deleting any other alphabets)
 » 7 months ago, # |   +101 Achievement unlocked: Place last in a Codeforces round
•  » » 7 months ago, # ^ |   0 Why is this an achievement, I do this all the time.... :(
•  » » 7 months ago, # ^ |   +1 Hahaha
 » 7 months ago, # |   +8 round is rated or not ?
•  » » 7 months ago, # ^ |   +5 Yes.
 » 7 months ago, # |   0 How to solve Problem B(Div 2)?
•  » » 7 months ago, # ^ |   0 This is the solution that I found the easiest to understand: Comment
 » 7 months ago, # |   0 When will they put the tutorials/solutions?
 » 7 months ago, # |   +10 shit! I misread the sentence is div.2 C. Because the title contains the word "Adjacent" I thought it is allowed to remove character not only the adjacent in position but also in the alphabets. I am so sad.
•  » » 7 months ago, # ^ |   0 Me too :( But any idea on how to solve this version of the problem?
•  » » » 7 months ago, # ^ |   0 What I tried to do is firstly devide-and-conquer approach: If we know range [l,r) is deletable then l-1 and r becomes adjacent now and may be deletable. Secondly, I thought it is graph something. The alphabetical adjacency can be expressed as graph and it is obvious that at some moment, a node with degree one should be higher priority than those with higher degrees. After these thinkings however, I couldn't find the way out. Regret is that I should test the sample 1 so I could find myself misunderstood the problem sentence.
 » 7 months ago, # | ← Rev. 2 →   -21 one of the weirdest and most boring rounds I've ever participated . I hope next round will be more exciting and fun XD
•  » » 7 months ago, # ^ | ← Rev. 2 →   +15 For me the problems where not that bad. The fact that others solved them much faster than me was :/However, I think Div2 B and C where kind of math problems, since once the key observation is clear, it is more or less trivial implementation.
 » 7 months ago, # |   0 When will ratings get updated?
 » 7 months ago, # | ← Rev. 2 →   -9 .
 » 7 months ago, # |   0 cool and nice div1 contest :)
 » 7 months ago, # |   -8 My (correct) div2 D solution timed out using py3 in post contest tests but when I resubmit I pass based on random variation in timing... Anything I can do or is it just what I get for using python?
 » 7 months ago, # |   -8 why im getting runtime error and tle at test case 5 of div2 A..?
•  » » 7 months ago, # ^ |   0 May you are dividing by zero
 » 7 months ago, # |   0 How to solve Div 2 Problem C: "Remove Adjacent" ?
•  » » 7 months ago, # ^ |   0 I did this. submission
•  » » » 7 months ago, # ^ |   0 Submissions are not visible right now
•  » » 7 months ago, # ^ |   +2 I started at the maximum value in the string and kept deleting elements before and after it until I there are no elements which satisfy the given condition and do it all over again while decreasing the maximum value. I hope that makes sense.
•  » » » 7 months ago, # ^ |   0 Got it, thanks
 » 7 months ago, # |   +8 Where can I find Editorials of these questions..?
 » 7 months ago, # | ← Rev. 2 →   +17 Became a Candidate Master ~ Happy happy day >__
•  » » 7 months ago, # ^ |   +11 me too, bro — ^__^
•  » » 7 months ago, # ^ |   +5 became an expert again:(
 » 7 months ago, # |   +33 Final round rated?
 » 7 months ago, # |   +37 Ummmm..... I cannot find the solution, editorial please help me
 » 7 months ago, # |   -21 The pretests in this contest is too weak :( I have dropped my rating because of this too many time. I hope this is the last :(
 » 7 months ago, # |   0 How terrible!The second problem in Div 2 is the first problem in Div 1!
 » 7 months ago, # |   0 When will be the editorial?