SRM 669 Div1 250: Subdivided Slimes

After one turn, the maximum number of mascots that we can get is . That suggest a greedy algorithm: In each step chose the largest slime, and divide it in two almost equal parts. Unfortunately this algorithm is wrong (it made me lose a lot of time trying to find a proof). Here is a counterexample: .

The next idea that I came up was that maybe there exists an optimal way of cutting the slimes such that after k turns, the resulting slimes are almost equal (Note that this is true for ).

Let’s think backwards. If after k turns the sizes of the slimes are , then which is the maximum number of mascots that we can get? The process of cutting slimes determines a binary tree, the root is the initial slime, and the two children of a node are the resulting slimes after cutting that node. Let be the left and right child of the root respectively, then [ max mascots from root = max mascots from u + max mascots from v + size of u * size of v ]. With that in mind you can prove that the maximum number of mascots that we can get is

So the problem is how to divide S in many parts () such that the sum of the products of pairs is maximized. Let’s suppose that is an optimum partition, if we increase by one and decrease also by one then the change in the number of mascots is . That means that if we can find to elements such that then we can improve that solution. Therefore, the optimum partition is when all the elements are almost the same (when the difference between the maximum and minimum is at most 1).

My awesome implementation:

#include<bits/stdc++.h>
typedef long long int uli;
using namespace std;

class SubdividedSlimes {
	public:
	int needCut(int s, int m) {
      uli d[2000];
      uli ans=-1;
      for(int k=2;k<=s;k++){
         uli v=s;
         for(int i=0;i<k;i++){
            d[i]=v/(k-i);
            v-=d[i]; 
         }
         uli pets=0;
         uli maxi=d[k-1];
         for(int i=k-2;i>=0 && pets<m;i--){
            pets+=maxi*d[i];
            maxi=maxi+d[i];
         }
         if(pets>=m){
            ans=k-1;
            break;
         }
      }
      return ans;
	}
};