Блог пользователя awoo

Автор awoo, история, 6 лет назад, По-русски
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Разбор задач Educational Codeforces Round 31
  • Проголосовать: нравится
  • +46
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

Can anyone explain the max-flow solution of F?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +32 Проголосовать: не нравится

    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.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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)

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится -11 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +12 Проголосовать: не нравится

      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.

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    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://codeforces.com/contest/884/submission/33817504

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please post author's solutions.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

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