Showing posts with label Complete Search. Show all posts
Showing posts with label Complete Search. Show all posts

Saturday, June 15, 2013

11242 Tour de France


This is complete search problem only catch in this problem to fix and round the ouput note cout at the end

435 Block Voting


This is problem of Complete search.Though problem statement is not clear it can be understood with the test case.It states to find no of winning combination including particular party. Search all combinations

10360 Rat Attack



This is easy backtracking problem which can be solved in O(n*d^2) complexity.
But this could also solved in 1025^2 using dp using range sum.
take input and make entries in dp[1025][1025];
Preproccess the 1025x1025 array using :
        dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+dp[i][j];
then, use recurrence relation to find max
        dp[i+d][j+d]-dp[i+d][j-d-1]-dp[i-d-1][j+d]+dp[i-d-1][j-d-1]; for all (i,j) between d+1 to 1025-d