I guess in the above solution greedy wont wrk..i just assumed it wud..dint
prove it..
nevertheless..we can replace dis with..
F(A,B,a,b,x,N) = % fill + max( F(A,Bx,a,b,x,N-(squares filled across
length)), F(Ax,B,a,b,x,N-(squares filled across breadth)) )
Regards
VM
NSIT, COE, 3rd yr
On , [email protected] wrote:
With the binary search we can decide for a value of size of square with
reasonable error..
nw to check hw much % fill does that value of size gives..we can
implement a dp..or a recursive substitute..
say size of rectangle is 'a' x 'b' and size of square chosen is 'x'..
we hv to fill a grid with squares of size 'x'..so greedily fill the
squares across the length of rectangle(subject to N)..
so recursive function wud luk sumthin like dis
F(A,B,a,b,x,N) = gives the % fill = % fill + F(A,Bx,a,b,x,N-(squares
filled across length))
where A x B is size of rectangle to fill, axb is maximum size of
rectangle, x is size of square we are considering, N is remaining squares
we can fill..
base cases wud be wen we cannot fill squares subjected to N = 0 or if A
and B dont permit us to..
I hope dis helps mam.
Regards
VM
NSIT, COE, 3rd yr
On , Kamakshii Aggarwal [email protected]> wrote:
> @vaibhav:can u please elaborate?
>
> On Tue, Aug 2, 2011 at 6:31 PM, Vaibhav Mittal
[email protected]> wrote:
>
> dynamic programming with binary search should do it..
>
> Regards
> VM
> NSIT, COE, 3rd yr
>
>
>
> On Tue, Aug 2, 2011 at 6:19 PM, Kamakshii Aggarwal
[email protected]> wrote:
>
> @sunny:yes all the squares should be of same size
>
>
> On Tue, Aug 2, 2011 at 5:03 PM, Poised~ [email protected]> wrote:
>
>
>
> @ narain-i didn't see that coming. thanks for the heads up.
>
>
>
>
>
> --
>
> You received this message because you are subscribed to the Google
Groups "Algorithm Geeks" group.
>
>
> To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/oSuB8bJuqDcJ.
>
>
>
> 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?hl=en.
>
>
>
>
>
>
>
>
>
>
> --
> Regards,
> Kamakshi
> [email protected]
>
>
>
>
>
> --
>
>
> 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?hl=en.
>
>
>
>
>
>
>
>
>
>
>
>
> --
>
> 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?hl=en.
>
>
>
>
>
>
>
>
> --
> Regards,
> Kamakshi
> [email protected]
>
>
>
>
>
> --
>
> 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?hl=en.
>
>
>
>
--
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?hl=en.
