Sort 6 Discussions, By:
Please Login in order to post a comment
Case #19 seems to violate the described input format - looks like there is a line (after the first m+1) and which contains a single integer, not three.
I does not understand the problem can anyone explain it clearly, what is it
Why does my last case does not get submitted?
interesting problem, had a lot of fun micro-optimizing it, though with that said it really should be marked advanced, overall neither I nor the editorial could reduce the time complexity to 2^d or lower, i.e. constant overhead; the best I got was a factor of ceil(n/w) where w is the largest machine word in bits while the editorial is at n; note that the editorial has little to no micro-optimizations, as such the likelyhood of actually passing all the testscases without compile optimization flags is very low, its still a good start, good luck.
Dynamic programming (or memoization) and indeterminism!
If we suppose n_ways(A, d) to be a function that returns the total number of distinct ways in distance d from ANY house in a set A, we can compute it recursively:
n_ways(A, d) = n_ways(reach(A, 0), d-1) + n_ways(reach(A, 1), d-1)
where reach(A, c) gives the set of all houses that can be reached from ANY house in A with given clue (c = 0 or 1).
Then, memoizing n_ways() based on different A and d can boost the performance.