Getting back to more programming after an inspirational summer camping trip. Saw one of my friends attempting this problem, thought I should give it a shot.
If you want to solve the problem yourself - stop reading now.
Solution - Recursion + Memoization
Easy problem really
1) Treat numbers starting with zero as special cases.
2) Let minplus[sum][pos] be an array that is the minimum number of pluses required to obtain the value 'sum' using the postfix starting at 'pos', then it's just simple recursion.
3) To avoid initialization, the array stores the number of pluses plus one.
If you want to solve the problem yourself - stop reading now.
Solution - Combinatorics
The hard part is to calculate the number of possibilities to fill one row of flowers; to obtain the final answer, raise this number to the number of rows.
Let S(c,n) be the number of ways to fill n columns with exactly c colours, when only c colours are available:
If you want to solve the problem yourself - stop reading now.
Solution: Catalan numbers & number of permutations.
The number of ways to order n pairs of matching brackets is i.e. The Catalan numbers.
The number of ways to order n things of m different types, where there are a1, a2,..., am things of each type is i.e. The number of permutations.
When multiplying, we can divide out n! and have: Numerator = (2n)! Divisor = (n+1)!a1!a2!...am!
We can calculate both quantities using modular multiplication, calculate the modular inverse of the divisor and then the modular product is the required answer.
This modular inversion uses the fact that and applies repeated squaring to calculate the exponentiation. We could have used extended Euclid instead.
Maybe one could have solved it by following the logical steps the problem outlined. Though I doubt it'll pass the time limit required. I, however, find this solution more fun.
The Canadian Computing Competition is a prestigious programming competition for high school students with considerable programming experience willing to take on a challenge.
For over a year now, I have been rather struggling to solve the last problem from the 2009 senior section, Wireless. The reason I have been struggling was not that my solution didn't generate the correct outputs, but that the algorithm was not efficient enough to pass the SPOJ online judging system, with a rather strict time limit.
My original solution which was just straight forward 2D array processing, with an O(N log N) algorithm complexity failed to pass the judge as it exceeded the time limit. Mind you, this was implemented in Java, which I realize now is horrible for online competitions. Perhaps another time I will post my thoughts on Java vs C/C++.
Anyways, after several failed attempts, I decided to change my language to C++, and while talking with one of my friends, I came up with a rather odd sort and count solution that at the time I didn't think was sufficient enough.
Here is an outline of how it works:
On every row, all wirelesses have a (possibly empty) range of columns it covers. This is translated into a set of commands for that row, consisting of a column number and the change in bitrate, with every wireless leading to two commands: An increase in rate at the start of the range, and a similar decrease at the end of the range. By combining the commands and considering them in order of column number, the cumulative bitrates can be calculated over the range of the whole row.
NOTE: With N rows and K wirelesses, the complexity of this implementation is O(N*K*InK), the K*InK factor arising from the fact that a simple Quick sort is used to sort the commands, plus the fact that a Binary search is used to find the ranges within each row (Pythagoras). Better algorithms may be possible.
Once I coded this, to my surprise, it finally got accepted! Time: 11.25 sec MEM: 2.6 M
Now I have to prepare for the upcoming regional ECOO programming contest held at York University. Usually the problems are very trivial, so i'm not worried at all.
