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.

Digital Matrix

For the 3rd day in a row, I'm solving a problem from recent Dhaka regionals. This time it is problem F - Digital Matrix. It is a very tricky ad hoc problem. No team could solve it during the real time contest. Fudan University came closest to solving it with their solution giving wrong output on only one type of cases. It took them 13 submissions though to come that close.

The problem states that

You are given two N x N square matrices, A and B. Each of the elements of these matrices is an integer between 1 and K (inclusive). You have to convert matrix A into matrix B in minimum number of operations. In each operation you can choose one element of matrix A and change it to any integer between 1 and K (inclusive). You have to ensure that after any operation the matrix is not converted to a symmetric matrix.

Knockout Tournaments

This problem is also from recent Dhaka Regional contest. Problem link -
http://acm.uva.es/archive/nuevoportal/region.php?r=as9&year=2010

The problem in short would be

For a number of tennis tournaments, each consisting of 8 rounds, you are given total number of wins (W) and losses (L). You have to find your average performance (round you reached) considering all possible scenarios. Two scenarios are different if the number of tournament played is different. W and L both are between 0 and 2*10^8.

Halloween Costumes

This is a problem from recently held ACM ICPC Dhaka Regionals. You can find the problem here -
http://acm.uva.es/archive/nuevoportal/region.php?r=as9&year=2010

The problem can be reduced to this -

Find minimum number of push operations needed to build a number sequence by printing the top element of the stack.

For example, if the sequence to be built is -

1 2 1 1 3 2 1 

We can do it through the following steps -