Can it be faster than O(M^2)?

Delete a rectangle if there is another one covering this one

For those who has WA4 or WA7

Test #1:
20 10
3
94 3 3 18
36 7 1 10
73 2 15 19

Answer: 1


Test #2:
7 2
11
6 1 4 1
9 2 5 1
8 3 1 2
7 1 4 2
10 1 7 2
4 2 5 3
99 3 1 5
85 3 4 5
100 1 7 5
100 1 7 6
100 1 7 7

Answer: 4


Test #3:
55 14
87
84 26 14 12
24 14 41 27
85 6 42 18
42 5 49 44
54 1 13 40
85 1 55 17
77 1 9 55
34 5 15 50
31 1 32 55
18 2 54 45
59 8 26 44
79 3 43 52
72 4 51 51
101 5 34 46
35 1 52 18
31 8 47 3
92 1 20 38
10 2 50 1
46 2 5 51
10 2 48 13
92 3 21 52
84 1 12 55
58 2 11 17
24 1 46 54
74 1 30 9
32 2 54 43
29 3 28 52
23 2 1 41
89 1 19 44
49 2 53 1
52 2 40 1
77 6 1 33
44 1 42 9
28 1 52 16
53 1 9 52
74 1 42 2
16 1 37 54
27 1 40 55
72 6 3 21
58 1 13 55
9 1 44 55
37 2 50 23
51 7 21 2
6 1 34 43
27 5 39 43
16 1 40 54
63 2 2 54
93 1 7 55
63 2 13 9
12 1 18 55
94 1 54 12
34 2 41 54
91 1 12 47
99 1 55 27
97 4 25 40
70 1 55 29
21 1 39 54
42 1 9 41
89 1 31 53
84 2 50 17
93 1 14 55
81 4 7 36
68 1 55 14
84 2 7 43
51 1 21 55
85 3 53 23
46 6 1 44
49 2 3 28
42 1 20 53
58 1 53 13
15 2 54 21
59 2 47 50
94 1 17 55
28 2 40 25
49 2 48 54
88 1 55 32
55 4 17 8
47 4 3 17
41 3 49 20
7 1 52 20
67 1 49 52
33 1 38 55
85 5 3 4
23 3 21 45
19 3 11 50
36 1 2 39
67 8 31 1

Answer: 24


Good Luck!

Split your land and get smaller lands !

First, you have a land (1,1)(n,n)

For example:

Your land:

1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1

after adding the land with maximal importance:

1 1 1 1 1 1
1 1 1 1 1 1
1 1 9 9 1 1
1 1 9 9 1 1
1 1 1 1 1 1
1 1 1 1 1 1

You have 4 new lands:

2 lands:

a a a a a a
a a a a a a
1 1 9 9 1 1
1 1 9 9 1 1
a a a a a a
a a a a a a

and 2 lands:

a a 1 1 a a
a a 1 1 a a
a a 9 9 a a
a a 9 9 a a
a a 1 1 a a
a a 1 1 a a

For each of your new lands, you continue add other lands with decreasing importance.

Finally, you will find out that after adding a land with a certain importance t, you can't create a land with desired park size. Now, you end your program and output t.

THE END ^^!







Edited by author 08.10.2010 14:39

Edited by author 12.10.2010 10:14

My solution got AC, but it looks like it won't pass next test:

10000 9982
100
98 1 1 1
98 1 2 1
98 1 3 1
98 1 4 1
98 1 5 1
...
98 1 100 1

Upd. To be exact, submission 5758774 works over 15 seconds locally on this test
(over 10 if change 9982 to 10000).

Edited by author 19.07.2014 21:31

Who can give me the test 5?I get WA5!Thanks!

my AC program failed on many tests

I have a question what do I output, the sum of importance
or just a piece of land's importance?

The example is that:
 3   2   0   0   0
 2   2   0 100 100
 2   2   0 100 100
94  94   0   0   0
94  94   0   0 255

we have to select a land whose area is 3*3,how can I just
expropriate the land whose importance is 3?

I think the least importance is 3+2+2=7.


Thank you for answering my question?

I'd be glad if anybody could give me some tests. I get WA on test 7.

Could anyone give some testdatas?

i need help, pls!!
how i can solve this problem with another way

   var
   a : array [1..10000, 1..10000] of byte;
   n, min : byte;
   i, j, k, i1, L, Lpark, x, y, eni : word;

begin
   read(L, Lpark);
   read(n);
   for i := 0 to n-1 do
     begin
       read(min, eni, x, y);
       for j := 0 to eni-1 do
       for k := 0 to eni-1 do
       a[x+j, y+k] := min;
     end;
   L := L - Lpark;
   min := 255;
   for i := 0 to L do
   for j := 0 to L do
     begin
       n := 1;
         for k := 1 to Lpark do
         for i1 := 1 to Lpark do
           if n < a[k+i, i1+j] then n := a[k+i, i1+j];
       if min > n then min := n;
     end;
  if min > 100 then writeLn('IMPOSSIBLE')
  else writeLn(min);
end.
thx.

#include <stdio.h>
#include <string.h>

const int MAXM = 100;


struct Occupied
{
    int x;
    int y;
    int size;
    int im;
};

Occupied occupied[MAXM]= {0};

void main ()
{
    int L = 0;
    int A = 0;
    int M = 0;

    //FILE * fin = fopen ("E:/Algorithm/Timus/data.txt", "r");
    FILE * fin = stdin;

    fscanf (fin, "%d%d%d", &L, &A, &M);

    int i = 0;
    int j = 0;
    int k = 0;

    for (i = 0; i < M; i++)
    {
        fscanf (fin, "%d%d%d%d", &occupied[i].im, &occupied[i].size, &occupied[i].x, &occupied[i].y);
    }

    int max = 0;
    int min = 0;

    for (i = 1; i <= L - A + 1; i++)
    {
        for (j = 1; j <= L - A + 1; j++)
        {
            int max = 0;
            bool contain255 = false;
            bool intersected = false;
            for (k = 0; k < M; k++)
            {
                if (occupied[k].x + occupied[k].size -1 < i || occupied[k].y + occupied[k].size - 1 < j ||
                    occupied[k].x > i + A - 1 || occupied[k].y > j + A -1)
                {
                    continue;
                }
                intersected = true;

                if (occupied[k].im == 255)
                {
                    contain255 = true;
                    break;
                }

                if (max == 0 || occupied[k].im > max)
                {
                    max = occupied[k].im;
                }
            }

            if (!contain255 && !intersected)
            {
                max = 1;
            }

            if (!contain255)    1
            {
                if (max != 0 && (max < min || min == 0))
                {
                    min = max;
                }
            }

        }
    }

    if (min > 100 || min == 0)
    {
        printf ("IMPOSSIBLE");
    }
    else
    {
        printf ("%d\n", min);
    }
}

After reading the problem,I think out an algo O(MLlogRang)at once.
But it is a bit slow,and the most important thing is that it
need much more momeries than 1000K.
So this algo doesn't work......:(
Later I realize that A,L<=10000 but M<=100!
Maybe it can help......Oh,yes!
Obvous every square has the lowest left point,and then......(think it yourself,hint:use some thought like greedy)
My algo is O(M^3),and it can faster......
Sorry for my poor English,Hope it can help......:)

I have a question what do I output, the sum of importance
or just a piece of land's importance?

The example is that:
 3   2   0   0   0
 2   2   0 100 100
 2   2   0 100 100
94  94   0   0   0
94  94   0   0 255

we have to select a land whose area is 3*3,how can I just
expropriate the land whose importance is 3?

I think the least importance is 3+2+2=7.


Thank you for answering my question?

I don't know why I got WA. Can you let me see ?
Here's my source code.

type
    tab = array [1..202] of longint;

var
   E, XX, YY, Imp: array [1..100] of longint;
   n,Min,Max: longint;

   DX,DY: tab;

   X,Y: array [1..202] of longint;
   nX, nY: longint;

   Re, L, A: longint;


procedure Read_Data;
var
   i: longint;
begin
     read(L,A,n);
     Min := maxint;
     Max := 0;
     for i := 1 to n do begin
       read(Imp[i], E[i],XX[i],YY[i]);
       if Imp[i] < Min then Min := Imp[i];
       if Imp[i] > Max then Max := Imp[i];
       DX[i*2-1] := XX[i];
       DX[i*2] := XX[i]+E[i];
       DY[i*2-1] := YY[i];
       DY[i*2] := YY[i]+E[i];
     end;
     DX[2*n+1] := 1;
     DX[2*n+2] := L+1;
     DY[2*n+1] := 1;
     DY[2*n+2] := L+1;
end;


procedure QSort(l,r: integer; var A: tab);
var
   i,j: integer;
   x,k: longint;
begin
     i := l;     j := r;
     x := A[(l+r) div 2];
     repeat
       while A[i] < x do i := i + 1;
       while x < A[j] do j := j - 1;
       if i <= j then begin
         k := A[i];  A[i] := A[j];  A[j] := k;
         i := i + 1;  j := j - 1;
       end;
     until i > j;
     if i < r then QSort(i,r,A);
     if l < j then QSort(l,j,A);
end;


function Common1(x1,l1, x2,l2: longint): boolean;
begin
     Common1 := true;
     if (x1<=x2) and (x2+l2<=x1+l1) then exit;
     if (x2<=x1) and (x1+l1<=x2+l2) then exit;
     if (x2<x1) and (x1<x2+l2) then exit;
     if (x2<x1+l1) and (x1+l1<x2+l2) then exit;
     Common1 := false;
end;


function Common(x1,y1,l1, x2,y2,l2: longint): boolean;
begin
     Common := Common1(x1,l1,x2,l2) and Common1(y1,l1,y2,l2);
end;


procedure Solve;
var
   i,j,k,h: longint;
begin
     nX := 1;
     X[nX] := DX[1];
     for i := 2 to 2*n+2 do begin
       if DX[i]+A > L+1 then break;
       if DX[i] <> DX[i-1] then begin
         nX := nX+1;
         X[nX] := DX[i];
       end;
     end;

     nY := 1;
     Y[nY] := DY[1];
     for i := 2 to 2*n+2 do begin
       if DY[i]+A > L+1 then break;
       if DY[i] <> DY[i-1] then begin
         nY := nY+1;
         Y[nY] := DY[i];
       end;
     end;

     Re := maxint;
     for i := 1 to nX-1 do
       for j := 1 to nY-1 do begin
         {X[i],Y[j]  left down corner}
         h := Min;
         for k := 1 to n do
           if (h < Imp[k]) and Common(X[i],Y[j],A, XX[k],YY[k],E[k])
                then h := Imp[k];
         if h < Re then Re := h;
         if Re=Min then exit;
       end;
end;


procedure Write_Result;
begin
     if Re > 100 then writeln('IMPOSSIBLE')
       else writeln(Re);
end;


begin
     Read_Data;
     if A<L then begin
       QSort(1,2*n+2, DX);
       QSort(1,2*n+2, DY);
       Solve;
     end else Re := Max;
     Write_Result;
end.

Here is my code:
{$r-,s-,q-}

type
 owner=record
        x,y,le:integer;
        import:byte;
       end;
var
 member:array[1..100] of owner;
 n,l,m:integer;

procedure init;
 var
  i:integer;
 begin
  fillchar(member,sizeof(member),0);
  read(n,l);
  read(m);
  for i:=1 to m do
   with member[i] do read(import,le,x,y);
 end;

function touch(x1,x2,y1,y2,x3,x4,y3,y4:integer):boolean;
 begin
  if (((x1>x4) or (x2<x3)) or ((y1>y4) or (y2<y3))) and
     (not ((x1>=x3) and (x2<=x4) and (y1>=y3) and (y2<=y4))) and
     (not ((x3>=x1) and (x4<=x2) and (y3>=y1) and (y4<=y2))) then
   touch:=false
    else
    touch:=true;
 end;

procedure solve;
 var
  i,j,k:integer;
  max,min:byte;
  x1,x2,x3,x4,y1,y2,y3,y4:integer;
  t:boolean;
 begin
  min:=255;
  for i:=1 to n-l+1 do
   for j:=1 to n-l+1 do
    begin
     max:=0;
     x1:=j;x2:=j+l-1;
     y1:=i;y2:=i+l-1;
     for k:=1 to m do
      with member[k] do
      begin
       x3:=x;x4:=x+le-1;
       y3:=y;y4:=y+le-1;
       t:=touch(x1,x2,y1,y2,x3,x4,y3,y4);
       if t and (import>max) then max:=import;
       if max>min then break;
      end;
     if max<min then min:=max;
    end;
  if min<=100 then writeln(min)
   else writeln('IMPOSSIBLE');
 end;

begin
 init;
 solve;
end.

I am getting compilation error, but I CAN compile it?

#include <fstream.h>
#include <stdlib.h>
#include <mem.h>
//ifstream fin("square.dat");
short l,a,m, imp[100],size[100],x[100],y[100];
char f[10001]; short s[2][10001];

inline short min3(short a, short b, short c)
{
    return a<b ? (a<c?a:c) : (b<c?b:c);
}

void trace(int r, int u)
{
    int i,j,g;
    memset(f+1,1,l);
    for(i=0; i<m; i++) if(imp[i]>u && y[i]<=r && r<y[i]+size[i])
    {
        g=x[i]+size[i];
        for(j=x[i]; j<g; j++) f[j]=0;
    }
}

void find(int u)
{
    int i,j,b1,b0;
    trace(1,u);
    if(a==1)
        for(i=1; i<=l; i++)
        {
            if(f[i]) {cout << u << endl; exit(0);}
            s[1][i]=0;
        }
    else
        for(i=1; i<=l; i++)s[1][i]=f[i];

    for(j=2; j<=l; j++)
    {
        b1=j&1; b0=1-b1;
        s[b1][0]=0; trace(j,u);

        for(i=1; i<=l; i++)
            if(f[i])
            {
                s[b1][i] = 1+min3(s[b1][i-1],s[b0][i],s[b0][i-1]);
                if(s[b1][i]==a) {cout << u << endl; exit(0);}
            }
            else
                s[b1][i] = 0;
    }
}

void main()
{
    cin >> l >> a >> m;
    char z[101]={0,1};
    for(int i=0; i<m; i++) {cin >> imp[i] >> size[i] >> x[i] >> y[i]; z[imp[i]]=1;}
    for(i=1; i<=100; i++) if(z[i]) find(i);
    cout << "IMPOSSIBLE" << endl;
}

#include <stdio.h>

int l, m, n, min, max;
int land[100][4];

int getmax(int x, int y)
{
  int k, maxx;
  maxx = 1;
  for (k = 0; k <= m; k++)
  {
    if (x + l <= land[k][2] || y + l <= land[k][3] || x >=
land[k][2] + land[k][1] || y >= land[k][3] + land[k][1])
      continue;
    else
      {
    if (land[k][0] > 100)
      return 256;
    else
      if (land[k][0] > maxx)
        maxx = land[k][0];
      }
  }
  return maxx;
}

void main()
{
  int i, j, p, q, r, s;
  scanf("%d%d", &n, &l);
  n--;
  scanf("%d", &m);
  m--;
  for (i = 0; i <= m; i++)
  {
    scanf("%d%d%d%d", &p, &q, &r, &s);
    r--;
    s--;
    land[i][0] = p;
    land[i][1] = q;
    land[i][2] = r;
    land[i][3] = s;
  }
  min = 255;
  for (i = 0; i <= n - l; i++)
  {
    for (j = 0; j <= n - l; j++)
    {
      max = getmax(i, j);
      if (max < min) min = max;
    }
  }
  if (min > 100) printf("IMPOSSIBLE\n"); else printf("%
d\n", min);
}

Type Arr                        = record
          X,Y                   : Integer;
          P                     : Byte;
          L                     : Integer;
     End;
Var N,L,M                       : Integer;
    Land                        : Array[1..100] of Arr;
    S1,S2                       : Array[1..200] of Integer;
    Total1,Total2               : Integer;

Procedure Init;
Var i,j : Integer;
Begin
  Readln(N,L);
  Readln(M);
  For i := 1 to M do
    Readln(Land[i].P,Land[i].L,Land[i].X,Land[i].Y);
End;

Procedure Main;
Var i,j,k : Integer;
    T     : Arr;
    T2    : Integer;
    Max   : Byte;
    Min   : Byte;
    Yes   : Boolean;
Begin
  Min := 255;
  For i := 1 to N-L do
    For j := 1 to N-L do
      Begin
        Max := 0;
        For k := 1 to M do
          If (i+L<=Land[k].X) or (i>=Land[k].X+Land[k].L) or
             (j+L<=Land[k].Y) or (j>=Land[k].Y+Land[k].L)
then Continue
             else If Land[K].P>Max then
               Begin
                 Max := Land[K].P;
                 If Max>Min then Break;
               End;
        If Max<Min then
          Begin
            Min := Max;
          End;
      End;
  If Min<=100 then Writeln(Min)
              else Writeln('IMPOSSIBLE');
End;

Begin
  Init;
  Main;
End.