[algogeeks] Re: Help me with this problem

Sat, 17 Jun 2006 17:52:26 -0700

I've encountered the 8*8 and 1*2 version of this problem. The number of feasible placement is much greater than you expected, because very brick has two direction(vertical and horizontal).
 
One way to solve this N*M and 1*2 version problem is DP, which is fast. But the general problem is too complex using DP, I don't know whether it works or not.
 
At first, the N*M matrix is considered as consisting of N layers.
The idea is that every layer of the N*M matrix maintains an array  to record it's state . The length of the array is 2^M and each element i of the array represents the optimal solution when current layer is in the state i and all the layer below it is filled fully( 1*2 version can guarantee that the below layer is filled fully). When you want to calculate layer j according to layer j-1(1*2 version can guarantee that only layer j-1 is needed, which is not correct when the more general situation 1*K is considered), you should try all the possible placement of every brick.
 
On 6/18/06, Norbert <[EMAIL PROTECTED]> wrote:

Letters are just numbers bigger than 10:

0000aaaa??
1111bbbb??
2222ccccqv
3333ddddqv
4444eeeeqv
5555hhhhqv
6666kkkkwg
7777nnnnwg
8888oooowg
9999ppppwg

0-9, a, b, c, d, e, h, k, n, o, p, q, v, w, g: 10 + 14 = 24

On 6/17/06, prashant bhargava < [EMAIL PROTECTED]> wrote:
> Could u plz explain how u r getting the answer 24 (for ur 2nd reply) ??
>
> I really didn't understand.plz explain
>
>
> On 6/17/06, Norbert < [EMAIL PROTECTED]> wrote:
> >
>
> There's another example if you use floating point arithmetic. N = 10,
> M = 10, K = 4. Correct answer is 24, not 25
>
> On 6/17/06, Norbert <[EMAIL PROTECTED]> wrote:
> > Sorry, you're wrong. Consider board of size N = 1, M = 5 and K = 2.
> > If you round down (N/K) then you have RESULT = 0. If you round up then
> > you have 5. Also wrong.
> >
> > On 6/17/06, prashant bhargava <[EMAIL PROTECTED] > wrote:
> > > if the question is complete then the answer shd' be (N/K) * M bricks
> > >
> > > am i right??
> > >
> > >
> > >
> > > On 6/17/06, Norbert < [EMAIL PROTECTED]> wrote:
> > > >
> > >
> > > I'm unable to solve this problem correctly. Please help me:
> > >
> > > You have chess board of size N x M and a lot of bricks of size K x 1.
> > > How many bricks can you place on this board (brick edges must be
> > > pallarel to board edges)
> > >
> > > Thanks for help
> > >
> > >
> > >
> > > Regards,
>  > > Prashant Bhargava
> > > ***--***--***--***--***--***--***
> > > Plz do visit
> > > www.hemantdesign.com/prashant
> > >  > >
>  > >
> >
>
>
>
>
> --
> "I am extraordinarily patient, provided I get my own way in the end."
>
>
> Regards,
> Prashant Bhargava
> ***--***--***--***--***--***--***
> Plz do visit
>  www.hemantdesign.com/prashant
>  >
>
>


--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---

Reply via email to