10020 - Minimal coverage

[Mahbub]

Wats the idea?

I got WA in greedy approach :
Always taking the line with highest end_x which has a lower left_index than curent covered length..

Thanks
Light

[Shahab]

What's wrong with this ?
I got WA.

Code: Select all

Program P10020;
Const LMAX=1000;
Var CaseNo,m,t,Num,CNum,i,Max,Left:Integer;
    Test:Boolean;
    L,R:Array [1..LMAX] Of Integer;
    Choosed:Array [1..LMAX] Of Boolean;
Procedure Swap(Var a,b:Integer);
Var c:Integer;
Begin
  c:=a;
  a:=b;
  b:=c;
End;
Procedure Sort;
Var ANum:Integer;
  Procedure AddNode;
  Var i:Integer;
  Begin
    Inc(ANum);
    i:=ANum;
    While i>1 do
      If L[i]>L[i Div 2] then
      Begin
        Swap(L[i],L[i Div 2]);
        Swap(R[i],R[i Div 2]);
        i:=i Div 2;
      End
      Else Break;
  End;
  Procedure MakeMaxHeap;
  Var i:Integer;
  Begin
    ANum:=1;
    While ANum<Num do
      AddNode;
  End;
  Procedure Heapify;
  Var i:Integer;
  Begin
    i:=1;
    While i<ANum Div 2 do
    Begin
      If L[i]>L[i*2] then
      Begin
        If L[i]>L[i*2+1] then
          Break
        Else
        Begin
          Swap(L[i],L[i*2+1]);
          Swap(R[i],R[i*2+1]);
          i:=i*2+1;
        End;
      End
      Else
      Begin
        If L[i*2]>L[i*2+1] then
        Begin
          Swap(L[i],L[i*2]);
          Swap(R[i],R[i*2]);
          i:=i*2;
        End
        Else
        Begin
          Swap(L[i],L[i*2+1]);
          Swap(R[i],R[i*2+1]);
          i:=i*2+1;
        End;
      End;
    End;
  End;
Var i:Integer;
Begin
  MakeMaxHeap;
  For i:=1 to Num do
  Begin
    Swap(L[1],L[ANum]);
    Swap(R[1],R[ANum]);
    Dec(ANum);
    Heapify;
  End;
End;
Begin
  Assign(Input,'10020.in');
  ReSet(Input);
  ReadLn(CaseNo);
  For t:=1 to CaseNo do
  Begin
    ReadLn;
    Num:=1;
    ReadLn(m);
    ReadLn(L[Num],R[Num]);
    While (L[Num]<>0) Or (R[Num]<>0) do
    Begin
      If L[Num]>R[Num] then
        Swap(L[Num],R[Num]);
      Inc(Num);
      ReadLn(L[Num],R[Num]);
    End;
    Dec(Num);
    Sort;
    Left:=0;
    i:=1;
    Test:=True;
    CNum:=0;
    FillChar(Choosed,SizeOf(Choosed),0);
    While Left<m do
    Begin
      Max:=i;
      While (L[i]<=Left) And (i<=Num) do
      Begin
        If R[Max]<R[i] then
          Max:=i;
        Inc(i);
      End;
      If (R[Max]<=Left) Or ((i>Num) And (R[Max]<m)) then
      Begin
        Test:=False;
        Break;
      End
      Else
      Begin
        Choosed[Max]:=True;
        Inc(CNum);
        Left:=R[Max];
      End;
    End;
    If Test then
    Begin
      WriteLn(CNum);
      For i:=1 to Num do
        If Choosed[i] then
          WriteLn(L[i],' ',R[i]);
    End
    Else WriteLn(0);
    If t<>CaseNo then
      WriteLn;
  End;
  Close(Input);
End.

[sidky]

I used DP for this problem and it took 6 seconds. Can anyone plz say, how can I make it efficient?

[arnsfelt]

Use the Gready approch.

[Miguel Angel]

My algorithm is the following
* At given left end, take the biggest right end.
* Fill an array of char's to see if they cover the segment at all
* if there's a way to fill the M segment, then DP to get the minimal number of segments..
BUT WA!!!
I have some doubts,
Can the lines overlap??
I have saw about only greedy, but greedy can't be correct at all, at least the tester it's not right.

[arnsfelt]

Miguel Angel:
It's not very clear how your algorithm works.
But, yes - the line segments (of course?) can overlap.
And, yes - the greedy approch can be applied - if done in the right way.

[hank]

hi
I have some questions about this problem.

Code: Select all

if the inpu is:

4
-1 3
0 1
0 2
2 3
3 4
0 0

what should I print?
-------------------------------
and if the input is:

4
0 1
1 20
1 19
0 0

what should I print?

[sidky]

My program produces this output:

Code: Select all

2
-1 3 
3 4 

2
0 1 
1 19 

[Amir Aavani]

i think you got WA because of wrong output,i mean that the problem ask you to write L and R of each line , in the same order as it apear in input

try it!

[miras]

DEAR SIDKEY..

i have solved this problem.. my prog gives same outputs as yours but it gives not

Code: Select all

2 
0 1 
1 19 

but

Code: Select all

2 
0 1 
1 20 

so it means that inputs like this doesn't metter....


Regrads
MIras

[miras]

wait..

I got AC....

[miras]

Your prog. looks ok. but there is one thing that is very easy to discover if u really wont to know write to me:
miras@unreg86.lonet. gdynia.pl

[miras]

miras@unreg86.lonet.gdynia.pl



MIras

[sidky]

This problem is a special judge problem. It wouldn't matter as long as that solves the problem.

[Tomislav Novak]

Hi!

I 'm having really big problems with those multiple input problems lately.

I'm trying to solve 10020 (Minimal coverage) using greedy algorithm and I think my code is OK, but I keep getting runtime error (SIGSEGV, i.e. invalid memory reference).

The problem is marked with yellow color which only means special correction program, although it's written in the input file description that it is a multiple input problem...

Anyhow, here's the code:
[c]
#include <stdio.h>

typedef struct
{
int x, y;
} line;

line lines[50000];
int solution[50000], nsol, nlines;

int cmp(const void *e1, const void *e2)
{
line a, b;

a = *((const line *)e1);
b = *((const line *)e2);

if (a.x < b.x) return -1;
else if (a.x > b.x) return 1;
else if (a.y > b.y) return -1;
else if (a.y < b.y) return 1;
else return 0;
}

int main()
{
int i, j, k, cases, m, current, a, b;

scanf("%d", &cases);
for (k = 0; k < cases; k++)
{
scanf("%d", &m);
nlines = nsol = 0;

while (scanf("%d %d", &a, &b) == 2)
{
if (a == 0 && b == 0) break;
if (a < b)
{
lines[nlines].x = a;
lines[nlines].y = b;
}
else
{
lines[nlines].x = b;
lines[nlines].y = a;
}
nlines++;
}

qsort(lines, nlines, sizeof(line), cmp);

current = 0;

for (i = 0; (i < nlines) && (current < m); i++)
if (lines.x <= current && lines.y > current)
{
solution[nsol++] = i;
current = lines.y;
}
else if (lines.x > current)
{
nsol = 0;
break;
}

if (current < m)
nsol = 0;

printf("%d\n", nsol);
for (i = 0; i < nsol; i++)
printf("%d %d\n", lines[solution].x, lines[solution].y);

if (k < cases - 1) printf("\n");
}

return 0;
}
[/c]

Thanks!

Tomislav