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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » 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>

...

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

Post by Tomislav Novak » 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? ;)

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » 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.
Where's the "Any" key?

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

Post by Tomislav Novak » 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! ;)

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » 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.
Where's the "Any" key?

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

Post by Minilek » 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.
Last edited by Minilek on Thu Aug 19, 2004 11:00 am, edited 1 time in total.

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

Post by Tomislav Novak » Thu Aug 19, 2004 10:07 am

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:

Post by Minilek » 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 :oops:

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

10020

Post by KvaLe » Mon May 09, 2005 6:25 pm

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

Post by sunnycare » Wed Jun 08, 2005 4:40 am

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

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

Post by Sedefcho » 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.
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 :)

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

Test Cases

Post by Sedefcho » 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

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:

Post by chops » Fri Jul 01, 2005 6:00 pm

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




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

check the test cases

Post by Sedefcho » 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.

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

Post by neno_uci » 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:

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.

Post Reply

Return to “Volume 100 (10000-10099)”