Atcoder Beginner Contest 142 Task — E

Revision en1, by cd_mas7er, 2019-09-29 13:39:36

Hello,

problem :- link

I am finding a difficulty in understanding why does one of my solution pass and the other is giving tle although i think the time complexity of both the codes are same.

tle code — link

ac code — link

tle code — i have written a recursive function and i am using 2d dp where dp[i][j] means minimum cost of opening those locks where the bit is set in the binary representation of j using only 0 to i keys. Base case — if i==m , that is all the keys are taken into consideration if the binary representation of j does not have all the bits set to 1 , then all the locks are not opened , return infinity and if all the locks are opened then return 0.

ac code — i have just written an iterative function and taken 1d dp where dp[i] = minimum cost of opening those locks where bit is set in the binary representation of i.

the time complexity of TLE code at worst can go O(m*(2^n)) because this the dimension of the dp i am filling and ac code has time complexity as O(m*(2*n)). Since both the solution have same time complexity i don't know why one is gettiing tle and other is not.

Could anyone please tell me what i am doing wrong. Thanks in advance.

Tags #atcoder, beginner contest, #dp, bitmasking, #tle, #help me

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English cd_mas7er 2019-09-29 13:39:36 1434 Initial revision (published)