You are not logged in. Please login at www.codechef.com to post your questions!

×

Dynamic Programming

Hey how to solve this problem? Thanks in Advance

asked 27 Mar '18, 00:08

phantomhive's gravatar image

4★phantomhive
944
accept rate: 0%

1

I think it would be appropriate to put the full name of the problem in the question title. It may help someone searching for it in the future.

(27 Mar '18, 22:14) meooow ♦6★

Noted! @meooow

(31 Mar '18, 22:21) phantomhive4★

1) Take a linear DP array which you'll use as a table.
2) Instead of taking a boolean visited array, take an integer array and store a unique number for each DFS search.
3) Use this index to refer to DP array whenever you encounter a query which is already visited.

if(!vis[a][b]) {
  ++idx;
  ans = dfs(a, b);
  dp[idx] = ans;
}
printf("%d\n", dp[ vis[a][b] ]);

You can also use a Union-Find Data Structure.

link

answered 27 Mar '18, 13:12

raffleberry's gravatar image

4★raffleberry
11
accept rate: 0%

edited 27 Mar '18, 13:22

Hi,

The problem asks u to find the number of pictures(maximum) he can see for the given k starting positions.

So for now leave the k queries and solve the problem.

Approach:1) start iterating the museum and whenever u encounter an empty cell perform dfs if it is not visited and count the pictures he can see and the answer will be the same for all the empty cells we get in the path of dfs.

void dfs(int a,int b)

{

path.push_back(make_pair(a,b));

checker(a-1,b);

checker(a+1,b);

checker(a,b-1);

checker(a,b+1);

}

Now in checker function we add the answer of the pictures.

void checker(int a,int b) {

if (visited[a][b]) return;

if (museum[a][b]=='*')
    ++C;

else
  dfs(a,b);

}

Here C is the maximum pictures he can see and it is same for all the empty cells in that component.

Now we have the answer for all the cells as starting point so for each query just output the answer .

link

answered 27 Mar '18, 16:32

beginner_1111's gravatar image

4★beginner_1111
240110
accept rate: 13%

U need to simply apply dfs from the starting point given in the query if u dont have its answer precalculated....now the recurrence for dp could be like

dp[x][y]+=1 ...if adjacent child is '*' or dp[x][y]+=dp[child_x][child_y]...where arr[child_x][child_y]='.'...

"Now answer for all the nodes visited in dfs will be equal to dp[x][y]",,,this is because if u can visit child_x and child_y from x and y and see dp[x][y] pictures then you can also see dp[x][y] pictures if you start your journey from child_x and child_y..........

To implement this simply take a vector of pair...push all the nodes visited in this vector and do something like this... for(auto it:v) { dp[it.first][it.second]=dp[x][y]; } Now print the value of dp[x][y]..!!

link

answered 01 Apr '18, 02:46

v_k_pandey98's gravatar image

4★v_k_pandey98
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,095

question asked: 27 Mar '18, 00:08

question was seen: 479 times

last updated: 01 Apr '18, 02:46