Türkçe

Bu problemi çözerken Huffman Encoding Tree'yi kullanacağız.

Neden

Problemde X fiyatını seçmenin \(2^{(N-X)}\)(token hard için \(K^{(N-X)}\)) puan tuttuğunu söylemiştik. Bundan dolayı A fiyatını bir ürün türü için seçmenin puan giderinin A+1,A+2,A+3,...,A+B,... fiyatlarının puan giderlerinin sırasıyla 2,4,8...,\(2^{B}\),...(token hard için K,\(K^{2}\),\(K^{3}\)...,\(K^{B}\),...) katı olduğundan dolayı herhangi bir fiyatı herhangi bir ürün türü için seçmek ondan yüksek fiyatları seçme kapasitenizi 2 fiyatın arasındaki farka göre üstel olarak azaltacaktır. Bu nedenden ve problemde her ürün türü için seçilecek fiyatı optimize etmeniz gerektiğinden dolayı sorudaki her ürün türünü bir full Tree'nin yaprakları olacak şekilde düşündüyseniz, sorunun aslında Huffman'ın encoding algoritmasıyla çözülebileceğini farketmişsinizdir(token easy için binary(normal huffman tree) token hard için ise huffman'ın K-ary Tree'sini kullanmanız gerekiyor ve token hardda ilk oluşturulan iç node hariç tüm nodelarımız tam olarak K farklı node a bağlanıyor).

Soruyu çözerken aynı algoritmayı 2 farklı yaklaşım üstünden giderek uygulayacağız.

2'inci çözüm Code 1'in altındadır.

Çözüm-1

Sorunun kolay versiyonunu çözerken ,ürünlerin her birinin tree içindeki yüksekliği Ada'nın o ürün türü için birim fiyatını bize vereceği, Binary Huffman Tree'yi oluşturmamız gerekiyor. Bu yüzden ilk olarak her ürüne karşılık gelen yaprağın ağırlığını o üründen almamız gereken sayı(\(a_i\)) olarak atıyoruz. Huffman tree(tree'yi optimal tutmak adına) aşağıdan yukarıya doğru önce iç nodeları oluşturup en son kökü oluşturacak şekilde implemente edilir. Binary Huffman tree yi oluştururken her adımda yeni oluşturacağımız nodeların çocuk nodelarını daha önce seçilmemiş nodelardan en düşük ağırlığa sahip olan 2'si olarak seçip onların ağırlığı toplamını yeni node'umuzun ağırlığı olarak belirliyoruz. Bu işleme sadece tek bir nodeumuz(kök) kalana kadar devam ediyoruz. Daha sonra treedeki ürünlerimizin(yapraklarımız) yüksekliklerini(o ürün türü için birim fiyatı), ağırlıklarıyla çarpıp(o üründen almamız gereken miktarla çarpıp(\(a_i\))) daha sonra bu değerleri toplayarak ödenebilecek mininmum fiyatı buluyoruz.

Açıklama-1

Tree'nin bu şekilde oluşturulmasının nedeni fiyatın ağırlığa bağlı olması. Her adımda çocuk olarak seçilmiş olan nodelar ve çocuk olarak seçilmiş olan node'un soyundan gelen nodelarının yüksekliği 1 birim artacağı için onların fiyatlarını da bir birim arttırmış oluyoruz. Kısacası her adımda aslında o ana kadar seçilmiş olan nodelarla birçok huffman tree oluşturuyoruz ve her adımda 2 tree'yi birleştirip her treedeki ürün türlerinin birim fiyatını 1 arttırarak yapıyoruz. Bu yolla, en düşük ağırlığa sahip olan ürün türündeki ürünler, toplamda ödenecek fiyatı optimize edecek şekilde daha yüksek fiyatlara satılıyor.

Dikkat edilmesi gerekenler-1

• Toplamda N adet yaprak nodeumuz(ürün türü) olduğu için ve her adımda 2 node kullanıp 1 node ürettiğimizden dolayı (-2+1=-1)her adımda kullanabileceğimiz node saysı 1 azalıyor. Bu işlemi toplamda N-1 kere yapmamız gerekiyor ve her işlemde bir iç node üreterek N-1 inernal node üretmiş oluyoruz.
• N tane yaprak N-1 adet iç node umuz olduğundan dolayı Huffman Encoding Tree nin toplamda 2N-1 adet node u bulunuyor.

English

We will use Huffman Encoding Tree to solve this problem.

Reason

In the problem, we said that choosing the price of X costs \(2^{(N-X)}\)(\(K^{(N-X)}\) for token(hard)) points. Therefore, the point expense of choosing price 'A' for a product type is calculated as 2,4,8...,\(2^{B}\),...times(K,\(K^{2}\),\(K^{3}\)...,\(K^{B}\),... times for token(hard)) the point expense of A+1,A+2,A+3,...,A+B,... . Because of that choosing a price will exponentially reduce your capacity to select higher prices by the difference between these 2 prices. For this reason and because you have to optimize the price to be selected for each product type, If you thought each product type as a leaf of a full tree, you might have realized that the problem can actually be solved by Huffman's encoding algorithm(For token(easy) you need to use Binary Huffman Tree (normal Huffman Tree) for token(hard), you need to use Huffman's K-ary Tree and for token hard, except for the first node created, all our nodes connect exactly to K different internal nodes.).

We will apply the same algorithm with 2 different approaches.

2nd solution is below Code-1.

Solution-1

While solving the easy version of the problem, we need to create the Binary Huffman Tree, where the height of each product type in the tree will represent the price that needs to be paid for that product type's unit price. Therefore, first we assign the weights of the leaves as the number of times we need to buy that product type(\(a_i\)). Huffman tree (to keep the tree optimal) is implemented from the bottom up. This way the internal nodes will be created first and root would be created in the last step. This way the internal nodes will be created first and root would be created in the last step. While creating the Binary Huffman tree, we select the child nodes of the new node, from haven't already been selected 2 nodes that has the lowest weight and determine the now created node's weight as the sum of its child nodes's weights. You will need to continue this process until there is only one node left(root). Then we multiply the heights of our leaves(unit price) by their weights(the amount we need to buy(\(a_i\))). At last we will add these values to get the total optimal price.

Explanation-1

The reason for creating the tree this way is because prices depend on weights. Since the height of the nodes selected as child noes and the descendent nodes of those nodes at each step will increase by 1 unit, we are actually increasing their prices by one unit. In short, at each step, we are creating multiple huffman trees with the nodes that have been selected so far and we combine 2 trees at each step and increase the unit price of the product type by 1. IN this way, products of the product type with the lowest weight are sold at higher prices to optimize the price to be paid in total.

Important Information-1

• Since we have N leaf nodes (product types) in total and we use 2 nodes at each step and produce 1 node (-2 + 1 = -1), the number of nodes we can use at every step will decrease by 1. Because of that we have to perform this process total of N-1 times and will produce N-1 internal nodes by producing one internal node in each step.
• since we have N leafs and N-1 internal nodes, our Huffman Encoding Tree will have 2N-1 nodes in total.

Code-1

#include <iostream>
#include <algorithm>
using namespace std;

#define ll long long

struct Node{
    ll number;
    Node *left,*right;
    Node(ll val=0,Node *l=nullptr,Node *r=nullptr):number(val),left(l),right(r){};
};

bool comparator(Node a,Node b){
    return a.number<b.number;
}

ll TOTAL_SIZE(Node *r,int height){
    if(!r)return 0;
    if(!r->right&&!r->left)return r->number*height;
    //ENGLISH: If node is a leaf returning the total price that will be paid for those products. 
    //TURKISH: Eğer node'umuz leaf ise onun için toplam ödenecek miktarı dönüyoruz.
    return TOTAL_SIZE(r->left,height+1)+TOTAL_SIZE(r->right,height+1);
}




int main()
{
    ll n;
    cin>>n;
    Node array[2*n-1];
    for(Node *i=array;i<array+n;i++)cin>>i->number;
    sort(array,array+n,comparator);
    for(int i=0;i<n;i++)cout<<array[i].number<<" ";
    cout<<endl;

    Node *min_array[2]{array,array+1};
    //ENGLISH: Selecting first minimum node array.
    //TURKISH: İlk Minimum node arrayi seçiliyor.
    Node *current=array+n,*notleaf=array+n,*isleaf=array+2;            
    for(int i=0;i<n-1;i++){                           
        current->number=min_array[0]->number+min_array[1]->number;
        current->left=min_array[0];
        current->right=min_array[1]; 
        current++;

        for(int j=0;j<2;j++){
            if(isleaf>=array+n){
                min_array[j]=notleaf;
                notleaf++;
            }
            else if(notleaf>=current){
                min_array[j]=isleaf;
                isleaf++;
            }
            else{
                if(isleaf->number<notleaf->number){
                    min_array[j]=isleaf;
                    isleaf++;
                }
                else{
                    min_array[j]=notleaf;
                    notleaf++;
                }
            }
        }
        //ENGLISH: We are choosing minimum 2 nodes from all of the nodes that haven't been chosen before
        //TURKISH: Daha önce seçilmemiş nodelar arasından en düşük değerlere sahip 2 node u seçiyoruz
    }

    cout<<TOTAL_SIZE(&(array[2*n-2]),0)<<endl;
    //ENGLISH: We are sending the root of the tree that resides in array[n+operations-1]
    //TURKISH: TOTAL_SIZE fonksiyonuna rootu array[n+operations-1] de olan rootu yollayıp çıkan cevabı yazdırıyoruz
}

Turkish

2'inci çözümü okumadan önce 1'inci çözümü ve açıklamasını okumanızı öneririz.

Çözüm-2

Bu çözümde tüm ürünlerin alım miktarlarını priority queueya ekleyerek başlıyoruz(bu değerler tree mizin yaprak nodelarının ağırlığını oluşturuyor). Sonra, priority queueda tek bir sayı kalana kadar(kökün ağırlığı) her adımda elimizdeki en düşük 2 ağırlığı priority queuedan çekip toplamlarıyla oluşturduğumuz yeni ağırlığı(iç nodeun ağırlığı) tekrar priority queueya ekleyerek oluşturuyoruz.

Bu çözümü uygularken her adımda iç nodeları oluştururken öbür nodeları kaybettiğimiz için ve nodeların çocuk nodelarını kaydetmediğimiz için her ürünün birim fiyatını, ürününün bulunduğu heighttan bulamayız. Fakat Huffman Encoding Treenin önemli bir özelliğini kullanabiliriz. Huffman Treelerde bir nodeun ağırlığı(yaprak node olmadığı sürece) çocuklarının ağırlığı toplamına eşittir ve her treedeki her nodeun ata sayısı, nodeun yüksekliğine eşit olduğu için: Yüksekliği h olan herhangi bir nodeun ağırlığının eklenmiş olduğu h adet atası bulunmaktadır. Bu yüzden toplam harcanan miktarı bulmak için tek yapmamız gereken her adımda oluşturduğumuz iç nodeları toplamak olacaktır çünkü bunu yaptığımızda asıl yaptğımız şey her nodeun ağılığını(alım miktarı) o node'un yüksekliği kadar eklemektir.

English

We recommend that you read solution 1 and its explanation before reading solution 2.

Solution-2

In this solution, we start by adding the given purchase amounts of products to the priority queue (these values are weights of the leaf nodes in our tree). Then, in each step, we take and add the lowest 2 weights from the priority queue and add the new weight(the weight of the inner node) back to priority queue until there is only one number(root) left in the priority queue.

We cannot find the unit price of each product from the height of the product, since we pop child nodes while creating their parent nodes at each step. But we can use an important property of Huffman Encoding Trees. In Huffman Trees, the weight of a node is equal to the total weight of its children (unless that node is a leaf node), and since the number of ancestors of each node in a tree is equal to the height of that node: Any node with a height of h has h ancestors to which its weight was added. So we can find minimum price to pay in total by just adding the internal nodes we create at every step since by doing that we would be adding their weights(purchase amounts) h times.

Code 2

#include <iostream>
#include <queue>

using namespace std;
#define ll long long


int main()
{
    ll n;
    cin>>n;

    ll temp;
    priority_queue<ll,vector<ll>,greater<ll>> pq;
    for(int i=0;i<n;i++){
        cin>>temp;
        pq.push(temp);
    }

    ll next,res=0;
    while(pq.size()!=1){
        next=pq.top();
        pq.pop();
        next+=pq.top();
        pq.pop();
        //ENGLISH: Next is the newly created internal node
        //TURKISH: Next yeni üretilmiş iç nodetur

        res+=next;
        //ENGLISH: By adding internal node weights we are actually adding every leaf node h times.(h is that node's height)
        //TURKISH: İç node ağırlıklarını ekleyerek aslında her yaprak nodeun ağırlığını h kez eklemiş oluyoruz. (h, node yüksekliğidir)
        pq.push(next);
    }

    cout<<res<<endl;

}