10020 - Minimal coverage

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10020 - Minimal coverage

Post by Mahbub » Thu Nov 07, 2002 6:13 am

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

Post by Shahab » Wed Nov 20, 2002 9:51 am

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

10020

Post by sidky » Sat Jan 04, 2003 6:17 pm

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:

Post by arnsfelt » Sat Jan 04, 2003 9:57 pm

Use the Gready approch.

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

Mmm

Post by Miguel Angel » Tue Jan 07, 2003 4:33 am

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.
:D Miguel & Marina :D

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

Re: Mmm

Post by arnsfelt » Tue Jan 07, 2003 10:59 am

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.

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Thu Feb 06, 2003 12:54 pm

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

Post by sidky » Thu Feb 06, 2003 5:09 pm

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

Post by Amir Aavani » Mon Mar 31, 2003 8:07 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! :wink:

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

Post by miras » Wed Dec 17, 2003 5:42 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....


Regrads
MIras
:lol:

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

Post by miras » Wed Dec 17, 2003 5:49 pm

wait..

I got AC....

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

Post by miras » Wed Dec 17, 2003 5:54 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. :lol: gdynia.pl

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

Post by miras » Wed Dec 17, 2003 5:55 pm


sidky
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:

Post by sidky » Thu Dec 18, 2003 8:50 am

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

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

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

Post by Tomislav Novak » Fri May 21, 2004 8:18 pm

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

Post Reply

Return to “Volume 100 (10000-10099)”