Hyper-Box

Today its going to be an easy problem as I couldn't manage time to solve anything harder. Its problem C of Dhaka Regional; 3rd most easiest problem of the set.

The problem requires you to

build an N dimensional hyper box using N dimensional hyper bricks whose length in any dimension can only be a Fibonacci number. You have to calculate minimum of bricks you'll need. N can be at most 15 and the length of any dimension of the hyper box can be 2*10^9.

First few numbers of Fibonacci sequence are -

1, 2, 3, 5, 8, 13, 21, 34, 55.....

So, if N = 3, you can use bricks of size (8,2,55) or (1,2,3), but you cannot use (1,5,10) as 10 is not a Fibonacci number.



The problem seems intimidating at first look as you have to think about more than 3 dimensions. Lets just work out from lower dimensions. Say N=2 and dimension of the hyper box is (12,10). Now we will require at least 3 Fibonacci numbers to make 12 - 8+3+1 or 8+2+2 and we will require 2 to make 10 - 8+2. Illustration below -

As we can see, we will require 6 bricks here, of sizes (8,8), (3,8), (1,8), (8,2), (3,2) and (1,2).

Now, lets say N=3 and dimension of hyper box is (12,7,6). Now we can split the box in 3 separate boxes - (8,7,6), (3,7,6) and (1,7,6). Each of the boxes will require us to find optimal solution for a 2D box of size (7,6). So, we can easily see that to get the minimum number of bricks to build the hyper box, we have to optimally build each dimensions of the box and then multiply them all.

The question now is how to represent a number as a sum of minimal number of Fibonacci numbers. It can be proved mathematically that in such a representation, we will always take the closest Fibonacci number to the sum to be built.

Source code -

/*
Problem Name : Hyper Box
Problem Number : Archive 4855
Link   : http://acm.uva.es/archive/nuevoportal/region.php?r=as9&year=2010
Problemsetter : Abdullah al Mahmud
Problem Type : Math, Greedy
Difficulty  : 4 / 10
Interest  : 6.5 / 10
Complexity  : O(NlogL)
Date   : November 13, 2010
*/

#include<stdio.h>

#define rep(i,n) for(i=0;i<(n);i++)
#define i64 long long

int N;
i64 fib[100];

int solve(i64 L) {
 if(L == 0) return 0;
 int i;
 rep(i,100) if(fib[i] > L) return 1 + solve(L-fib[i-1]);
}

int main() {
 int T,kase=1;
 int i;
 i64 res;
 i64 len;

 fib[0] = 1; fib[1] = 2;
 for(i=2;i<100;i++) fib[i] = fib[i-1] + fib[i-2];

 scanf(" %d",&T);
 while(T--) {
  scanf(" %d",&N);
  res = 1;
  rep(i,N) {
   scanf(" %lld",&len);
   res *= solve(len);
  }
  printf("Case %d: %lld\n",kase++,res);
 }
 return 0;
}