11394 - Digit Blocks

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Sun Jan 20, 2008 12:09 am

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:

Post by Robert Gerbicz » Thu Jan 24, 2008 3:18 pm

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

Post by serur » Wed Feb 10, 2010 7:00 pm

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

Post by patsp » Fri Jan 21, 2011 10:57 pm

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.

Post Reply

Return to “Volume 113 (11300-11399)”