## 10020 - Minimal coverage

Moderator: Board moderators

Mahbub
New poster
Posts: 26
Joined: Thu Aug 08, 2002 8:04 am

### 10020 - Minimal coverage

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
New poster
Posts: 24
Joined: Sun Nov 10, 2002 2:17 pm

### 10020 - WA

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;
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
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,L[ANum]);
Swap(R,R[ANum]);
Dec(ANum);
Heapify;
End;
End;
Begin
Assign(Input,'10020.in');
ReSet(Input);
For t:=1 to CaseNo do
Begin
Num:=1;
While (L[Num]<>0) Or (R[Num]<>0) do
Begin
If L[Num]>R[Num] then
Swap(L[Num],R[Num]);
Inc(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
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:

### 10020

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

arnsfelt
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:

Miguel Angel
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico

### Mmm

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. Miguel & Marina arnsfelt
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:

### Re: Mmm

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
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
hi

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
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:
My program produces this output:

Code: Select all

``````2
-1 3
3 4

2
0 1
1 19
``````

Amir Aavani
New poster
Posts: 30
Joined: Wed Oct 23, 2002 6:53 am
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
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
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....

MIras miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
wait..

I got AC....

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
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
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
miras@unreg86.lonet.gdynia.pl MIras

sidky
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:
This problem is a special judge problem. It wouldn't matter as long as that solves the problem.

Tomislav Novak
New poster
Posts: 44
Joined: Fri Feb 20, 2004 5:52 pm

### 10020 Minimal coverage - runtime error (multiple input?!)

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;
int solution, 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