BABY - Baby



hide comments
Rafail Loizou: 2020-11-12 13:39:43

Just do top-down if you just want to get the AC. Use memoization since you can have at most 2^16 states to deal with which is pretty small. So for each test case you don't have to do more than 2^16 recursive calls which will work and give you the AC. I would be interested to see in what other way it can be solved like flows and similar definitely gonna try this again.

Last edit: 2020-11-12 13:40:22
abhimanyu_1998: 2019-12-29 12:48:40

cakewalk!

rks14: 2019-09-14 15:57:01

Are we assuming that we can move all the queens simultaneously?
Should be mentioned.

tarungupta: 2019-04-07 07:54:34

Since Time Limit is very less, don't take much additional space in dp matrix as initializing all with -1 can cost a TLE.
I used dp matrix of size [100000][20], this costed me a TLE, while changing size to [70000][17] got me AC.

learnerinblack: 2018-06-04 15:34:10

Hint :
Step1 : Make a matrix of nxn named dis where dis[i][j] = the distance between ith queen to the jth final position.
Step2 : Recurrence relation solve(mask) = minimum of( for all i st mask&(1<<i) == 0 solve(mask | (1<<i)) + dis[i][j])
Step3 : Submit the solution and get AC

enzymii: 2018-03-14 09:44:07

Got accepted with min-cost-max-flow rather than dp...

siddharth9820: 2016-12-26 21:26:26

Just do not use bottom-up as the time limit is low.

Furquan Uddin: 2016-09-14 08:28:23

Bottom up DP gave TLE while top down gave AC.

zoooma13: 2016-08-14 03:36:49

For people who want an image : https://image.ibb.co/hFRBwn/BABY.png
Hope this helps :)

Last edit: 2018-04-20 02:34:51
jajusantosh: 2016-06-17 07:54:14

will hungarian algorithm work?


Added by:Jimmy
Date:2008-12-09
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ACM Kanpur 2007