### vovuh's blog

By vovuh, history, 3 years ago, translation,

1092A - Uniform String

Tutorial
Solution

1092B - Teams Forming

Tutorial
Solution

1092C - Prefixes and Suffixes

Tutorial
Solution

1092D1 - Great Vova Wall (Version 1)

Tutorial
Solution 1
Solution 2

1092D2 - Great Vova Wall (Version 2)

Tutorial
Solution

1092E - Minimal Diameter Forest

Tutorial
Solution

1092F - Tree with Maximum Cost

Tutorial
Solution

• +32

 » 3 years ago, # |   -14 my solution on E was same with editorial but i got WA on test 8
•  » » 3 years ago, # ^ |   0 You are searching for the wrong vertex. I'm really bad at all these graph definitions, is it centroid?) Imagine the following tree: treeYou'll consider vertex 6 center but 4 is the real center.
•  » » » 3 years ago, # ^ |   0 Yes you're right,thank you
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 deleted
•  » » » 3 years ago, # ^ | ← Rev. 3 →   0 My logic was almost same as the editorial. Can you look at it and explain what is wrong in it if possible. My solution is also failing in test case 8.Solution Link is : Solution Link
•  » » » » 3 years ago, # ^ |   +4 Hmm, as far as I can understand, you consider the center the vertex with distance of half the diameter from one of its ends. That is wrong. tree Diameter is 4, you can say that vertex 6 is center.I'm not sure if there is a simpler way but I usually search for vertex with distances (diam / 2) from one end of the diameter and (diam — diam / 2) from the other end.
•  » » » » » 3 years ago, # ^ |   0 Thanks for helping. I got my submission acccepted :).My code for finding centre was kinda tedious. Can you provide your code to find centre of connected tree?
•  » » » » » » 3 years ago, # ^ |   0 Editorial has my code in it. It's basically bfs from x, from y and a loop over the vertices of the current component.
 » 3 years ago, # |   +1 Here I have written my approach to solve problem F: [Editorial] Another Solution to Problem F(1092F) from Codeforces Round #527 (Div. 3)
•  » » 2 years ago, # ^ |   0 Nice
 » 3 years ago, # |   0 Kindly, would you link this to the official contest?
 » 3 years ago, # |   0 how do we solve C but with bigger constraints?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +3 How much bigger are we talking about? One can easily do O(input size) (like O(n2)) replacing multiset with trie but that's about it.
•  » » 3 years ago, # ^ |   0 if i'm not mistaking we can use hashes to compare string parts faster. It is one of the optimization for this task
 » 3 years ago, # |   +21 D1 is interesting! I believe the same idea extends if you are able to place horizontal blocks with size 1 × H and vertical blocks with size V × 1 (in this problem H = V = 2). Any contiguous section of H columns with the same height modulo V can be greedily deleted from consideration. It is possible to make all columns have the same height iff after making all such deletions all remaining columns (if any) have the same height.
 » 3 years ago, # |   0 for problem C: Store all given strings and their positions. Let's two strings of length n - 1 be A and B in given strings. Assume A to be largest prefix then search for A.substr(0, i) for 0 <  = i < n - 1. If all such strings are present then A can be a prefix and check for B as suffix in similar manner. If this goes wrong check for B as a prefix and A for suffix. Is it a correct Approach?
•  » » 3 years ago, # ^ |   0 But that's exactly the editorial?
•  » » » 3 years ago, # ^ |   0 I got WA at test 17
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +2 Oh, that's an interesting case. Let the test be string "abb". Imagine getting it wrong — prefix "bb " and suffix "ab". Each substring exist and the amount is correct. However, they can't make a full string.
•  » » » » » 3 years ago, # ^ |   0 Got it! Thank you.
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 I also have used the same approach,even I am getting correct answer for your test "abb", getting prefix="ab" and suffix ="bb". Still I am getting wrong answer on test case 17. Can you explain it why? awoo
 » 3 years ago, # |   0 Can anyone tell what is the intuition behind the logic of D1 problem i.e how to approach and think as keeping them as odd and even and then deleting all even length segments then deciding if size <=1 then "YES" else "NO". Thanks in advance.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 It's just an experience thing, I believe. Vova first told me D2 and I immediately was like "what if that is correct bracket sequences". It just felt alike. Details for implementation came pretty minor after it. As for D1, turning the numbers to their parities is the most intuitive thing. You kinda trying to check what if there were just a single way to put bricks. And then come up with a strat to do this. The stack is harder but having some similar problems solved already helps find this approach here. The ending step is just common sense. I mean, obviously, either all the segments got destroyed, or all but the one of odd length left. Easier tests for this case (like 1 2 2) can help to understand.
•  » » » 3 years ago, # ^ |   0 Thanks a lot sir.
 » 3 years ago, # |   0 For Uniform String, I had just made an array alphabetically like if n=5 and k=3 so make it abcab here only 3 letters a b c are used. Thus making the easiest solution I think.
 » 3 years ago, # |   0 3 lines implementation in python2.x of A solution for _ in xrange(int(raw_input())): n, k = map(int, raw_input().split()) print ''.join([chr(ord('a') + i%k) for i in xrange(n)]) find more here
 » 3 years ago, # | ← Rev. 3 →   +13 I have a alternative solution to problem D1.Clearly, by using vertical blocks we can change any given input to a binary representation. We simply use a[i] = a[i] % 2 . Now clearly a solution only exists when we can transform this representation to all '0's or all '1'sI claim that we can reach every possible valid state that has a solution by adding 3 i.e binary '11' to a set of all '0's. Example if we have only 4 columns we have possible states of '0000', '0011', '1001','0110', '1111' , '1100'. So, clearly if solution exists the binary representation should be divisible by 3 or '11'. Note that this is only valid when an all '0's solution exists. We also have to check another case for all '1's solution by using a[i] = (a[i] + 1) % 2 repeating the process.So we simply check if your binary representation is divisible by 3 in one of the 2 cases or not. For that we check if absolute value of the difference between the sum of digits in odd places and even places in our binary representaion is divisible by 3 or not, i.e. abs(sum_odd_places - sum_even_places) % 3 == 0.Overall Complexity is O(n) .Solution Code : Python |Submission|
•  » » 4 months ago, # ^ |   0 Your solution is incorrect. The following case 6 2 1 2 1 2 1 gives "YES" in your code, but official solution gives NO. In fact, answer should clearly be NO, You cannot add any horizontal brick at any moment. Divisible by 3 is a necessary condition, but not sufficient.
 » 3 years ago, # |   0 I was trying to solve problem E using centroids (not centroid decomposition) my idea is to find centroids for each connected component add an edge between 2 connected components and then find a new centroid on this new tree, and so on until there is only one centroid left, then I calculate maximum possible dist as maximum_height + 2nd maximum_height, I really do not know why but it gives me wrong answer on test case #8 because my answer is: 22 9 60vs21 9 100since I do not have access to the test cases anyone has some advice into what could be happening? I think the idea should work since the centroid is the node that is in the "middle" of each tree.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Actually centroid decomposition isn't working here. Because, even if it's the "center", that doesn't mean that its the node that have average shortest path to all other nodes.
•  » » » 3 years ago, # ^ |   0 Thanks for the reply now I know the difference between centroid and center
 » 3 years ago, # |   0 The first approach of D1 can be implemented using linked list. The complexity will be O(n).Code here: Code
 » 3 years ago, # |   0 please someone explain how we can solve d2 question
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 I solved it using stack, the idea is that you need to always pair 2 elements in order to say that you can place a brick wall of size N which has to be divisible by 2 (this due to the 2x1 thing). The solution is something like this:Given P as the array of elements, and S the stack we have the following: if P[i] == S.top() we have a size 2 or divisible by 2 N , so we pop the top of S if S.empty() || P[i]!=S.top() , we have a new possible wall to take into account we push the element into S IF P[i]
•  » » » 3 years ago, # ^ |   0 Great explanation bro, thanks
 » 3 years ago, # |   +1 please explain me the logic of D1 I am not able to understand.
•  » » 3 years ago, # ^ |   0 Since you have a 2x1 block that you can either place horizontally or vertically, you then can assure this things: You can always increase the height of any element of the array by 2 even if it is by itself You can only increase the height by 1 if there are 2 elements connecting that create a segment , but as the size of blocks is 2 then it must be of even size Having that in mind then you can use the parity instead of the elements itself, lets take an example where the array is called P:1 2 2 3 As you can see on the case above you can increase P[1] because it pairs with P[2], but then you have an issue how can you pair P[0] with P[3]? well you increase 1 by 2 and it is 3, ok now a little thing, in math there are this rules: even + even = even odd + even = odd odd + odd = even even + odd = odd So if you assume that you can reach any increasing odd number from an odd number, and any increasing even number from an even number, then you can pair 1 and 3 for example or 2 and 10, then what matters is the parityIf you look above I explained how to solve problem D2 , here is the same deal the difference is that arrays are like this: 0 0 1 1The only change to the algorithm is that you do not need to check if P[i]
•  » » » 3 years ago, # ^ |   0 thank u so much bro ,this helps me a lot thank u
 » 3 years ago, # |   0 Can someone please tell me where my mistake is in problem E? I am doing exactly what the editorial says, but I'm using DFS instead of BFS to find the diameter and center, so maybe that's why it's wrong? Link — 47346955
•  » » 3 years ago, # ^ |   +6 dfs2 function won't return the center of the diameter in all cases (I'm too lazy to write a test for that) anyways, I've fixed dfs2 and it just worked fine. here it is
•  » » » 3 years ago, # ^ |   0 Thank you so much for helping me, I really appreciate it.
 » 3 years ago, # | ← Rev. 2 →   0 D1: when 'n' is odd does the bracket analogy still hold?? or what does that even mean then? obviously valid bracket sequences must be of even length, so I am a little confused. Can anyone please clarify??
 » 3 years ago, # |   0 Can someone please explain the logic for C problem in more detail?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 You have two strings with length n-1. Let them be a1,a2,a3,...,an-1 and b1,b2,b3,...bn-1. Then the final string is either a1,a2,...,an-1,bn-1 (if first string is prefix and second is suffix), or b1,b2,...,bn-1,an-1 (if second string is prefix and first is suffix). So, we can try both combinations. Let this combined string be s. Now how do we verify that s is correct? We should check all prefixes and suffixes of it, and if s is correct, we should be able to find that prefix or suffix in the other given strings from the input (remember that in the input we have all the prefixes and suffixes of every length).The constraints are small enough that you can use brute force.For example, here is how you would check if all prefixes are good (you should do this with all suffixes right after). s is the string we want to verify is correct. All strings from the input are stored in an array affixes. int status[210]; //status[i] = whether i-th string is unused(0), marked as prefix(1), or suffix(2) for (int i = 0; i < 2*n-2; ++i) status[i] = 0; bool ok = true; string pref = "", suff = ""; //check whether all prefixes of *s* can be found from the input for (int i = 0; i < n; ++i) { pref += s[i]; bool found = false; for (int j = 0; j < 2*n-2; ++j) { if (status[j] == 0 && pref == affixes[j]) { status[j] = 1; //number for prefix (see above) found = true; break; } } if (found == false) { ok = false; break; } } //similar code for suffixes //... if (ok) { //success, iterate over *status*, if status[i]=1, print 'P', otherwise print 'S' }
•  » » » 22 months ago, # ^ |   0 Can you give the link of your code? I tried but yet wrong verdict.
 » 3 years ago, # | ← Rev. 2 →   0 I was trying to solve Problem C but my answer is wrong for test 4, can anybody help??I have attached my solution Solution Link
 » 3 years ago, # |   0 For problem F, I think it would be more clear if you were to write the code for "undoing" the re-root operation as the "re-root" operation, but with v and to reversed: res -= sum[to]; sum[v] -= sum[to]; res += sum[v]; sum[to] += sum[v]; go(to, v); res -= sum[v]; sum[to] -= sum[v]; res += sum[to]; sum[v] += sum[to];
 » 3 years ago, # |   0 What will this block do in the Problem C solution ?else { assert(false); }
•  » » 3 years ago, # ^ |   0 Whenever there is a false statement within an assert block the program displays a Run time error and terminates . Since it is written in the problem statement that there is always a solution therefore the control will never be transferred to this block of code unless there exists no string and if that is the case then an error will be produced indicating to the user that there is some problem with the test data and not his logic. However run time error may arise due to other reasons too (obviously).
•  » » » 3 years ago, # ^ |   0 Thank you :)
 » 3 years ago, # |   0 I am not able to understand why i am getting WA on test 9 for question 1092D1. Link to my solution
 » 3 years ago, # |   0 What's wrong in my code for 1092C ? I got this error code on test case 9 wrong answer The number of 'P's and 'S's should be one and one for length 1
•  » » 3 years ago, # ^ |   0 Found the reason?
 » 3 years ago, # | ← Rev. 2 →   0 For problem D1,"Now imagine the following greedy solution. While you have some segment of the same parities of even length, fill it with horizontal bricks. This operation merges this segment with one to the left and to the right. If there is a single segment left then the answer is "YES". Otherwise it's "NO". The proof is left to the readers"Can anyone help me with the proof of this algorithm?. I am stuck with the proving part.
 » 3 years ago, # |   0 Hi, I am not sure if there is a problem with Problem C test case 14. My code produced an answer which is totally opposite to the required answer, but somehow I can't find out what's wrong. Can anyone help?This is my submission: https://codeforces.com/contest/1092/submission/54026479
 » 3 years ago, # |   0 @PikMike in problem F. You could easily see that sum[v] is nothing but total sum — sum[v] i.e. sum[1]-sum[v]; res=res+sum[1]-2*sum[v] then to reverse re root; use res-=sum[1]-2*sum[v]
 » 2 years ago, # |   0 Hi. Could someone please explain the diagnostics message that i am getting in testcase 17 for problem 1092C? I am not able to understand why my code is giving a runtime error. Here's my submission 78355872
•  » » 2 years ago, # ^ |   0 Never mind. I got it. It doesn't work with a testcase like "abb" as mentioned in one of the comments above by pikmike.
 » 23 months ago, # |   0 someone please help me in this problem: My approach for adding edge : cmp = find_all_reachable_from(1); for( i = 1 ; i <= n ; i++ ){ if( i is not in cmp ){ cmp1 = find_all_reachable_from(i) v1 = center_in( cmp ); v2 = center_in( cmp2 ); // add edge in v1 and v2 g[v1].push_back(v2); g[v2].push_back(v1); for( v in cmp2 ){ cmp.push_back(v); } } }
 » 23 months ago, # |   0 Explanation of problem A is mind blowing
 » 18 months ago, # |   0 Regarding the problem Prefixes and Suffixes. Can anyone tell me why my solution is wrong? I took inputs in a vector Sorted this vector according to length of strings Iterate over the sorted vector to check whether a given string v[i]. v[i].substr(0,v[i].length())==prefix till now If it can be then count the given string as a prefix and move ahead.Here is a link to my code