FifthThread's blog

Help in greedy problem which I am unable to do
By FifthThread, 3 years ago, In English

Hello everyone. Recently I encountered an interesting problem which I believe could be done by greedy strategy but I am not sure how. Can you help me to proceed?

The problem is as follows:

You are given 2n alphabets a_1, a_2, ..., a_{2n} with positive frequencies f_1, f_2, ..., f_{2n} respectively. (We assume that f_1 + f_2 + ... + f_n = 1.)

Alphabets a_1, a_2, ..., a_n are colored blue, and alphabets a_{n+1}, a_{n+2}, ..., a_{2n} are colored red.

A prefix-free code C for {a_1, a_2, ..., a_{2n}} is called valid if and only if every subtree of Trie(C) with at least two leaves has equal number of blue and red alphabets.

Give an algorithm to find a valid prefix-free code of minimum cost.

Thanks for helping me out.

  • Vote: I like it
  • -19
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Isn't this the same problem that the following blog mentioned four days ago?

Greedy algorithms — Interesting problem

Can you share the link to the problem if it is available in public domain?

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

How is the cost function of the valid prefix-free code C defined? Is it equal to the number of nodes of Trie(C) or equal to the height of Trie(C)?

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

    cost function is same as of huffman coding cost function

    → Reply