Posted:

**Fri May 21, 2004 9:27 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>

...

[c]#include <assert.h>

...

Page **2** of **4**

Posted: **Fri May 21, 2004 9:27 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>

...

[c]#include <assert.h>

...

Posted: **Sat May 22, 2004 9:06 am**

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?

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

Do you have any ideas?

Posted: **Sat Aug 14, 2004 7:56 am**

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.

R

I checked for L

I hope this works for u as well.

Posted: **Wed Aug 18, 2004 2:41 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!

[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!

Posted: **Wed Aug 18, 2004 9:48 pm**

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.

My algorithm was to get to the highest point possible from each current position. Hope this will help.

Posted: **Thu Aug 19, 2004 5:03 am**

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.

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.

Posted: **Thu Aug 19, 2004 10:07 am**

Oops... What I ment actually by X was the left coordinate (LSolaris 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.

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;
```

[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.

Posted: **Thu Aug 19, 2004 10:54 am**

ah thanks - AC now. i only learned C from these online contests so i'm still newb at so many things

Posted: **Mon May 09, 2005 6:25 pm**

I use greed algorithm.

Here is my code:

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");
}
}
```

Posted: **Wed Jun 08, 2005 4:40 am**

i got wa too..

need some sample input and output

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;
}
}
```

Posted: **Fri Jun 24, 2005 3:23 pm**

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.`

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

Posted: **Fri Jun 24, 2005 5:03 pm**

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

values of your double variables.

INPUT

OUTPUT

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

values of your double variables.

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
```

Posted: **Fri Jul 01, 2005 6:00 pm**

can someone help me.

I got WA.

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");
}
}
```

Posted: **Fri Jul 01, 2005 6:04 pm**

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.

And well, it crashes even on them. So I suggest you debug

your program using these test cases.

Posted: **Mon Jul 04, 2005 8:17 am**

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:

waiting for your help,

Yandry.

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;
}
```

Yandry.