Page 1 of 4
10020 - Minimal coverage
Posted: Thu Nov 07, 2002 6:13 am
by 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
10020 - WA
Posted: Wed Nov 20, 2002 9:51 am
by 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.
10020
Posted: Sat Jan 04, 2003 6:17 pm
by sidky
I used DP for this problem and it took 6 seconds. Can anyone plz say, how can I make it efficient?
Posted: Sat Jan 04, 2003 9:57 pm
by arnsfelt
Use the Gready approch.
Mmm
Posted: Tue Jan 07, 2003 4:33 am
by 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.
Re: Mmm
Posted: Tue Jan 07, 2003 10:59 am
by 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.
Posted: Thu Feb 06, 2003 12:54 pm
by 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?
Posted: Thu Feb 06, 2003 5:09 pm
by sidky
My program produces this output:
Posted: Mon Mar 31, 2003 8:07 am
by 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!
Posted: Wed Dec 17, 2003 5:42 pm
by miras
DEAR SIDKEY..
i have solved this problem.. my prog gives same outputs as yours but it gives not
but
so it means that inputs like this doesn't metter....
Regrads
MIras
Posted: Wed Dec 17, 2003 5:49 pm
by miras
wait..
I got AC....
Posted: Wed Dec 17, 2003 5:54 pm
by 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
Posted: Wed Dec 17, 2003 5:55 pm
by miras
Posted: Thu Dec 18, 2003 8:50 am
by sidky
This problem is a special judge problem. It wouldn't matter as long as that solves the problem.
10020 Minimal coverage - runtime error (multiple input?!)
Posted: Fri May 21, 2004 8:18 pm
by 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