11394 - Digit Blocks

[arsalan_mousavian]

I am getting TLE on this "easy" problem, can anybody take a look at my code and tell me why....????

Code: Select all

Accepted after writing my dynamic solution recursively!!!!!

[Robert Gerbicz]

Thanx for help, I have got AC.
There was problem in my initialization of memo.
And I have solved this using 16X16X5 memo.

The problem is also solvable by only two 5X17 arrays, by that it took 0.00 sec. to solve this.

[serur]

I solved it with multinomial coefficients -- i.e. without any DP except for a set to store some duplicating bitmasks.
Got AC in 1.560. I now wonder how those fellows solve it in 0.000?
We just enumerate all the bitmasks, and if the corresponding sum of digits is divisible by 5, we form all permutations with repetitions... But here two different masks may represent one and the same subset, and here sets come into play.

[patsp]

I tried to solve this problem with the state dp[1<<16][5] as proposed, but getting TLE. Maybe some tips on how to solve it with 16X16X5 memo?

EDIT: With the help of Topcoder msg555 I am able to solve this problem now. See here for details.