Türkçe

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

Neden

Problemde X fiyatını seçmenin \(K^{(N-X)}\)(token easy için \(2^{(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 K,\(K^{2}\),\(K^{3}\)...,\(K^{B}\),...(token easy için 2,4,8...,\(2^{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 zor 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, K-ary 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 miktar(\(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. K-ary 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 K tanesi(ilk oluştuduğumuz nodedaysa bu sayı girilen N ve K değerlerine göre 2 ile K arasındaki herhangi bir sayı olabilir) 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 minimum 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 K tree'yi(ilk adım hariç(ilk adımda 2 treeden K tree ye kadar her sayıda tree birleşebilir)) 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 ilk adım dışındaki her adımda K node kullanıp 1 node ürettiğimizden dolayı (-K+1=-(K-1)) her adımda kullanabileceğimiz node sayımız K-1 azalıyor. Bu, nedenden ilk üreteceğimiz node'un çocuk sayısını FIRST=N%(K-1) işlemiyle rahatça bulabiliriz. Fakat burda dikkat etmemiz gereken 3 farklı edge case bulunuyor.

  • FIRST=0: İç node oluşturacağımız için çocuk sayısı asla 0 olamaz. Burda sonucumuzun 0 gelmesinin nedeni aslında ilk oluşturacağımız nodeun K-1 çocuk node a sahip olmasının gerekmesi. Matematiksel olarak 0(mod K-1)=K-1 olduğu için bu bu değeri K-1 ile değiştirilmeli
  • FIRST=1: Oluşturacağımız iç node un tek çocuğu olacaksa aslında o iç node'a ihtiyaç duymadığımızı rahatlıkla fark edebilirsiniz. Burda 1 elde etmemizin nedeni N%(K-1) işleminin verebileceği sonuç kümesinin 0,1,2,...,K-2 olması bu yüzden doğru miktardaki çocuk sayısını bulmak için bir önceki edge case teki gibi 1(mod K-1)=K olduğu için 1 deperi K ile değiştirilmeli.
  • K=2: K mız 2 olduğunda(binary) N%(2-1) her zaman 0 çıkacaktır fakat tüm işlemlerde 2 adet seçilmemiş node umuz olacağından bu sayıyı 2 ile değiştirmeniz gerekecektir.

• ilk adımın sonunda elimizdeki node sayısı tam olarak K-1 in katı olacağından toplam işlem saysı ve toplam iç node sayısı OPERATONS=1+(N-FIRST)/(K-1) işlemiyle bulunabilir.(1+(N-FIRST)/(K-1) teki 1, ilk adımda elde ettiğimiz node u simgeliyor)

Not: Soru modelini gözlemleyerek iç node sayısını OPERATONS=1+(N-2)/(K-1) işlemiyle de hesaplanabildiğini fark etmiş olabilirsiniz. Bunun neden sağladığı aşağıda matematiksel olarak gösterilmiştir:

• FIRST ∈ {2,3,...,K}

• N=(K-1)*X+FIRST                                         N i daha önce bulduğumuz FIRST=N%(K-1) işlemi ve modülüsün tanımını kullanarak keyfi bir X değişkeniyle bu şekilde de yazabiliriz.

  • operations=1+(N-FIRST)/(K-1)
  • operations=1+(K-1)*X/(K-1)
  • operations=X+1

• N=(K-1)*X+FIRST                                          olduğundan dolayı

  • N-2=(K-1)*X+(FIRST-2)             olduğunu da söyleyebiliriz ve FIRST-2 ∈ {0,1,...,K-2} olduğundan dolayı K-1 e bölümü bize her zaman 0 verecektir bu yüzden
  • 1+(N-2)/(K-1)
  • =1+((K-1)*X+(FIRST-2))/(K-1)
  • =1+((K-1)*X/(K-1))+((FIRST-2)/(K-1))
  • =1+X+0=X+1                                 her zaman X+1 değerini vereceğinden OPERATONS=1+(N-2)/(K-1) her zaman doğru iç node sayısını verecektir.

English

We will use K-ary Huffman Encoding Tree to solve this problem.

Reason

In the problem, we said that choosing the price of X costs \(K^{(N-X)}\)(\(2^{(N-X)}\) for token(easy)) points. Therefore, the point expense of choosing price 'A' for a product type is calculated as K,\(K^{2}\),\(K^{3}\)...,\(K^{B}\),... times(2,4,8...,\(2^{B}\),... times for token(easy)) 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 K-ary 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 bottom up. 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 K nodes(For the first node we create, this number can be any number between 2 and K according to the N and K values entered.) 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). After this process is done, you would need to multiply the heights of leaves(unit price) by their weights(the amount we need to buy(\(a_i\))). At last, you 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 K(except for the first operation(In first operation, every number of trees from 2 to K can be combined)) 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 K nodes at each step and produce 1 node (-K + 1 = -(K-1)), the number of nodes we can use at each step decreases by K-1. This is why we can easily find the number of children of the first node we will produce by using FIRST=N%(K-1). But here are 3 edge cases that we need to pay attention to. Which are:

  • FIRST=0: Since we aim to create an internal node, the number of children can never be 0. The reason why our result is 0 here is that the first node we will create must have a K-1 child node. Mathematically, this value should be replaced by K-1 since 0(mod K-1)=K-1
  • FIRST=1: If the internal node that we will create, will have only one child, you can easily realize that we do not actually need that internal node. The reason we got 1 here is that the results we can get from N%(K-1) can never be higher then or equal to K-1. So to find the right number of children, we need to add K-1 to it and make it K, as we did in the previous edge case since 1(mod K-1)=K.
  • K=2: When K is 2 (binary) N%(2-1) will always be 0, but since we will have at least 2 unselected nodes in all steps, you will need to replace this number with 2.

• Since the number of nodes we have at the end of the first step will be exactly a multiple of K-1, the total number of steps and the total number of internal nodes can be found by using OPERATONS=1+(N-FIRST)/(K-1). (1 in 1+(N-FIRST)/(K-2) represents the node we created in the first step)

• Note: By observing the question model, you might have noticed that the number of internal nodes can also be calculated with the operation OPERATONS=1+(N-2)/(K-1). The mathematical reason for this is given below:

• FIRST ∈ {2,3,...,K}

• N=(K-1)*X+FIRST                       We can also write N in this way with an arbitrary variable X, using the definition of modulus and the operation FIRST=N%(K-1) which was found earlier.

  • operations=1+(N-FIRST)/(K-1)
  • operations=1+(K-1)*X/(K-1)
  • operations=X+1

• since N=(K-1)*X+FIRST we can easily see that

  • N-2=(K-1)*X+(FIRST-2) and since FIRST-2 ∈ {0,1,...,K-2} is always less then K-1 (FIRST-2)/(K-1) will always be 0. And Because of that:
  • 1+(N-2)/(K-1)
  • =1+((K-1)*X+(FIRST-2))/(K-1)
  • =1+((K-1)*X/(K-1))+((FIRST-2)/(K-1))
  • =1+X+0=X+1      so we can easily see thatOPERATONS=1+(N-2)/(K-1) will always give us the number of internal nodes.

Code-1

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

#define ll long long

int k;      //Our tree will be k-ary tree

struct Node{
    ll number;
    Node **children;
    Node(ll val=0):number(val){
        children=new Node*[k];
        for(int i=0;i<k;i++)children[i]=nullptr;
    }
};

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

ll TOTAL_SIZE(Node *r,int height){
    if(!r)return 0;
    if(!r->children[0])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.

    ll res=0;
    for(int i=0;i<k;i++){
        if(r->children[i])res+=TOTAL_SIZE(r->children[i],height+1);
    }
    return res;
}



int main()
{
    ll n,operations;   
    cin>>n>>k;        
    //ENGLISH: k is a gloabal variable. Its initialized at top.
    //TURKISH: k yukarda global olarak tanımlandı.

    ll first=n%(k-1);
    if(first<=1)first+=k-1;             
    if(k==2)first=2;
    //ENGLISH: number of nodes that will be the child of first created node
    //TURKISH: İlk oluşturacağımız node'un çocuk sayısı

    operations=1+(n-first)/(k-1);
    //ENGLISH: It could have also been 1+(n-2)/(k-1)
    //TURKISH: 1+(n-2)/(k-1) de olabilirdi

    Node array[n+operations];
    for(Node *i=array;i<array+n;i++)cin>>i->number;
    sort(array,array+n,comparator);

    bool flag=1;

    Node *min_array[k];
    for(int i=0;i<first;i++)min_array[i]=array+i;
    //ENGLISH: Selecting first minimum node array.
    //TURKISH: İlk Minimum node arrayi seçiliyor.
    Node *current=array+n,*notleaf=array+n,*isleaf=array+first;

    for(int i=0;i<operations;i++){
        if(flag){
            flag=0;
            for(int j=0;j<first;j++){
                current->number+=min_array[j]->number;
                current->children[j]=min_array[j];
            }
        }
        else{
            for(int j=0;j<k;j++){
                current->number+=min_array[j]->number;
                current->children[j]=min_array[j];
            }
        }
        //ENGLISH: Creating a new node from now chosen minimum node array.
        //TURKISH: Üstte yeni seçilmiş olan minimum node arrayinden yeni bir node oluşturuluyor.
        current++;

        for(int j=0;j<k;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 K 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 K node u seçiyoruz
    }

    cout<<TOTAL_SIZE(&(array[n+operations-1]),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
}

Türkçe

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 K ağırlığı(ilk adım hariç) 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 fiyatı 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.

Dikkat edilmesi gerekenler-2

• Dikkat edilmesi gerekenler-1 deki ilk kural(FIRST hesaplanması) burdada geçerli ve gereklidir.

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 K weights(except in the first step) 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.

Important Information-2

• First Rule in Important Information-1 (FIRST calculation) is also neccessery here.

Code 2

#include <iostream>
#include <queue>

using namespace std;
#define ll long long


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

    ll first=n%(k-1);
    if(first<2)first+=k-1;
    if(k==2)first=2;
      //ENGLISH: First is the number of chidren the first created internal node will have
      //TURKISH: First ilk oluşturulacak iç node'un çocuk sayısıdır
    bool flag=true;

    ll next,res=0;
    while(pq.size()!=1){
        if(flag){
            flag=false;
            next=0;
            for(int i=0;i<first;i++){
                next+=pq.top();
                pq.pop();
            }
            res+=next;
            pq.push(next);
        }
        else{
            next=0;
            for(int i=0;i<k;i++){
                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;

}