awoo's blog

Educational Codeforces Round 31 Editorial
By awoo, history, 7 years ago, translation, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +46
  • Vote: I do not like it

Comments Comments (15)
| Write comment?
»
7 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Can anyone explain the max-flow solution of F?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    You just add an additional color with 0 balls. Then you can always choose k = 3, and ignore the k = 2 case.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      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.

      → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    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.

    Solution: http://mirror.codeforces.com/contest/884/submission/33817504

    → Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please post author's solutions.

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    You can pick the groups as (4,4),(4,4,1),(4)= 21+8+9= 38

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it +5 Vote: I do not like it

        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).

        → Reply
»
7 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Can someone explain the solution of D ? How, it is proved to be working ? Can't understood from editorial.

→ Reply