PikMike's blog

By PikMike, history, 11 months 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  

»
11 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Can anyone explain the max-flow solution of F?

  • »
    »
    11 months 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.

»
11 months 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.

  • »
    »
    11 months 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.

    • »
      »
      »
      11 months 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.

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like 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.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

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

»
11 months 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.

  • »
    »
    10 months 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.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please post author's solutions.

»
11 months 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

  • »
    »
    11 months 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

    • »
      »
      »
      11 months 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?

      • »
        »
        »
        »
        11 months 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).

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
11 months 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.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.