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.
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?
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)?
cost function is same as of huffman coding cost function