trying to solve Happy Valentine Day (Valentine Maze Game)
getting TLE
![:frowning: :frowning:](https://discusstest.codechef.com/images/emoji/apple/frowning.png?v=9)
first i am mapping all my T, W and C to a map<pair, int>
then i am doing bfs to find all the minimum distances between all C, T and W
as C < 10 , T == 1, W == 1,
so a matrix[12][12] is crested and then jst back tracking the matrix from T to W via all C
i have also used dp with bitmask instead of backtrackingā¦ but still TLE
can anyone suggest me any way to optimize the solution
my backtrack solution link
Try this one, unfortunately setting limit to 15s is broken on IdeOneā¦
sorry but C < 10 in the problem
so for this my code wont workā¦ for the input u had give to meā¦
can u suggest me any other approach for this problem
actually i m finding the minimum distance for each pair of C, T, w
and then jst backtracking itā¦but its giving TLE
first thing, you can try is to replace all cin/cout with scanf/printfā¦ or simply turn off buffering ( ios_base::sync_with_stdio(false)
) ā¦
i am using scanf for input and as testcase are only 30 so cout or printf doesnt matterā¦
i dont know what is this os_base::sync_with_stdio(false)??
and if i am using this in my code it is giving the initialised value of the variable i am priting and not changing it
without this its working fine
try the input in ideone, for 4 inputs it gets TLE, hope the input is ok now ![:wink: :wink:](https://discusstest.codechef.com/images/emoji/apple/wink.png?v=9)
can u suggest me how can i optimise the solution or any other approach to solve this ā¦
i am not getting one thing 2 testcase with same input is working in 0.01 and if a similar testcase is added 3rd time its giving TLEā¦strange
Maybe some memory issue, are you clearing memory?
Why you iterate cell by cells if bfs()? It seems to me, you want to find the best sequence of T - C1 - C2 - ā¦ - CN - W, while N is atmost 10, 10! is ok on modern PC, but you can use queue just for those 12 points similarlyā¦
in the last input again u add c > 10 so it was TLE nw its notā¦
can u plz elaborate ur last comment actually i m not getting itā¦
if i use DP bitmask instead of backtrack will this reduce the timeā¦
@betlista thank u very much for ur time finally accepted using bitmask
please remove the ideone link that u have mentioned in ur first commemt
thank u man