## 10020 - Minimal coverage

Moderator: Board moderators

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Looks like your input handling is ok, so your array size(s) might be too small. You can always use assert() to test it.
[c]#include <assert.h>

...

Tomislav Novak
New poster
Posts: 44
Joined: Fri Feb 20, 2004 5:52 pm
I've added assert like you suggested and submitted the problem, but it resulted again in SIGSEGV...

I've increased array sizes anyway, but now I've got wrong answer...

Do you have any ideas?

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Contact:
I was having the same problem. By using assert() and about 10-15 submissions I have found that my mistake was kind of stupid. It was not with my array size but with input taking.

R can be less than 0 and L can be greater than M

I checked for L < 0 and R > M but the previous two checks was not in my code. So for line segments like (10000, 20000) or (-20000, -10000) I get SIGSEGV.

I hope this works for u as well.
Where's the "Any" key?

Tomislav Novak
New poster
Posts: 44
Joined: Fri Feb 20, 2004 5:52 pm
I think I've been getting SIGSEGV because of the
[c]
line lines[50000];
[/c]
and the problem states that the maximum number of lines is 100000.

I've fixed it now. However, now I'm getting WA. I guess my greedy approach is wrong (sort by increasing x coordinate; if two coordinates are same, sort by decreasing y coordinate; always pick the first segment that is compatible with the previous ones).

Help!

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Contact:
All the points stated in this problem will be on the X axes, so all Y co-ordinates should be zero. I dont know what did u mean by X-Y coordinates?

My algorithm was to get to the highest point possible from each current position. Hope this will help.
Where's the "Any" key?

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:
May someone please give me some i/o for this problem? I'm getting SIGSEV but am not quite sure why (I tried putting assert's all over the place but still no SIGABRT).

Also, if you're feeling giving and also wouldn't mind taking a look at my source code, here it is :)

[c]
AC
[/c]

Thanks.
Last edited by Minilek on Thu Aug 19, 2004 11:00 am, edited 1 time in total.

Tomislav Novak
New poster
Posts: 44
Joined: Fri Feb 20, 2004 5:52 pm
Solaris wrote:All the points stated in this problem will be on the X axes, so all Y co-ordinates should be zero. I dont know what did u mean by X-Y coordinates?
My algorithm was to get to the highest point possible from each current position. Hope this will help.
Oops... What I ment actually by X was the left coordinate (L), and Y was the right coordinate(R)...

I fixed it yesterday and got AC. Used the same algorithm as yours - set 'current' to 0, find the line segment with left coordinate <= current and right coordinate the rightmost possible; then i updated current with the right coordinate of that segment, and repeated this until left > current

Minilek wrote:
I'm getting SIGSEV but am not quite sure why (I tried putting assert's all over the place but still no SIGABRT).

Code: Select all

Program received signal SIGSEGV, Segmentation fault.
0x080485a1 in main () at minilek.c:32
32               best->l = best->r = -1;

Your problem is that you have
[c]
seg *best;
[/c]
and you don't allocate memory for it... Just add a malloc somewhere in the beginning of your main() and it should work.

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:
ah thanks - AC now. i only learned C from these online contests so i'm still newb at so many things

KvaLe
New poster
Posts: 30
Joined: Sun May 01, 2005 7:45 pm

### 10020

I use greed algorithm.
Here is my code:

Code: Select all

#include <stdio.h>
#include <stdlib.h>

#define MaxN 100000

void Swap (long *A, long *B) { long C = *A; *A = *B; *B = C; }

int main (void) {
long I, J, T, M, N, K, OK, Sol, L [MaxN], R [MaxN], X [MaxN], Y [MaxN];
scanf ("%d", &T);
for (; T > 0; T--) {
scanf ("%d", &M);
N = 0;
while (scanf ("%d%d", &L [N], &R [N]) != EOF) {
if (! L [N] && ! R [N]) break;
if (L [N] > R [N]) Swap (&L [N], &R [N]);
if (N > 0 && L [N-1] == L [N] && R [N-1] < R [N]) R [N-1] = R [N--];
for (I = N; L [N] < L [N-1] && I > 0; I--) Swap (&L [N-1], &L [N]), Swap (&R [N-1], &R [N]);
N++;
}
Sol = 0;
for (I = K = 0; I < N && K < M; I = J) {
OK = K;
for (J = I; L [J] <= OK && R [J] >= OK && J < N; J++)
if (R [J] > K) K = R [J];
if (OK != K) X [Sol] = L [J-1], Y [Sol] = R [J-1], Sol++;
else { Sol = 0; break; }
}
printf ("%d\n", Sol);
for (I = 0; I < Sol; I++) printf ("%d %d\n", X [I], Y [I]);
if (T > 1) printf ("\n");
}
} 
Giorgi Lekveishvili

sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai
i got wa too..

need some sample input and output

Code: Select all

//10020 Minimal coverage
#include <iostream>
#include <cstdlib>
using namespace std;
struct Segment
{
long l,r;
};
Segment segment[100000];
long choose[100000];
int compare(const void *a,const void *b)
{
Segment *p=(Segment*)a;
Segment *q=(Segment*)b;
if(p->l > q->l)
return 1;
else
if(p->l < q->l)
return -1;
else
if(p->r < q->r)
return -1;
else
if(p->r > q->r)
return 1;
else
return 0;
}

int main(int argc,char *argv[])
{
long M,n,s;
long i;
long l,r;
long curLeft;
long maxRight,pos;
long testCase;
cin>>testCase;
while(testCase-->=1)
{
cin>>M;
n=0;
cin>>l>>r;
while(l!=0 || r!=0)
{
if(!(l>M || r<0))
{
segment[n].l=l;
segment[n].r=r;
n++;
}
cin>>l>>r;
}
qsort(segment,n,sizeof(Segment),compare);

curLeft=0;
maxRight=-1;
pos=0;
s=0;
for(i=0;i<n;i++)
{
if(segment[i].l<=curLeft)
{
if(segment[i].r>maxRight)
{
pos=i;
maxRight=segment[i].r;
}
}
else
{
if(maxRight==-1)
{
break;
}
else
{
choose[s]=pos;

s++;
curLeft=segment[pos].r;
maxRight=-1;
}
}
}
choose[s]=pos;
s++;
curLeft=segment[pos].r;
maxRight=-1;

if(curLeft>=M)
{
cout<<s<<endl;
for(i=0;i<s;i++)
cout<<segment[choose[i]].l<<" "<<segment[choose[i]].r<<endl;
}
else
cout<<0<<endl;
cout<<endl;
}
}



Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Code: Select all

In the following lines, the coordinates of segments, sorted by their left end (Li), should be printed in the same format as in the input.
They talk about "format", so the Li and Ri numbers are not integers.
Check the problem statement. Nowhere in the problem description
is said that L and R are integers. I also had that problem
before. Now, it seems I have another one

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

### Test Cases

I got ACC after 3-4 hours of fighting with this one
although it is not a difficult problem.

Some test cases for you. Pay attention to the first two of them.
Strictly taken, I give a logically incorrect answer to the second
test case as I assume a double number X to be equal to 0 if and
only if its ABS VALUE is <= 0.000001. But this is OK.
You may safely do the same. Be careful when comparing the

INPUT

Code: Select all

10

4
-1 3.1
0 1
0 2.1
2.1 3
3.100002 4
0 0

4
-1 3.1
0 1
0 2.1
2.1 3
3.1000002 4
0 0

4
-1.100101 3
0.557 1
1.1 2
2 3
2.99 4.141414141414141
0 0

1
-1.000 0.11
-5 -3.2
2 5.7
0 0

1
-1 0
-10.1000 0.25
0.2499999 1
0 0

5
0 3
0 4
4 5
0 0

4
-1 3.1
0 1
0 2.1
2.1 3
3.099999 4
0 0

4
0 1
1 20
1 19
0 0

5
0 1
3 5
-10 4.2
4.1 11
0 0

1
-1 -2
0 1
0 0


OUTPUT

Code: Select all

0

2
-1 3.1
3.1000002 4

2
-1.100101 3
2.99 4.141414141414141

0

2
-10.1000 0.25
0.2499999 1

2
0 4
4 5

2
-1 3.1
3.099999 4

2
0 1
1 20

2
-10 4.2
4.1 11

1
0 1

chops
New poster
Posts: 9
Joined: Sat Jan 29, 2005 10:48 pm
Location: dhaka
Contact:
can someone help me.
I got WA.

Code: Select all


#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define SIZE 100001
#define EPS 1e-6

typedef struct {
double l,r;
char one[17];
char two[17];

}point;

point arr[SIZE];
int pos[SIZE];

void refresh()
{
long i;
for(i=0;i<SIZE;i++){arr[i].l=arr[i].r=pos[i]=0;}
}

int comp(const void *a,const void *b)
{
if (((point *)a)->l>((point *)b)->l) return 1;
if (((point *)a)->l<((point *)b)->l) return -1;
if (((point *)a)->l==((point *)b)->l)
{
if (((point *)a)->r<((point *)b)->r)return 1;
if (((point *)a)->r>((point *)b)->r) return -1;
}
return 0;
}

void main()
{
long N,i,num,j;
double a,b,M,cur_r,temp;
char p[17],q[17];

/*freopen("d:\\in10020t.txt","r",stdin);
freopen("d:\\out10020.txt","w",stdout);
clrscr();*/

scanf("%ld",&N);

while(N-->0)
{
scanf("%lf",&M);
i=0;
while(scanf("%s %s",p,q)==2)
{

sscanf(p,"%lf",&a);
sscanf(q,"%lf",&b);

if(a+b==0.0)break;

if(a<0.0 && b<=0.0)continue;

if(a>b)
{
temp=a;a=b;b=temp;
strcpy(arr[i].one,q);
strcpy(arr[i].two,p);
}

strcpy(arr[i].one,p);
strcpy(arr[i].two,q);

if(a<=M)
{
if(fabs(a)>=EPS)arr[i].l=a;
else {arr[i].l=0;}
arr[i].r=b;
i++;
}
}
qsort(arr,i,sizeof(point),comp);

cur_r=0;
num=0;

for(j=0;j<i;j++)
{
if((arr[j].l<=cur_r || arr[j].l-cur_r<=EPS) && arr[j].r>cur_r )
{
num++;
pos[j]=1;
cur_r=arr[j].r;
}
if(cur_r>=M)break;
}

if(cur_r>=M)
{
printf("%ld\n",num);
for(j=0;j<i && num;j++)
{
if(pos[j])
{
num--;
printf("%s %s\n",arr[j].one,arr[j].two);
}
}
}
else printf("0\n");

refresh();
if(N>0)printf("\n");
}
}



Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

### check the test cases

I've tried your program on the sample I/O which is posted above.
And well, it crashes even on them. So I suggest you debug
your program using these test cases.

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba
I have tried a lot of test cases(including Sedefcho's in another thread) and my program works fine for them, I need more I/O, please help!!!, anyway this is my source code:

Code: Select all

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

#define MAX 100000

struct line
{
double l, r;
char cl[20];
char cr[20];
};

int n;
double m;
line arre[MAX];

int sort(const void *a, const void *b)
{
struct line *aa = (line*)a;
struct line *bb = (line*)b;

if (aa->l != bb->l)
{
if (aa->l < bb->l)
return -1;
else
if (aa->l > bb->l)
return 1;
else
return 0;
}
else
{
if (bb->r < aa->r)
return -1;
else
if (bb->r > aa->r)
return 1;
else
return 0;
}
}

bool Igual(double a, double b)
{
return fabs(a - b) <= 0.000001;
}

bool Esta(double val, double ini, double fin)
{
return (ini < val || Igual(ini, val)) && (val < fin || Igual(val, fin));
}

int main()
{
int test, t, h, mark[MAX];
char c1[20], c2[20];
double ini, fin;

scanf("%d", &test);

while (test--)
{
scanf("%lf", &m);
scanf("%s %s", &c1, &c2);
sscanf(c1, "%lf", &ini);
sscanf(c2, "%lf", &fin);
n = 0;

while (ini || fin)
{
if (Esta(0, ini, fin) || Esta(m, ini, fin))
{
arre[n].l = ini;
arre[n].r = fin;
strcpy(arre[n].cl, c1);
strcpy(arre[n].cr, c2);
++n;
}

scanf("%s %s", &c1, &c2);
sscanf(c1, "%lf", &ini);
sscanf(c2, "%lf", &fin);
}

if (n)
{
qsort(arre, n, sizeof(line), sort);
mark[t = 1] = 0;

for (int i = 1; i < n; i++)
{
if (t == 1)
{
if (Esta(arre[i].l, arre[mark[1]].l, arre[mark[1]].r) && arre[i].r > arre[mark[0]].r)
mark[++t] = i;
}
else
{
if (Esta(arre[i].l, arre[mark[t - 1]].l, arre[mark[t - 1]].r) && arre[i].r > arre[mark[t]].r)
mark[t] = i;
}

if (arre[mark[t]].l == 0)
{
h = mark[t];
mark[t = 1] = h;
}

if (arre[mark[t]].r > m && Igual(arre[mark[t]].r, m))
break;
}
}
else
puts("0");

if (arre[mark[t]].r > m || Igual(arre[mark[t]].r, m))
{
printf("%d\n", t);

for (int i = 1; i <= t; i++)
printf("%s %s\n", arre[mark[i]].cl, arre[mark[i]].cr);

}
else
puts("0");

if (test > 0)
putchar('\n');
}

return 0;
}