PikMike's blog

By PikMike, history, 3 weeks 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  

»
3 weeks ago, # |
  Vote: I like it +24 Vote: I do not like it

Can anyone explain the max-flow solution of F?

  • »
    »
    3 weeks 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.

»
3 weeks 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.

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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.

  • »
    »
    13 days 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.

»
3 weeks 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.

  • »
    »
    9 days 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Please post author's solutions.

»
3 weeks 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

  • »
    »
    3 weeks 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

    • »
      »
      »
      3 weeks 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?

      • »
        »
        »
        »
        3 weeks 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).

  • »
    »
    7 days 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.

»
3 weeks 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.

  • »
    »
    7 days 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.