Codeforces Round not_a_round (Div.0) EDITORIAL. A.Shan and the Pirates.

Revision en10, by Kolwdfurr_Rad, 2023-05-09 17:19:15

A.Shan and the Pirates.

Let us state the facts :

  • We must go from the top left corner to the bottom right corner .

  • We can only move right or down.

You may think that this question is dreadfully complicated as there are $$$2^{m+n-2}$$$ ways to go from the top left corner to the bottom right. If we were to check every possible path for the one with most treasures time taken by the program will be too much and we will clearly get TLE for larger m and n.

Let us take a coordinate system with $$$(1,1)$$$ being the top left corner of the grid and the bottom right being $$$(m,n)$$$.\ Define a function $$$f(x,y)$$$ to be the maximum number of treasures they can collect for all paths from $$$(1,1)$$$ to $$$(x,y)$$$ by only travelling down and right.

Take the input example in the question: \begin{array}{|c|c|c|c|} \hline 1 & 0 & 2 & 2 \cr \hline 0 & 0 & 0 & 0 \cr \hline 0 & 0 & 0 & 0 \cr \hline 0 & 3 & 0 & 1 \cr \hline \end{array}

Let $$$treasure(x,y)$$$ give the number of treasures on the island at $$$(x,y)$$$.

We can define the recursive relation : $$$f(x,y) = treasure(x,y) + max(f(x-1,y),f(x,y-1))$$$

This is because the we can reach $$$(x,y)$$$ immediately from the the points $$$(x-1,y)$$$ and $$$(x,y-1)$$$ only. If we had a $$$f(x-1,y)$$$ treasures at $$$(x-1,y)$$$ and we move right by one unit we will now have $$$f(x-1,y)+treasure(x,y)$$$.

Similarly ,If we had a $$$f(x,y-1)$$$ treasures at $$$(x,y-1)$$$ and we move down by one unit we will now have $$$f(x,y-1)+treasure(x,y)$$$.

The larger of these two values will $$$f(x,y)$$$ :-)

How do we find $$$f(m,n)$$$ -- the maximum number of treasures we can have by travelling from (1,1) to (m,n)?

Interestingly , we can just find the value of f for every point by iterating through every line one after another. I was initially proposing finding diagonals one by one , then realized line by line works just fine. Lets define $$$f(x,0)=0$$$ and $$$f(0,y)=0$$$ because there are no islands at those locations also, and it would make implementation of loop easier. If we did not define this , we would need to write separate loops to find value of f for first column and row.( its not too hard to do that but we're just lazy right).

The array of values of f are :

\begin{array}{|c|c|c|c|} \hline 1 & 1 & 3 & 5 \cr \hline 1 & 1 & 3 & 5 \cr \hline 1 & 1 & 3 & 5 \cr \hline 1 & 1 & 3 & 6 \cr \hline \end{array}

Code :

include <bits/stdc++.h>

using namespace std;

int main(){ int n,m; cin>>n>>m; int treasure[n][m]; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>treasure[i][j]; } }

//INPUT DONE

int f[n+1][m+1]; //function , maximum treasures shan can have at an island (x,y)
for(int i=0;i<=n;i++)f[i][0]=0;
for(int i=0;i<=m;i++)f[0][i]=0;

//set top , left side to ZERROOO

for(int i=1;i<n+1;i++){
    for(int j=1;j<m+1;j++){
        f[i][j]=max(f[i-1][j],f[i][j-1])+treasure[i-1][j-1];
    }
}

cout<<f[n][m];

}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en16 English Kolwdfurr_Rad 2023-05-10 10:47:44 0 (published)
en15 English Kolwdfurr_Rad 2023-05-10 10:47:19 8 (saved to drafts)
en14 English Kolwdfurr_Rad 2023-05-09 18:25:03 0 (published)
en13 English Kolwdfurr_Rad 2023-05-09 17:40:45 2
en12 English Kolwdfurr_Rad 2023-05-09 17:24:07 138
en11 English Kolwdfurr_Rad 2023-05-09 17:21:42 12
en10 English Kolwdfurr_Rad 2023-05-09 17:19:15 662
en9 English Kolwdfurr_Rad 2023-05-09 12:13:50 2070 Tiny change: '===\nThis problem r' -> '===\nThis ### problem r'
en8 English Kolwdfurr_Rad 2023-05-09 09:48:50 4 Tiny change: '===\nThis problem r' -> '===\nThis ### problem r'
en7 English Kolwdfurr_Rad 2023-05-09 09:48:39 57 Tiny change: '===\nThis problem r' -> '===\nThis ### problem r'
en6 English Kolwdfurr_Rad 2023-05-09 09:48:12 4 Tiny change: '===\nThis problem r' -> '===\nThis ### problem r'
en5 English Kolwdfurr_Rad 2023-05-09 09:48:00 60
en4 English Kolwdfurr_Rad 2023-05-09 09:46:29 147
en3 English Kolwdfurr_Rad 2023-05-09 09:44:51 6 Tiny change: 'there are 2^(m+n-2) ways to g' -> 'there are $2^{m+n-2}$ ways to g'
en2 English Kolwdfurr_Rad 2023-05-09 09:44:30 44 Tiny change: 'nd n. \n\n' -> 'nd n. \n\n[user:Kolwdfurr_Rad]\n$a=b$\na=b'
en1 English Kolwdfurr_Rad 2023-05-08 23:29:26 612 Initial revision (saved to drafts)