Editorialist : Sudheera Y S
Problem link : Zonal Informatics Olympiad, 2006
Prerequisites: logical thinking , observations , dp
Problem statement:
Given a set of points with their x and y coordinates , we need to start from a point in the given set and then we can perform two steps :
- Decrease x coordinate and reach another point in the same set
- Decrease y coordinate and reach another point in the same set
We can start from any number and we need to keep on doing this until we can’t continue it any further . Find the maximum number of steps we can perform.
Idea:
We will plot the given set of points in a x and y coordinate and then we will see what these two operations mean in the graph and then find the maximum number of steps we can perform and that would be our answer
Subtask A :
Given set of points :
{ (87,115) , (115,56) , (208,242) , (115,87) , (182,242) , (147,242) , (147,147) , (147,182) , (242,56) , (208,147) , (182,208) , (56,115) , (147,208) , (115,208) , (87,56) , (115,115) , (182,56) , (182,115) , (147,115) , (56,182) }
Plotting the given set of points and the graph would look like :
So here we can do two things :
- Reduce x coordinate and the same y coordinate → means that we are travelling along the same y-axis i.e we are travelling horizontally
- Reduce y coordinate and the same x coordinate → means that we are travelling along the same x-axis i.e we are travelling vertically
Therefore here is our observation :
Starting from any point , we can either move horizontally or vertically backward or downward respectively
Therefore we have to start as top right as possible to make the maximum number of moves
Let us take an example ( 242, 56 ) which is the maximum right possible but we will be able to do only three moves ( Note: Here we should not consider ( 242, 56 ) point in the number of moves )
But if we start from ( 208, 242 ) point then we will be able to do 10 moves as shown :
Here we see that this is the maximum number of moves we can make as we are using all the points of top right
Therefore the answer is 10
Answer : 10
Subtask B:
{ (127,92) , (73,127) , (65,127) , (152,92) , (65,153) , (73,73) , (127,109) , (65,109) , (127,41) , (152,65) , (153,92) , (41,65) , (127,152) , (41,109) , (153,73) , (92,92) , (152,73) , (153,127) , (65,73) , (92,109) , (109,92) , (109,127) , (73,153) , (41,127) , (109,73) }t
Let us plot this given points :
Here finding all the possibilities may take too much time or it can give inaccurate results as we are just trying to figure out some possibilities
What we were doing till now is greedy approach or brute force approach , now let us try dp approach which is efficient and accurate
First let us give numbers to all these points plotted on the graph :
Let us define dp as follows :
dp[ i ] = maximum number of moves we can perform if we stop at ith point or start at ith point if we can’t reach i’th point from any other point
Base case → dp[ i ] = 1 for all those points for which we can’t come to that point from anywhere else
dp relation →
dp[ i ] = max( dp [ j ] + 1 ) for all j from which we can reach ith point
What are the j for any point i ?
- The point which is nearest to this point above it if it exists
- The point which is nearest to this point beside it if it exists
Answer →
(Max ( dp[ i ] ) ) - 1 for all valid i
Note: Here we are doing -1 once we get the maximum number because we should not consider the first point in our number of steps
How to fill the dp ?
We will start from top line which is parallel to x axis and fill the dp values of those points which are in that line from right to left as we can only move either down or left
Let us start our dp →
y = 153 line :
dp[ 3 ] = 1 ( as we can’t reach point 1 from any other point )
dp[ 4 ] = dp[ 3 ] + 1 = 2 ( as we can come to 4 only by 3 )
y = 152 line :
dp[ 2 ] = 1 ( as we can’t reach point 1 from any other point )
y = 127 line :
dp[ 1 ] = dp[ 1 ] + 1 = 2 ( as we can come to 17 only by 1 )
dp[ 8 ] = dp[ 1 ] + 1 = 2 ( as we can come to 8 only by 1 )
dp[ 7 ] = max ( dp[ 8 ] + 1 , dp[ 3 ] + 1 ) = 3
dp[ 6 ] = max ( dp[ 4 ] + 1 , dp[ 7 ] + 1 ) = 4
dp[ 5 ] = dp[ 6 ] + 1 = 5 ( as we can come to 5 only by 6 )
y = 109 line :
dp[ 12 ] = dp[ 2 ] + 1 = 2 ( as we can come to 12 only by 2 )
dp[ 11 ] = dp[ 12 ] + 1 = 3 ( as we can come to 11 only by 12 )
dp[ 10 ] = max ( dp[ 11 ] + 1 , dp[ 6 ] + 1 ) = 5
dp[ 9 ] = max ( dp[ 10 ] + 1 , dp[ 5 ] + 1 ) = 6
y = 92 line :
dp[ 17 ] = dp[ 1 ] + 1 = 2
dp[ 16 ] = dp[ 17 ] + 1 = 3
dp[ 15 ] = max ( dp[ 16 ] + 1 , dp[ 12 ] + 1 ) = 4
dp[ 14 ] = max ( dp[ 15 ] + 1 , dp[ 8 ] + 1 ) = 5
dp[ 13 ] = max ( dp[ 14 ] + 1 , dp[ 11 ] +1 ) = 6
y = 73 line :
dp[ 22 ] = dp[ 17 ] + 1 = 3
dp[ 21 ] = max ( dp[ 22 ] + 1 , dp[ 16 ] + 1 ) = 4
dp[ 20 ] = max ( dp[ 21 ] + 1 , dp[ 14 ] + 1 ) = 6
dp[ 19 ] = max ( dp[ 20 ] + 1 , dp[ 7 ] + 1 ) = 7
dp[ 18 ] = max ( dp[ 19 ] + 1 , dp[ 10 ] + 1 ) = 8
Y = 65 line :
dp[ 24 ] = dp[ 21 ] + 1 = 5
dp[ 23 ] = max ( dp[ 24 ] + 1 , dp[ 9 ] + 1 ) = 7
y = 41 line :
dp[ 25 ] = dp[ 15 ] + 1 = 5
Out of all these dp values , we find that the maximum number is 8 i.e dp[ 18 ]
Total number of steps = 8 - 1 = 7 ( -1 because we should not consider the first point )
Here is the steps we have to make to achieve this maximum :
And here are our dp values for all the points :
Here dp[ i ] is the answer for maximum number of steps we can perform if we stop at the ith point or if we start from the ith point
dp values for all the points :
Answer: 7
We see that for any given point , the answer is if we consider that point
Therefore dp is more accurate than greedy or brute force and it is efficient as we are not considering all the possible paths
Subtask C:
{ (84,36) , (54,41) , (36,41) , (97,75) , (35,35) , (64,36) , (97,97) , (64,84) , (54,97) , (54,64) , (36,75) , (54,35) , (41,35) , (64,75) , (84,54) , (84,41) , (35,54) , (35,84) , (75,41) , (41,75) , (35,75) , (87,84) , (64,97) , (35,87) , (36,87) , (97,84) , (41,41) , (84,64) , (84,75) , (87,36) }
Let us plot this on the graph :
Now, let us label these points so that we can write dp easily :
Let us start filling our dp from the top row and from right to left :
y = 97 line :
Dp[ 1 ] = 1 ( as we can’t come to point 1 from any other point )
Dp[ 2 ] = dp[ 1 ] + 1 = 2 ( as we can come to point 2 only from point 1 )
Dp[ 3 ] = dp[ 2 ] + 1 = 3 ( as we can come to point 3 only from point 2 )
y = 87 line :
Dp[ 4 ] = 1 ( as we can’t come to point 4 from any other point )
Dp[ 5 ] = dp[ 4 ] + 1 = 2 ( as we can come to point 5 only from point 4 )
y = 84 line :
Dp[ 6 ] = dp[ 1 ] + 1 = 2 ( as we can come to point 6 only from point 1 )
Dp[ 7 ] = max ( dp[ 6 ] + 1 , dp[ 2 ] + 1 ) = 3
Dp[ 8 ] = max ( dp[ 7 ] + 1 , dp[ 5 ] + 1 ) = 4
y = 75 line :
Dp[ 9 ] = dp[ 6 ] + 1 = 3 ( as we can come to point 9 only from point 6 )
Dp[ 10 ] = dp[ 9 ] + 1 = 4 ( as we can come to point 10 only from point 9 )
Dp[ 11 ] = max ( dp[ 10 ] + 1 , dp[ 7 ] + 1 ) = 5
Dp[ 12 ] = dp[ 11 ] + 1 = 6 ( as we can come to point 12 only from point 11 )
Dp[ 13 ] = max ( dp[ 12 ] + 1 , dp[ 4 ] + 1 ) = 7
Dp[ 14 ] = max ( dp[ 8 ] + 1 , dp[ 13 ] + 1 ) = 8
y = 64 line :
Dp[ 15 ] = dp[ 10 ] + 1 = 5 ( as we can come to point 15 only from point 10 )
Dp[ 16 ] = max ( dp[ 3 ] + 1 , dp[ 15 ] + 1 ) = 6
y = 54 line :
Dp[ 17 ] = 1 ( as we can’t come to point 17 from any other point )
Dp[ 18 ] = max ( dp[ 17 ] + 1 , dp[ 15 ] + 1 ) = 6
Dp[ 19 ] = max ( dp[ 18 ] + 1 , dp[ 14 ] + 1 ) = 9
Y = 41 line :
Dp[ 20 ] = dp[ 18 ] + 1 = 7 ( as we can come to point 20 only from point 18 )
Dp[ 21 ] = dp[ 20 ] + 1 = 8 ( as we can come to point 21 only from point 20 )
Dp[ 22 ] = max ( dp[ 16 ] + 1 , dp[ 21 ] + 1 ) = 9
Dp[ 23 ] = max ( dp[ 12 ] + 1 , dp[ 22 ] + 1) = 10
Dp[ 24 ] = max ( dp[ 13 ] + 1 , dp[ 23 ] + 1 ) = 11
y = 36 line :
Dp[ 25 ] = dp[ 17 ] + 1 = 2 ( as we can come to point 25 only from point 17)
Dp[ 26 ] = max ( dp[ 25 ] + 1 , dp[ 20 ] + 1 ) = 8
Dp[ 27 ] = max ( dp[ 26 ] + 1 , dp[ 11 ] + 1 ) = 9
y = 35 line :
Dp[ 28 ] = dp[ 22 ] + 1 = 10 ( as we can come to point 28 only from point 22)
Dp[ 29 ] = max ( dp[ 28 ] + 1 , dp [ 23 ] + 1 ) = 11
Dp[ 30 ] = max ( dp[ 29 ] + 1 , dp[ 19 ] + 1 ) = 12
Finding the dp values for all the points are over
Maximum number in the dp is 12 and the answer is 12 - 1 = 11 ( here we are doing -1 because the initial point is not considered in the number of steps but we are considering it in our dp )
Therefore answer is 11
Here are the dp values of all the points :
Answer: 11
Hope you understood 
