### awoo's blog

By awoo, history, 2 years ago, translation,

1082A - Vasya and Book

Tutorial
Solution (Ajosteen)

1082B - Vova and Trophies

Tutorial
Solution (Ajosteen)

1082C - Multi-Subject Competition

Tutorial

1082D - Maximum Diameter Graph

Tutorial
Solution (PikMike)

1082E - Increasing Frequency

Tutorial

1082F - Speed Dial

Tutorial
Solution (PikMike)

1082G - Petya and Graph

Tutorial
Solution (Ajosteen)

• +68

 » 2 years ago, # |   -17 python 6-lines AC solution to problem B _, string = raw_input(), raw_input() start, end, res = 0, 0, 0 for char in string: if char == "G": start += 1 else: end, start = start, 0 res = max(res, start + end + 1) print min(res, string.count("G")) 
 » 2 years ago, # |   0 How to solve E
 » 2 years ago, # | ← Rev. 2 →   +2 For problem E, I came up with an elegant (at least I thought during contest) O(nlogn) divide-and-conquer solution. I am just surprised to see the so easy linear solution after contest...
•  » » 2 years ago, # ^ |   0 could you explain your solution please?
 » 2 years ago, # |   0 In problem D, why do we have to loop from the end of the array at the end of algorithm?I tried forward loop but gives WA on test 18... it seems that it doesn't construct tree well.
•  » » 2 years ago, # ^ |   0 +1. having the same issue
•  » » 2 years ago, # ^ |   0 So I just thought about it. The reason why the for loop needs to be done in reverse is because there is a chance that the very last node in the bamboo tree needs a "one" node to satisfy the diameter requirement that was previously calculated.Consider this test case 5 1 3 2 2 1 If you have both the bamboo construction for loop and the "ones add-on" for loop both go forwards, we'll add both one nodes to vertex 2 and never get the chance to append a one node to vertex 4 -- this would be required to make the diameter of the constructed graph 4, which would be the max.
•  » » » 2 years ago, # ^ |   0 Now I got it, for the construction of the bamboo we go forward and but then we must go backward to use all the remaining edges.
 » 2 years ago, # |   +1 Hello friends, Here is my solution to problem E. The pedagogy is quite different from the one in the editorial and it might be helpful. :)
 » 2 years ago, # | ← Rev. 2 →   0 My problem E solution is super simple.It might me helpful for you.https://codeforces.com/contest/1082/submission/46421135
•  » » 2 years ago, # ^ |   0 Can you explain it?
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 In one word, It is like a parallel two pointer for every number.For every 'i', you need to change left of some numbers that count(left, i, X) < count(left, i, C), to 'i'. But you don't need to immediately calculate it for every number. Because count(i, i, vec[i]) is always 1.Sorry for my bad English.
•  » » » » 2 years ago, # ^ |   0 No issues with your english but I couldn't get you
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Neighter do I. And it's really simple.
•  » » » » 2 years ago, # ^ |   -9 Especially this part. Can elaborate more? Because count(i, i, vec[i]) is always 1. 
•  » » » » » 2 years ago, # ^ | ← Rev. 5 →   0 If count(left, i, x) < count(left, i, c), we should change left to i. Then, its count is maybe 0. But We know answer always exist on some events increasing count about x. So, we don't have to change lefts immediatly. Therefore, If count(left, i, vec[i]) > count(left, i, c), we use it as it is. But else, we use it be changed about left. We can easily know we have to change left to i, and count(left, i, vec[i]) will be 1.Don't forget all x have different left.
•  » » » 11 months ago, # ^ | ← Rev. 2 →   +5 I will explain how I understood his code. Let's define an array $num$, where $num$ $a_i$ is maximum length of a subsequence like this: $c, c, \dots, c, a_i, \dots, a_i, a_i.$ This is the subsequence of first i elements of array $a$. So, how to calculate this array $num$? $if$ $a_i=c$ we do nothing $else$ $num$ $a_i$ $=$ $max($ $pref$ $i$ $,$ $num$ $a_i$ $)+1$ This way we are either $1)$ starting a new sequence by appending $a_i$ to the sequence of $c$. or $2)$ extending $c, c, \dots, c, a_i, \dots, a_i, a_i.$ by appendind $a_i$ to the end. How does it help? Let $pref$ $i$ be number of $c$ in the prefix of array $a$. Say, we are at an index $i$. When we subtract $pref$ $i$ from $num$ $a_i$ , we get $cnt(l,i,a_i) - cnt(l,i,c)$ where $l$ is the index of first $a_i$ in the above sequence. Now, we iterate through all $i$ and find the maximum of $cnt(l,i,a_i) - cnt(l,i,c)$. Finally we add this value to $pref$ $n$ which is our answer. Note: $cnt$ is the same as defined in the editorial.
 » 2 years ago, # |   0 Could someone explain why we need this line in problem B, res = min(res, cntG); Thanks.
•  » » 2 years ago, # ^ |   0 int nres = 1; we considered 'S' as 'G' to combine 'G' in the two sides, trying to get the longest subsegment. For examble:input 4 SGGGBefore res = min(res, cntG);, res = 4. It's an wrong answer.
•  » » » 2 years ago, # ^ |   0 Got it. Thank you. :)
 » 2 years ago, # | ← Rev. 2 →   0 Update :- Got it :)
 » 2 years ago, # |   0 In the first case, Vasya can go directly to the y page from the x page if |x−y| is divided by d.In the second case, Vasya can get to page y through page 1, if y−1 is divided by d. The required number of actions will be equal to ⌈x−1d⌉+y−1d.Similarly, in the third case, Vasya can go to the page y through the page n if n−y is divided by d. The required number of actions will be equal to ⌈n−xd⌉+n−yd.why this? Please anyone explain.
 » 2 years ago, # | ← Rev. 2 →   0 In problem D, I was wrong in test 18. The vecdict is "Given diameter is incorrect 388 389", but in my output the diameter is 389? Anyone tell me why? Thanks so muck
•  » » 2 years ago, # ^ |   0 The checker checks the diameter of your graph using your adjacency list, not just the diameter your output after "YES".
•  » » » 2 years ago, # ^ |   0 Thanks u!
 » 2 years ago, # |   +1 Here is my idea of E:We have a naive solution: consider each segment [l, r], get the maximum appearance of a number in the segment, assume it is x, then update result with cnt(1, l - 1, c) + x + cnt(r + 1, n, c), where cnt(l, r, j) is number of apperance of j in segment [l, r].In the solution above, for each segment [l, r], we choose the number with highest appearance and then change to c. But in fact, we can greedy change all the elements equal ar in segment [l, r]. Proof: If we choose the number with highest appearance, assume it is y, and y ≠ ar, then we can get better result if we choose segment [l, r'], where r' < r, cnt(r' + 1, r, y) = 0, y = ar', because cnt(r' + 1, n, c) ≥ cnt(r + 1, n, c) and cnt(l, r', y) = cnt(l, r, y), so cnt(1, l - 1, c) + cnt(l, r, y) + cnt(r + 1, n, c) ≤ cnt(1, l - 1, c) + cnt(l, r', y) + cnt(r + 1, n, c).So at the position i, let fai be the most number of c in segment [1, i] if you change all the elements equal ai to c in some segment [l, i]. Then: fai = max(fai + 1, cnt(1, i - 1, c) + 1). We update result with fai + cnt(i + 1, n, c).My submission: 46365450
•  » » 2 years ago, # ^ |   +5 I like this one. GJ
•  » » 2 years ago, # ^ |   +5 You saved my day
•  » » 2 years ago, # ^ |   0 I understand that all a[i] in (l,r) can change to a[r] but : why calculate cnt( 1,i ,d ) only not cnt(1,l-1,c) and cnt(l,r,d)sorry for my poor English....
•  » » » 2 years ago, # ^ |   0 At position i, fai is the maximum c we can get if we change all number equal ai in some segment [l,  i] to c. That means there is a segment [l,  i] which the sum cnt(1,  l  -  1,  c)  +  cnt(l,  i,  ai) is maximum and we suppose this sum equal fai. So we update result with cnt(1,  l  -  1,  c)  +  cnt(l,  i,  ai)  +  cnt(i  +  1,  n,  c)  =  fai  +  cnt(i  +  1,  n,  c).
•  » » 2 years ago, # ^ |   0 What a wonderful solution!!!!
•  » » 2 years ago, # ^ |   0 Why you can prove that it's optimal to change the elements equal ar in [l, r]? The proof seems to have only proved that changing ar' is better than changing ar. Could you please explain it in more detail?
•  » » » 2 years ago, # ^ |   0 I mean that changing all numbers equal ar' = y to c in segment [l, r'] is better than changing all number equals y (which have the most apperance) in segment [l, r].
•  » » » » 2 years ago, # ^ |   0 Got it! Thanks very much! : )
 » 2 years ago, # |   0 i used binary search for problem B
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Would you explain a bit how you used Binary Search?
•  » » » 2 years ago, # ^ |   0 46471253here it is.
 » 2 years ago, # |   0 Can anybody tell me why my code for problem C is giving WA?The link to my code : https://codeforces.com/contest/1082/submission/46672149
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Your solution gives wrong answer on test like: 2 2 1 1 2 -1 
•  » » » 2 years ago, # ^ |   0 Thanks man.
•  » » » » 2 years ago, # ^ |   0 What should be the output of this?
•  » » » » » 2 years ago, # ^ |   +1 It should be 1
 » 2 years ago, # |   0 Someone please help me with problem C. I couldn't understand the problem.
 » 2 years ago, # |   -6 What is the time complexity of problem C?
 » 2 years ago, # |   0 can ANYONE give easier tutorial on prob G?
 » 2 years ago, # |   0 This editorial isn't linked from problems but only from the announcement so it's a bit harder to find.
•  » » 2 years ago, # ^ |   0 Oops, sorry, now it's linked.
 » 2 years ago, # |   0 In explanation to Problem G:"if a project-vertex belongs to S, then we take this project; if an instrument-vertex belongs to S, then we take this instrument; all other projects and instruments are discarded..If an edge between some project and some instrument is cut, then it means that the answer is incorrect (we try to take a project requiring some instrument we don't take), and the cut value is infinite. Otherwise, the value of the cut is equal to the total cost of taken instruments and discarded projects, and we need to minimize it." I didn't get what this means. Once we determine Minimum cut from the graph, it says discard all projects and instruments that are not part of the cut. But then it also states value of the cut is equal to total cost of instruments and discarded projects. Also, how can the cut value be infinite if all edges from source to projects have finite capacity and all edges from instruments to sink have finite capacity? Can someone please explained with an example or in a simpler way. Thanks.
 » 2 years ago, # | ← Rev. 2 →   0 B (1082B — Vova and Trophies) can also be solved with two pointers using constant additional memory. The idea is to find the longest substring with at most 1 silver (character S).Submission: 54993169
 » 12 months ago, # |   0 I am currently failing test 11 for prob D. This is my solution https://codeforces.com/contest/1082/submission/80575032. Can anyone please tell me what is wrong with it?
 » 8 months ago, # |   +3 .