## 11394 - Digit Blocks

Moderator: Board moderators

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:
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!!!!!
``````
In being unlucky I have the record.

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:
tanaeem wrote: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
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

### Re: 11394 - Digit Blocks

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
New poster
Posts: 12
Joined: Tue Sep 21, 2010 8:51 pm

### Re: 11394 - Digit Blocks

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.