ZCO Dynamic Programming problems

general
, , , ,
21

Seconded!!

22

So can u ? sandy999 ?

23

oh
so u changed it. i have done same thing in my code. except i didnā€™t use best[j,0] in comparison. is that even needed??

24

Yes it is because the solution would be stored in Best[0,0].

25

What should we loop from N-1 to 0? Shouldnā€™t we loop from 0 to N-1 instead?

26

You cannot find the value for i without first knowing the values for i + 1;

27

See that at the base case I am initializing Best[N,0] to Fees[N], and as @superty pointed out the the new values of Best[i,] cannot be found without knowing the value of Best[i+1,].Think it like this way,we are writing an unmemoized code where Best(0,0) would return the solution.The recursive procedure would continue until it hits the Base Case and then backtrack the solution from the Best(N,ā€¦).So the base case is a necessity and since we have set the Base case with regards to N, we have to loop from N-1 to 0.
You can try to loop from 1 to N by setting Best[0,1]=Fees[1].

28

Its wrong the memo table must be 2d

29

Which problem is this? In any case I have solved both with just a 1d memo table so it is not necessary

30
31

@superty can you help me in solving Little Red Riding Hood here ( ZCO problem Little Red Riding Hood - general - CodeChef Discuss ) and Save Spaceman Spiff here (Save Spacemen spiff - general - CodeChef Discuss )

32

its IPLā€¦ i thought if i could get this then SUPW was peice of cakeā€¦ :confused:

33

@superty can you please answer this ( ZCO practice server INOI 2013 problem SequenceLand - general - CodeChef Discuss )

34

Thanks a lot @superty and @swagatochatt! Sorry, this kind of thinking never occurred to me as I hadnā€™t got the hang of recursion, I spent over hours poring over this simple pseudocode, finally understood, that was one amazing logic! I got it accepted now. Thanks again! :slight_smile:

35

@superty can you tell me what thought process you undergo while solving DP?

1 Like
36

Itā€™s just practice, there is really not much to explainā€¦

Well upon seeing the problem I realized that itā€™s not really much different from other problems like SUPW and all, just that the table is circular.

So now we have to see how to deal with the circular part. What I did was I considered two cases for the pair of adjacent tables 1 and N, taking 1 or taking N. Then for each case do the DP and find the minimum cost of the cases

1 Like