### awoo's blog

By awoo, history, 2 years ago, translation, 1400A - String Similarity

Idea: BledDest

Tutorial

1400B - RPG Protagonist

Tutorial

1400C - Binary String Reconstruction

Idea: Roms

Tutorial
Solution (Roms)

1400D - Zigzags

Tutorial

1400E - Clear the Multiset

Idea: Roms

Tutorial
Solution (Roms)

1400F - x-prime Substrings

Idea: BledDest and Roms

Tutorial
Solution (pikmike)

1400G - Mercenaries

Idea: BledDest and Roms

Tutorial
Solution (BledDest)  Comments (62)
| Write comment?
 » Editorial for E is not visible, can you please fix it.
 » 2 years ago, # | ← Rev. 3 →   You can see nothing
 » In the contest page, the tutorial link redirects to neal's blog of Unofficial editorial. Maybe you should add this blog as tutorial, and neal's blog as extra tutorial.
 » Any similar problems like B for practice ?
 » Can someone explain what's wrong with my solution for B?
•  » » You aren't checking the cases when Follower can't pick enough items because Protagonist didn't leave for him. You are running two loops totally exclusively, but in reality they aren't mutually exclusive, and instead, dependent on each other. x swords picked by protagonist means Follower is only left with s-x and he has to choose from them.
 » 2 years ago, # | ← Rev. 2 →   Can someone give a binary search approach to problem B, I am not able to implement it, and not getting the function that can be used to find different numbers satisfying the given condition i.e x*(no_of_swords) + y*(no_of_war axes) <= p(or f), or this can't be implemented? Thanks a lot in advance!!
•  » » You mean problem B? LINK
•  » » » Can you explain this please you are doing r=mid-1 for first BS l=mid+1 for second BSWhy not together? How did u come up this unique in time of contest??
•  » » » » Basic idea : There are 2 people : me and my follower. I will brute force on the number of $swords$ that I take, binary search on the number of $swords$ my follower takes, and there will be some space left for both of us, we will use that to take as many $axes$ as we can. Problem with binary search : While doing binary search transition to the left or right is the most important thing. In our code $mid$ represents the number of $swords$ my follower is trying to take at this moment. If he can't take that much obviously he will try to take less, hence $r = mid-1$. If he can, then which direction you go next time? You try to take more swords and do $mid = l+1$, or do you try to take even lesser swords and do $r = mid-1$? We don't know. That is why I just decided to do both in separate binary searches. Doing it in one binary search : Do we try to take more swords or less? Actually we know the answer. If the weight of a sword is greater than the weight of an axe, taking more swords only reduces your chance of getting more items. So a simple greedy will allow you to do it in one binary search. LINK. It's just in contest I instantly had the idea of doing 2 binary searches so I just sticked with it.
 » Roms awoo In Problem E, what is the meaning of "closed", "open", "unclosed" operation?
•  » » The operations of the first type are applied to some segments. An "unclosed" operation means that we have started a segment corresponding to some operation of the first type earlier, but haven't finished it yet. To "open" an operation is to start a segment, to "close" it is to end a segment.
•  » » » So what does it mean to "close" some operations of the second type and "open" a new operation of the second type?
 » i cannnot understand the DP solution to problem E, can somebody help me ?
•  » » In case you need other solution than DP.Consider a range [l,r]. For first type of operations: Consider an index x (l<=x<=r) such that a[x] is minimum in that range. If we apply the first operation a[x] times, then each element would be reduced by a[x]. And a[x] becomes 0. Now we can break this range in two parts [l,x-1] ans [x+1, r] and do the same thing. When there is a 0 in the range.This case is handled by itself. Here a[x] will be zero, so operations of first type would also be zero. and then the range would be divided in two. When there are multiple indices whose values are minimum in the rangeAll of these value become zero after we apply the first operation a[x] times. Then this case would be handled as described above.For second type of operation: We can delete all elements in this range in no more than r-l+1 operations of second type.Code : 91083858
•  » » » 2 years ago, # ^ | ← Rev. 11 →   Problem E . explain the Tag "DP & sorting"Now i've get the process by checking out the top div.1 programmer jiangly's solution. It's an implement of The line chart .At first, assume the second option is banned .This problem == CF1392C — Omkar and Waterslide.it indicates that when we go up from the (i-1)th positon to the (i)th position, the new cost =the difference betweem a[i-1] and a[i] ,formally,** a[i]-a[i-1]**. when we go down from the (i-1)th positon to the (i)th position, the new cost =0;now consider the second option, it means we can change the num in ith position,(the raw a[i]) to any num less than or equal to a[i], the cost=(new_num
•  » » » For the second type of operation, you are considering r-l+1 operations but if there are already elements with zeros what about them. Shouldn't we just count the number of non zero elements and use that instead. Or Maybe that case is handled by recursion?
•  » » » » If there is a 0 in range [l,r], then the range would be divided into two without using any operation. Read the first spoiler.
•  » » » Why does greedy work?
 » In problem B, why we should take at first min(s,w)?
•  » » just greedy , cheaper means more chance to buy more items
 » 2 years ago, # | ← Rev. 7 →   Problem D: Can anyone please tell me what is wrong with my solution? it is not working for this test case: 3028 30 29 29 30 30 29 30 30 30 30 28 28 28 28 29 29 28 29 29 29 30 29 29 30 28 30 30 28 29 expected : 2618 received output : 41212 #include using namespace std; #define gc getchar_unlocked #define fo(i,n) for(int i=0;in;k> t; while(t--) { solve(); } return 0; } 
•  » » fo(i,n+1).... in the loop where youre clearing the rig array...
 » In problem E answer does not exceed $n$ because we can use $n$ operations of the second type so we can consider second parameter up to $n$.
 » For people interested, 3b1b-styled visual editorial for D. Zigzags this time with narration and as always, with visual dry-run of a testcase.
 » 2 years ago, # | ← Rev. 3 →   after reading editorial i feel D was easy i don't know what i was thinking during contest.
 » After seeing the MOD value for problem G, I was wondering, where/how FFT should be applied here. :)
 » I loved this contest, specially the problems D, E and F, learned a lot of thouse!! DP with Aho-Corasick blow up my mind but after understand it was awesome!!
•  » » Can you please explain the DP part(see below) of problem F x-prime substring? forn(i, s.size()) forn(j, trie.size()) if (dp[i][j] != INF){ dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1); int nxt = go(j, s[i] - '1'); if (!trie[nxt].term) dp[i + 1][nxt] = min(dp[i + 1][nxt], dp[i][j]); } 
•  » » » Sorry, I didn't understand the autor's solution, I write my own recursive approach that think is easier to understand [http://codeforces.com/contest/1400/submission/91095834](my solution) PD: Also my Aho-Corasik is another implementation
•  » » » » I hand run your code for the input s = '116285317' and x = 8. I was to able to understand finish and cnt array, but can you please explain the "out" and "link" arrays as they both remain zero for the aforementioned input? I know how Aho-Corasick algorithm works and it would be great if you could relate out and link arrays to equivalent arrays used in the Aho-Corasick link provided would really help me. Can you provide a better input(than mentioned at the top) which can make your solution more clear to me?Thank you!!!
•  » » » » » Sure, these are the values that stores each array of my Aho-Corasik implementation: cnt[n] -> amount of words that end in node n finish[n] -> id of the word that end in node n (not important in this problem) fail[n] -> suffix link of node n out[n] -> end word link of node n (also not important in this problem) As you can see the BFS named buildf() calculate these values, so ALL possible transitions of the automaton are calculated beforehand.Hope this help you...
•  » » » » » » Thank you Johnny. I have drawn a trie(see below) for 8 prime set (5,3) (3,5) (8) Suffix link of every vertex is 0 except vertex 4 with suffix link 1 and vertex 2 with suffix link 3. Please correct me if I am wrong.When I ran the code for same input s = '116285317' and x = 8, I get :Fail = 1 which is perfect.My question is why fail = 0 ? Is it because in original string we have substring '53' and not '35'? I thought fail should equal 3.May I know why you have taken MAXN=1e5+5 ? Again thanks Johnny for your time.
•  » » » » » » » Man I just ran my code and got fail = 3, don't know why you got 0. Anyway my advice is focus in the dp instead of the Aho-Corasik implementation (I've used it many times and it works fine to me, but you can use whatever you like)PD: The MAXN is just a value large enough, nothing special...
•  » » » » » » » » Oh ok. Glad to hear that. It must be a manual error(as I hand run the code) by me. I am so sorry about that.The dp part looked magical at first but breaking it into smaller steps really helped.Finally, I got it.I have learnt a lot from this problem.I don't know how to thank you.
•  » » » » » » » » » Happy to help
 » What language are adedalic's solutions written in?
 » 2 years ago, # | ← Rev. 2 →   *****************Why a O(2n) code getting TLE in problm C****************Can anyone tell me please why this submission 90966915 is showing TLE? It was accepted till final standing and after final standing I've submitted the same code in offline also & which was accepted, see here 91082748. I can't understand whats wrong with me. advance thanks. awoo Roms
•  » » 91117140I copy-pasted your submission 91117140 and it ran in $1918 ms$ and then I submitted it again with some comments and got TLE on test 7 91117335. Basically your code is slow because of the for loop you make to ans+='0'.Instead, using resize makes it run on $31 ms$.You got lucky that your code got accepted at all after the contest. These are minor fluctuations in judging time say ~$150ms$. Your code is basically slow.
•  » » » I was unable to identify the bug. thanks for your cooperation. But I've a little bit more to know. If you tell me some more details why ans = ans + '0' in the loop makes my code slow? Isn't it happening in O(n) time complexity? antontrygub
•  » » » » When adding (concatenating) strings (and almost any object) using the + operator, each operand is copied, after which they are summing and the result is copied to ans. So O (ans.size()) for each addition, due to copying. If you use the += operator, then only the right operand will be copied, push_back works the same way, it will work in O (1) on average.
 » if the edge <= 10 I will solve it...
 » worst contest ever
 » 2 years ago, # | ← Rev. 2 →   Yet another solution for G:There will be at most $2m$ nodes with nonzero degree, let's call this set of nodes $V'$, and let $k = |V'|$. We'll take this part of the graph and solve it independently from the rest. Namely, for each $s \in [1..n]$, we'll find the subset $V_s \subseteq V'$ such that these are exactly the nodes $v$ for which $l_v \leq s \leq r_v$. For each such subset, we can use meet-in-the-middle and sum-of-subsets DP to calculate, for each $j$, the number of ways to choose $j$ independent nodes from $V_s$, and then multiply this with the corresponding binomial coefficient $\binom{z_s-|V_s|}{s-j}$, where $z_s$ is the number of nodes $x$ satisfying $l_x \leq s \leq r_x$ in the whole graph. Fortunately, over all $s$, there can only be $2k$ different values of $V_s$, so we do the second phase only a small number of times. Also the sum-of-subsets DP of the first phase needs to be done only once.Code
 » In problem G, how to calculate $c_s$?
•  » » The cnt array serves that purpose in the editorial code.
•  » » » Thank you very much. But the tutorial didn't mention it. I hope the author can add this to the tutorial.
 » During solving this round, I understood that problem 1400E - Очистите мультимножество is similar to 448C - Про покраску забора. It's just rephrasing of the problem statement.
•  » » But we should notice that: when the input is: 1 0 the output should be 0,instead of 1 This is why I was hacked when I submit the same code as what I submitted in the 448C.
 » In Problem F, how about the string 2222222232222222232...(1000 characters long)? Doesn't it have about 1000 19-prime substrings, each with length 9? Their total length would then be about 9000. What is wrong here?
•  » » I thought the total length <= $5000$ remark is discussing the set of all possible distinct $x$-prime strings, and not the multiset of all $x$-prime substrings of the input or anything of that sort. But that can't be the case, as it is easily calculated with a small dp that there are $2399$ distinct strings which are $19$-prime, and their total length is $13739$. But the Trie generated from the $19$-prime strings still only has $4853$ nodes, because many prefixes are shared among those strings, and it is this number that determines the number of values of $y$ and the state space of the dp. A short Haskell program that calculates these numbersimport Data.List ( group, inits, sort ) f :: Int -> [[Int]] f n = case compare n 0 of LT -> [] EQ -> [[]] GT -> [k : s | k <- [2..9], s <- f (n-k)] x :: [[Int]] -- x is the list of all 19-prime strings x = f 19 y :: [[Int]] -- y is the list of all prefixes of 19-prime strings y = concatMap inits x z :: [[Int]] -- z is the sorted list of all unique prefixes of 19-prime strings z = map head (group (sort y)) main :: IO () main = do putStr "Number of 19-prime strings: " print (length x) putStr "Total length of all 19-prime strings: " print (sum (map length x)) putStr "Number of unique prefixes of 19-prime strings: " print (length z) 
•  » » » You're right. I misunderstood the remark. Thanks for the explanation!
 » There is a small typo in problem G (the factor of $(-1)^{|E|}$ is missing from the summation) . Other than that, it is a very nice writeup :)
 » 2 years ago, # | ← Rev. 2 →   With exact same approach as C, but using Java is giving me TLE. Anything I have missed to optimise? Any solution? My submission: 91120981
•  » » Instead of filling w with -1, fill it with 1. Update it's value only when you need to, i.e. when s[i]=0 and you have to make w[i-x] and w[i+x] 0. I copy/pasted your code and made these changes and it got accepted!
 » In zigzag the explanation should be ik), right?
 » I am not able to understand the DP solution of problem E, can somebody help me ?
 » 2 years ago, # | ← Rev. 3 →   In problem E, I have implemented a recursive solution where I compare the second operation ($r - l + 1$) with applying the first operations — subtracting minimum value of the range which splits the range into possibly multiple ranges with all positive elements and recursing further into those ranges. It passed all tests with 202ms in Java and implementation-wise, it's quite easy. I'm wondering if it's the tests were weak or the solution in practice runs faster. Anyone can reason about the complexity? Here's my solution.
•  » » The complexity is correct.Every time you visit the solveForAny function,the segment(l,r) is split into at least two parts.In the end,there are no more than n segments,so the total number of visits is no more than n.So the total complexity is O(n^2).You can refer to the blog,there's a clear explanation in it.
 » Can someone help me with Question D, its giving me TLE on the 6 test case but i am not able to find where i am going wrong, even though my code almost matches the editorial. my code
•  » » With PyPy 3 your solution is fast enough. 91575402
 » I can't figure out when will the answer be "-1" in C. Can anyone help me out please?