Problem Link: https://www.spoj.com/problems/LAZYCOWS/
LAZYCOWS Editorial/Solution
Basically We have 2 x B Grid where 2 rows and B colums are given. The problem say we have to use exactly "k" rectangles and every rectangle atleast contain one cow. No cow should be left outside of any rectangle.
Constraint :
t = Number of test cases.
N= Number of cows(N<=1000)
B= Number of columns (1<=B<=15,000,000).
Rows are 2 fixed.(Given).
K=Number of rectangles(1<=K<=1000)
Time limit=9 seconds.
For each test case : Output the minimum area required by the K rectangles/barns in order to cover all of the cows.
Firstly there are 3 types of rectangle can be possible:
In the A Type rectangle only upper horizontal cows included.(only 1st row).
In the B Type rectangle only lower horizontal cows included.(only 2nd row)
In the C Type rectangle only both both rows included.
Now We start from Left of Grid and form rectangle (Type A,B,C depend whether we can form or not).Rectangle starting and ending point must be cow.
We form Rectangle from L to R where L is fixed and R increases till the grid.If one rectangle is formed L to R then :
here L is starting point
cost[L][R-1]=depends which type of rectangle(A,B,C).
Time complexity will be =L*K where L=B and K<=1000 and TLE will come.To reduce time complexity get rid of B.
If we apply coordinate compression then L <=N and we will get AC.
Remove all those columns where no cows are present.
If You are not able to see Overlapping sub problem then see below gif :
.
Take a look at the code below:
few things to notice in the code that combination of Type A and Type B rectangle is different from Type C rectangle.In Type C only 1 rectangle is used where in Combination of Type(A+B) 2 rectangles are used.
Code URL : https://ideone.com/mJXOR8
LAZYCOWS Editorial/Solution
Basically We have 2 x B Grid where 2 rows and B colums are given. The problem say we have to use exactly "k" rectangles and every rectangle atleast contain one cow. No cow should be left outside of any rectangle.
Constraint :
t = Number of test cases.
N= Number of cows(N<=1000)
B= Number of columns (1<=B<=15,000,000).
Rows are 2 fixed.(Given).
K=Number of rectangles(1<=K<=1000)
Time limit=9 seconds.
For each test case : Output the minimum area required by the K rectangles/barns in order to cover all of the cows.
Firstly there are 3 types of rectangle can be possible:
In the A Type rectangle only upper horizontal cows included.(only 1st row).
In the B Type rectangle only lower horizontal cows included.(only 2nd row)
In the C Type rectangle only both both rows included.
Now We start from Left of Grid and form rectangle (Type A,B,C depend whether we can form or not).Rectangle starting and ending point must be cow.
We form Rectangle from L to R where L is fixed and R increases till the grid.If one rectangle is formed L to R then :
here L is starting point
cost[L][R-1]=depends which type of rectangle(A,B,C).
Time complexity will be =L*K where L=B and K<=1000 and TLE will come.To reduce time complexity get rid of B.
If we apply coordinate compression then L <=N and we will get AC.
Remove all those columns where no cows are present.
If You are not able to see Overlapping sub problem then see below gif :
.
Take a look at the code below:
few things to notice in the code that combination of Type A and Type B rectangle is different from Type C rectangle.In Type C only 1 rectangle is used where in Combination of Type(A+B) 2 rectangles are used.
Code URL : https://ideone.com/mJXOR8
