### awoo's blog

By awoo, history, 5 years ago, translation,  Tutorial of Educational Codeforces Round 31 Comments (20)
 » 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.