10020 - Minimal coverage

[little joey]

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]

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]

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.

[Tomislav Novak]

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]

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.

[Minilek]

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.

[Tomislav Novak]

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

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]

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

[KvaLe]

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

[sunnycare]

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]

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]

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

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]

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]

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]

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

waiting for your help,

Yandry.