10020 - Minimal coverage

[wanderley2k]

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.

I didn

[Darwish]

Hi all,
I've tried all the test cases I can get and they work fine. Also above test cases work fine. I'm using a greedy algorithm by sorting all the segments by their L. if a tie occurs, by their bigger R. I set current = 0 then Greedily choose the one which Left side <= current, and right side is the rightmost. Please any help possible, this is my 15th WA.

Code: Select all

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cassert>
using namespace std;

/* Test two doubles equality */
#define equal(a, b) (fabs(a - b) <= 0.000001)
//#define equal(a, b) (a == b)

const int NUM_LEN = 20;
struct segment {
	double x, y;	

	/* We'll store the number as a string too to save the "double" format
	 * as said by the problem */
	char x_s[NUM_LEN];
	char y_s[NUM_LEN];
};

/*
 * compare input segments by Left side. If a tie occures, compare by
 * the bigger right side.
 */
int compare(struct segment *A, struct segment *B)
{
	if (!equal(A->x, B->x))
		if (A->x < B->x) return -1;
		else if (A->x > B->x) return 1;
	
	if (!equal(A->y, B->y))
		if (A->y > B->y) return -1;
		else if (A->y < B->y) return 1;
	
	return 0;
}

struct segment pairs[100010];
int mark[100010], nsol, npairs;

int main()
{

	/* Hold the L and R side of a segment here */
	char a_s[NUM_LEN], b_s[NUM_LEN];

	int repeat, i, M, counter;
	double a, b, current;
	double max_len, len;
	int flag, biggest, another_flag;

	scanf("%d", &repeat);
	while (repeat --) {
		scanf("%d", &M);
		assert(M >= 1 && M <= 5000);

		npairs = nsol = counter = 0;
		while (scanf("%s %s", a_s, b_s) != EOF) {
			a = atof(a_s);
			b = atof(b_s);
			assert(strlen(a_s) < NUM_LEN);
			assert(strlen(b_s) < NUM_LEN);

			if (a == 0 && b == 0) 
				break;		
			++ counter;
			assert(a <= b);

			/* Ignore segments out of range or dots (a == b)*/
			if (a >= M || b <= 0 || equal(a, b))
				continue;

			/* Strore values in memory */
			pairs[npairs].x = a;
			pairs[npairs].y = b;
			strcpy(pairs[npairs].x_s, a_s);
			strcpy(pairs[npairs].y_s, b_s);
			npairs++;
		}
		assert(counter <= 100000);

		qsort(pairs, npairs, sizeof(pairs[0]), 
		      (int (*)(const void *, const void *))compare);
		
		/* Greedily choose the one which Left side <= current, and
		 * right side is the rightmost */
		current = 0;		
		for (i = 0; (i < npairs) && (current <= M); i++) {
			flag = 0, max_len = 0;
			another_flag = 0;
			while (i < npairs && 
			       (pairs[i].x < current || equal(pairs[i].x, current)) && pairs[i].y > current) {
				another_flag = 1;
				len = pairs[i].y - current;
				if (len > max_len) {
					flag = 1;
					max_len = len;
					biggest = i;
				}
				++ i;
			}
			/* Decrement the `i' wrongly incremented in last while loop 
			   iteration */
			if (another_flag)
				-- i;
			if (flag) {
				/* Catch this one! */
				mark[nsol ++] = biggest;
				current = pairs[biggest].y;
			}
			else if (pairs[i].x > current) {
				nsol = 0;
				break;
			}
		}

		if (!equal(current, M) && current < M) {
			nsol = 0;
		}
		
		printf("%d\n", nsol);
		for (i = 0; i < nsol; i++)
				printf("%s %s\n", pairs[mark[i]].x_s, pairs[mark[i]].y_s);

		if (repeat != 0)
			printf("\n");
	}
	
	return 0;
} 

Thanks .

[andysoft]

Hello
I have been solving this problem for long, but all that I have got was one WA and six TLEs. I have no idea and asking for help: HOW to avoid TLE and improve my algo.

What I do is:

1) Find a segment with the biggest R, which has L less than current minimum L.
2) To insert a segment to the list, where I store segments, which are used, I use binary search
3) I perform quicksort algo just after reading data
4) I do not count the length of covered area on line each time, instead I just add it every time, which must be faster

Hope there is any way to improve that.
I don't want to post my code as it is always hard to read others' sources.[/list]

[rio]

I'm not sure how your code works, but I feel step2 maybe not needed.

You could post you code or send it to me.
----
Rio

[armansuleimenov]

I have been solving this problem ("Minimal coverage "): http://acm.uva.es/p/v100/10020.html for about a week. I got TLE and WA all the time. I assume the numbers in pairs are doubles. With the last version of my code I got TLE. Could you please point out how I can improve the efficiency and get AC? Here's my code:

Code: Select all

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

// Constants
const int INF = 1000000000;
const long double EPS = 1e-6L;
const long double PI = 3.14159265358979L;

#define For(i,b) for(int i = 0; i < (int)b; ++i)
#define Fori(i,a,b) for(int i = a; i < (int)b; ++i)
#define Ford(i,a,b) for(int i = a; i >=b; --i)
#define All(t) t.begin(),t.end()
#define Sort(a) sort(All(a),cmp)
#define Fill(a,b) memset(a,b,sizeof(a))
#define Forstl(it,x) for(typeof(x.begin()) it=x.begin(); it!=x.end(); ++it)
#define pb push_back
#define equal(a,b) fabs(a-b)<=EPS

using namespace std;

void pr(const vector<pair<string,string> >&v)
{
  cout<<v.size()<<endl;
  For(i,v.size())
  {
    printf("%s %s\n",(v[i].first).c_str(),(v[i].second).c_str());
  }
}

int M;

bool cmp(const pair<string,string>&a,const pair<string,string>&b)
{
  double af,bf,as,bs;
  istringstream in(a.first);
  in >> af;
  in.clear();
  in.str(b.first);
  in>>bf;
  in.clear();
  in.str(a.second);
  in>>as;
  in.clear();
  in.str(b.second);
  in>>bs;
  if(equal(af,bf))
    return (as>bs);
  else
    return (af<bf);
}

double f(const string& a)
{
  double ret;
  istringstream in(a);
  in>>ret;
  return ret;
}

int main ()
{
  //  ifstream fin("p.in");
  int n;
  cin>>n;
  char c;
  For(z,n)
  {
    cin.get(c);
    cin.get(c);
    cin>>M;
    string l,r;
    vector<pair<string,string> >v;
    cin>>l>>r;
    while(!(l=="0"&&r=="0"))
      {
	 v.push_back(make_pair(l,r));
	 cin>>l>>r;
      }
    Sort(v);
    //    pr(v);
    double cur=0;
    vector<pair<string,string> > res;
    for(int i=0;i<(int)v.size()&&cur<M;++i)
    {
      bool flag=0;
      pair<string,string> best("-2147483647.0","-2147483647.0");
      bool flag2=0;
      while(i<(int)v.size()&&(equal(f(v[i].first),cur)||f(v[i].first)<cur)&&(f(v[i].second)>cur))
	 {
	   flag2=1;
	   if(f(v[i].second)>f(best.second))
	     {
		best=v[i];
		flag=1;
	     }
	   ++i;
	 }
      if(flag2)--i;
      if(flag)
	 {
	   res.push_back(best);
	   cur=f(best.second);
	   //   printf("best.second: %s cur: %f\n",(best.second).c_str(),cur);
	 }
      else if(f(v[i].first)>cur)
	 {
	   res.clear();
	   break;
	 }
      //pr(res);
    }
    pr(res);
   if(z!=n-1)cout<<endl;
  }
  return 0;
}

[tryit1]

i use only integers greedy and get accepted.

[kbr_iut]

can u give some critical i/o?

[expert]

"presentation error" on both correct and wrong code

Code: Select all

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string>
#include <fstream>
#define MAX 1000001
using namespace std;
string i2s(int n)
{  stringstream ss;
   ss<<n;
   return ss.str(); 
}
int s2i(string h)
{   stringstream ss;
    ss<<h;
    int n;
    ss>>n;
    return  n;
}
int darray[2][100000];
int main()
{  int t;cin>>t;int first=0;
   while(t--)
   {  if(first==0){first=1;}else{cout<<endl;}
      int m;cin>>m;
      memset(darray,0,sizeof(darray));
      int lx;int rx;int i1=0;
      while(cin>>lx>>rx)
      {   if(lx==0 && rx==0)break;
          darray[0][i1]=lx;darray[1][i1]=rx;i1++;
      }       
      int cnt=0;int cor=0;int val;
      vector<int> x;x.clear();vector<int> y;y.clear();
      bool flag[i1];memset(flag,true,sizeof(flag));
      while(true)
      {   int max1=-1000000;int index=-10;
          for(int i=0;i<i1;i++)
          {   if(flag[i]==true && darray[0][i]<=cor && darray[1][i]>=cor)
              {  //eligible to use this length of string
                 if(max1<darray[1][i])
                 {  max1=max(max1,darray[1][i]);index=i;
                 }
                 else
                 {   if(max1==darray[1][i] && darray[0][index]>darray[0][i])
                     {   index=i;
                     }
                 }
              }
          }   
          if(index==-10)
          {  //no string that can be used
             val=0;break;
          }                         
          else
          {  cor=max1;cnt++;
             x.push_back(darray[0][index]);y.push_back(darray[1][index]);flag[index]=false;
             if(cor>=m)
             { val=cnt;
               break;
             }
          }
      }   
      if(val==0)
      {  cout<<val<<endl;
      }
      else
      {  cout<<val<<endl;
         for(int i=0;i<x.size();i++)
         {  cout<<x[i]<<" "<<y[i]<<endl;
         }
      }
   }             
   system("pause");
}

[tryit1]

Code: Select all

input:
1 4
0 1 2 5
1 3 3 4
0 0

output:
3
0 1
1 3
2 5     

Code: Select all

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cassert>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<deque>
#include<map>
#include<set>
#include<iterator>
#include<streambuf>
#include<sstream>
#include<list>
#include<stack>
#include<ostream>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int main(){
	int no;
	scanf(" %d",&no);
	while(no--){
		
		int M;
		scanf(" %d",&M);
		int i,x,y;
		set<pair<int,int> > s;
		int ans=0,mend=0,nend;
		while( scanf(" %d %d",&x,&y)!=EOF){
			if(x==0 && y==0) break;
			if(y>0 and x<=M){ s.insert(make_pair(x,y)); }
		}
		s.insert(make_pair(M,M+2));
		vector<pair<int,int> > v(s.begin(),s.end());
		vector<int> p;
		nend=-1;
		int idx=-1;
		bool bad=false;
		for(i=0;i<v.size();i++){
			if(v[i].first<=mend && v[i].second>mend){
				if(nend < v[i].second){
					nend=v[i].second;
					idx=i;
				}
			}
			if(v[i].first>mend){
	//		printf("i=%d,idx=%d\n",i,idx);
				if(idx!=-1){
					ans++;
					p.push_back(idx);
				}
				if(mend>=M) break;
				if(nend==-1){ bad=true; break;}
				mend=nend;
				bad=false;
				nend=-1;
				idx=-1;

				if(v[i].first<=mend && v[i].second>mend){
				if(nend < v[i].second){
					nend=v[i].second;
					idx=i;
				}
			}



			}
			
		}
		if(!bad){
		printf("%d\n",ans);
		for(i=0;i<p.size();i++){
			printf("%d %d\n",v[p[i]].first,v[p[i]].second);
		}
		} else printf("0\n");
		
		if(no) printf("\n");
	}
	return 0;
}

Use uvatoolkit for checking your inputs.

This is one way of solving , for other way , read about mf's post on range tree in algorithm section.
range tree is a datastructure that provides
query(int x,int r) , give me the maximum of points ending points R whose starting point <=x. Implementing range tree in C++ is little tricky. I haven't spent much time on it but it should be do-able. Maybe when i do it i'll post it here in algorithms section

[mf]

There's no need to use advanced data structures in this problem. Just sort the intervals, and use a greedy algorithm.

[satyaanveshi]

Hi,
I have checked out all the available test cases, the ones available here and on algorithmist.com. But couldn't understand what's wrong with my program. I used greedy algorithm. Can anyone point out what is wrong with my programme, is there any boundary case which I am missing?
Thanks a lot.

Code: Select all

#include <iostream>
#include <stack>
#include <queue>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
#define MAX 100010
long ans[MAX][3],terms;// ans contains all the terms of the output and terms contains the number of terms in the matrix ans

void greedy(long l,long r,long mat[MAX][3],long size);

bool resultant=true; // if a solution exists

long min(long a,long b)
{
	if(a<b)
	return a;
	else
	return b;
}

long max(long a,long b)
{
	if(a>b)
	return a;
	else
	return b;
}

int main()
{
	long test,m;
	long mat[MAX][3];
	long left,right,j;	
	cin>>test;
	
	for(long i=1;i<=test;i++)
	{
		cin>>m;
		resultant=true;
		terms=0;
		
		for(j=1;;j++)
		{
			cin>>mat[j][1];
			cin>>mat[j][2];
			if(mat[j][1] ==0 && mat[j][2]==0)
			break;
		}
		
		greedy(0,m,mat,j);
		
		if (resultant==false)
		cout<<'0'<<endl;
		else
		{
			cout<<terms<<endl;
			
			// Bubble Sort
			
			for(long tt=1;tt<=terms;tt++)
			{
				for(long qq=tt+1;qq<=terms;qq++)
				{
					if(ans[tt][1]>ans[qq][1])
					{
						long temp=ans[tt][1];
						ans[tt][1]=ans[qq][1];
						ans[qq][1]=temp;
						
						temp=ans[tt][2];
						ans[tt][2]=ans[qq][2];
						ans[qq][2]=temp;
					}
				}
			}						
			//Bubble Sort Ends
			
			for(long k=1;k<=terms;k++)
			cout<<ans[k][1]<<" "<<ans[k][2]<<endl;
			
		}
		
		if(i!=test)
		cout<<endl;
	}
	
}

// Greedy Algorithm
void greedy(long l,long r,long mat[MAX][3],long size)
{
	if(l==r)
	return;
	
	long dist=0,dist1;
	long mark;
	
	for(long i=1;i<=size;i++)
	{
		dist1= min(r,mat[i][2])-  max(l,mat[i][1]);
		if(dist1>dist)
		{
			dist=dist1;
			mark=i;
		}
	}
	
	if(dist==0)
	{
		resultant=false;
		return;
	}
	
	terms++;
	ans[terms][1]=mat[mark][1];
	ans[terms][2]=mat[mark][2];
	
	greedy(l,max(l,mat[mark][1]),mat,size);
	greedy(min(r,mat[mark][2]),r,mat,size);
}

[valkov]

Just got AC on this problem
In this problem long is enough as you read the coordinates ( so no doubles or anything like that ... ).
The greedy approach to solving this problem is really easy.
0. Some preconditions
If segment.end < 0 -> skip
if segment.start > M -> skip
If segment.start <= 0 && segment.end >= M -> print solution/ can be tricky if you stop reading input

Code: Select all

Sort by the starting coordinate of each segment
Set shouldBeCovered = 0,
while(shouldBeCovered < M)  
    get the max covering length (segment.end - shouldBeCovered + 1) segment that segment.start <= shouldBeCovered
    If segment found
        add to the segments that are in the solution
        update shouldBeCovered = segment.end
    else
        No solution can be found

Hint: Segment coordinates must overlap!

Helpful inputs for that (copied from Algorithmist)

Code: Select all

7

1
-1 0
-5 -3
2 5
0 0

1
-1 0
0 1
0 0

10
-2 5
-1 6
-1 3
0 4
1 5
2 6
3 7
7 8
8 10
8 9
0 0

10
-2 5
-1 6
-1 3
0 4
1 5
2 6
3 7
8 10
8 9
0 0

10
2 5
5 3
2 3
2 5
0 0

10
0 10
0 10
0 0

6
0 2
2 4
4 6
6 8
0 0

[Shafaet_du]

Judge data is week ,try submitting in TIMUS: http://acm.timus.ru/problem.aspx?space=1&num=1303

[mgavin2]

FML. I don't know what's wrong. Passes other's inputs. Awesome.

Code: Select all

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>

using namespace std;

//#define DEBUG  //comment this line to pull out print statements
#ifdef DEBUG
#define TAB '\t'
#define debug(a, end) cout << #a << ": " << a << end
#define dbg(end) end
#else
#define debug(a, end)
#define dbg(end)
#endif

typedef pair<int, int> point;
typedef long long int64; //for clarity
typedef vector<int> vi; //?
typedef vector<point> vp; //?
template<class T> void chmin(T &t, T f) { if (t > f) t = f; } //change min
template<class T> void chmax(T &t, T f) { if (t < f) t = f; } //change max

#define UN(v) SORT(v),v.erase(unique(v.begin(),v.end()),v.end())   
#define SORT(c) sort((c).begin(),(c).end())   
#define FOR(i,a,b) for (int  i=(a); i < (b); i++)    
#define REP(i,n) FOR(i,0,n)    
#define CL(a,b) memset(a,b,sizeof(a))
#define CL2d(a,b,x,y) memset(a, b, sizeof(a[0][0])*x*y)

/*global variables*/
vp segments;
int M;

struct cmp
{
    bool operator()(const point& a, const point& b)
    {
        if (a.first == b.first)
            return a.second < b.second;
        return a.first < b.first;
    }
};

/*global variables*/

void dump()
{
    //dump data
    debug(M, endl);
    REP(i, segments.size())
    {
        debug(segments[i].first, TAB);
        debug(segments[i].second, endl);
    }
}

bool getInput()
{
    //get input
    point a;
    scanf("%d", &M);

    do
    {
        scanf("%d %d", &a.first, &a.second);
        if (a.second > 0 && a.first < M) //useless segment, coverage is from 0 to M, therefore this says covers is <= 0
            segments.push_back(a);    
    }
    while (a.first != 0 || a.second != 0);
    
    return true;
}

void process()
{
    //process input
    sort(segments.begin(), segments.end(), cmp());
    dbg(dump());
    vp ans;
    int N = 0, max_cov = 0;
    vp::iterator max_it;
    while (N < M && !segments.empty())
    {
        //get max coverage
        max_it = segments.end();
        max_cov = 0;
        for (vp::iterator it = segments.begin(); it != segments.end(); ++it)
        {
            if (it->first > N || it->second < N)
            {
                debug(it->first, TAB); debug(N, endl);
                continue; //begins in a useless place
            }
            if (it->second - it->first >= max_cov)
            {
                max_cov = it->second - it->first;
                max_it = it;
                debug(max_cov, endl);
            }   
        }
        if (max_it == segments.end()) //no more coverable segments
            break;
        else
        {
            debug(max_it->first, TAB); debug(max_it->second, endl);
            ans.push_back(*max_it);
            N = max_it->second;
            segments.erase(max_it);
        }
    }

    if (N < M)
        ans.clear();
    
    printf("%d\n", (int)ans.size());
    REP(i, ans.size())
    {
        printf("%d %d\n", ans[i].first, ans[i].second);
    }
}

int main()
{
    int nc;
    scanf("%d", &nc);
    while (nc-- > 0)
    {
        getInput();
        process();

        if (nc != 0)
            printf("\n");
        
        /*CLEAR GLOBAL VARIABLES!*/
        segments.clear();
        /*CLEAR GLOBAL VARIABLES!*/
    }

    return 0;
}

[brianfry713]

Input:

Code: Select all

1

10
0 8
1 9
8 10
0 0

Correct output:

Code: Select all

2
0 8
8 10