### awoo's blog

By awoo, history, 4 years ago, translation, Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading... Tutorial of Educational Codeforces Round 31 Comments (19)
 » Can anyone explain the max-flow solution of F?
•  » » Build a flow graph where there is a vertex corresponding to each letter of the alphabet and 0.5n vertices corresponding to each pair of letters (si, sn - 1 - i). For each letter of the alphabet c, add an edge of capacity 1 to each of the 0.5n vertices, where the cost should be  - max(ai, an - 1 - i) if both characters are originally c, cost 0 of neither was equal to c, cost  - ai if only the i-th character is c and vice versa. Add an edge of cap cnti and cost 0 from sink to each letter, where cnti is the frequency of the i-th letter. Add an edge from each vertex denoting a pair with cap 2, cost 0 to sink. It is easy to see that the minimum cost of the min cost max flow is the negative of the answer.
•  » » » Setting the cost as you did only works because your know that if you are going to choose one of the two positions to have that value then it's better to choose the one with greater b_i, right?I modeled the same graph but I let the cost of that edges as 0 and changed the cost of the edge s_i to these extra nodes. If the extra node is connected to same character as s_i than edge from s_i to extra node has cost -b_i, otherwise it has cost 0.I think this is more intuitive since there are no greedy assumptions(sorry for the formatting, writing on phone makes it harder to edit properly)
 » Can you please explain the solution for problem-D in detail. Can you please explain what changes when n is even. I am still unable to to visualise the solution you told.
•  » » You just add an additional color with 0 balls. Then you can always choose k = 3, and ignore the k = 2 case.
•  » » » Hi, This has been told in the editorial. What I am asking is detailed understandable logic for problem D. If we are doing something then please explain why. I can't simply add additional color with 0 balls without understanding the reason behind it.
•  » » » » It is a simple greedy algorithm.We are asked to find the minimum penalty and to make it minimum we are taking out 3 colors of smallest numbers and adding it would give us a new number,insert this number to remaining colors and again choose three colors of smallest frequency.keep on doing it until and unless you are left with single number.One more thing every time you add three minimal numbers,add the resulting sum to your answer which is gonna be your penalty and your final answer in the end. And the reason he is using 0 when n is even because it generalizes the algorithm.Suppose you have n=5 first you would take three colors of minimal frequency,adding them would give us a new number so now again you have 3 colors and again you add them and finally left with single color where our algorithm ends.Using or adding 0 with even will help us to making group of three every time and adding zero to the penalty is not going to change our answer thats why he used 0.And he decided to make pair of three instead of two because making pair of two will increase the turn which means our penalty would also increase and not going to be minimum.So it is just a greedy algorithm choosing minimum will give us minimum.For more understanding you can learn huffman coding algorithm.I tried my best to explain the logic which i understood from editorial and after learning huffman coding algo.
•  » » Try to think of N=4 Case.Here we remove the 3 min balls and add 1, so from the first case we have 2 balls now and we can't handle such case without another ball, hence we add a ball of value 0.
•  » » 3 years ago, # ^ | ← Rev. 2 →   Let us reverse the problem, now we have to merge all the balls into single a box with calculation of answer being same. Greedily, we will pick 3 lowest size of boxes and merge them into a single box. When we are left with only 1 box we are done, but problem is when two boxes remain, now only way is to merge them, but we could do better than this, merge two boxes in the begining because they would weigh less than merging two boxes at end.
 » If D had a variable parameter m for k (So that k = 1, 2, 3, 4 ... m) can we adapt the same logic and add auxilary groups of 0 until the n % m = 0 to get the optimal solution? I'm not experienced with Huffman coding.
•  » » 4 years ago, # ^ | ← Rev. 2 →   I think we should make it n % (m - 1) = 1 to get the optimal solution. This way, you'll always use the k = m case to divide.
 » Please post author's solutions.
 » 4 years ago, # | ← Rev. 2 →   How is the answer of problem D third case is 38? 1, 1 4 4 4 4 4 -> 21 2. 1 4 4 4 -> 13 3. 1 4 -> 5 total number of balls picked: 39
•  » » You can pick the groups as (4,4),(4,4,1),(4)= 21+8+9= 38
•  » » » 4 years ago, # ^ | ← Rev. 2 →   can you please elaborate? at first turn, if I picked all 21 balls and put (4, 4) into 2 boxes, and put the rest into first box (because k=3), then I'm still left with 13 balls to sort at very least (21-8). How can you only pick 8 balls at next turn?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   Pick 21 balls and put it in 3 different boxes as - 1st Box — 4,4,1 2nd Box — 4,4 3rd Box — 4 Penalty — 21 Then you can split balls from 1st box to 1st,4th and 5th box with penalty 9(Total 30) and balls from 2nd box to 2nd and 6th box with penalty 8(Total 38).
•  » » This question is based upon Huffman coding problem which is a classic Greedy problem. In this problem if the given n is odd then during each iteration take 3 smallest elements from the given array of colors, add and combine them into a single node and add it back to your array. Make sure you delete their individual instances.So when you combine 3 in 1, you basically are deleting 3 and adding 1. So if n=7, you'll be left with 5 elements initially. Again repeat and you'll be left with 3 and then 1. This works fine if n is odd as it will follow the above pattern but if n is even we will be left with 2 in the end and adding this way will not guarantee the minimal answer. So let me explain the above approach with an example to clear things up. n=6 1 4 4 4 4 4 Here n is even so we add 0 to our set. Our set now looks something like this 0 1 4 4 4 4 4. Now combine the smallest 3 elements. Here 0,1,4 are the smallest 3. Combine them up and add it to our penalty. 0+1+4=5. So penalty=5 and our set now look like this 4 4 4 4 5. Repeat the above process till only 1 element is left in the set. After turn 2: set 4 5 12 and penalty=5+12=17 After turn 3 : set 21 and penalty=17+21=38 Hence 38 is the answer. If you're a CPP user then make use of multiset.
 » Can someone explain the solution of D ? How, it is proved to be working ? Can't understood from editorial.
•  » » This question is based upon Huffman coding problem which is a classic Greedy problem. In this problem if the given n is odd then during each iteration take 3 smallest elements from the given array of colors, add and combine them into a single node and add it back to your array. Make sure you delete their individual instances.So when you combine 3 in 1, you basically are deleting 3 and adding 1. So if n=7, you'll be left with 5 elements initially. Again repeat and you'll be left with 3 and then 1. This works fine if n is odd as it will follow the above pattern but if n is even we will be left with 2 in the end and adding this way will not guarantee the minimal answer.So let me explain the above approach with an example to clear things up.n=6 1 4 4 4 4 4Here n is even so we add 0 to our set. Our set now looks something like this 0 1 4 4 4 4 4.Now combine the smallest 3 elements. Here 0,1,4 are the smallest 3. Combine them up and add it to our penalty. 0+1+4=5. So penalty=5 and our set now look like this 4 4 4 4 5. Repeat the above process till only 1 element is left in the set.After turn 2: set 4 5 12 and penalty=5+12=17After turn 3 : set 21 and penalty=17+21=38Hence 38 is the answer. If you're a CPP user then make use of multiset.