## 10020 - Minimal coverage

Moderator: Board moderators

wanderley2k
New poster
Posts: 28
Joined: Mon Mar 01, 2004 11:29 pm

### Re: Test Cases

Sedefcho wrote:
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
I didn

Darwish
New poster
Posts: 2
Joined: Wed May 23, 2007 6:19 pm

### WA

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;
int mark, 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),
(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
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:
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]
Now I lay me down to sleep...
my profile

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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
New poster
Posts: 15
Joined: Tue Sep 25, 2007 3:07 am
Location: Astana, Kazakhstan
Contact:

### TLE after a week of struggle

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
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

### Re: 10020 - Minimal Coverage

i use only integers greedy and get accepted.

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Contact:

### Re: 10020 - Minimal Coverage

can u give some critical i/o?
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

expert
New poster
Posts: 1
Joined: Sat Jun 13, 2009 11:09 pm

### Re: 10020 - Minimal Coverage

"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;
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[i1]=lx;darray[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[i]<=cor && darray[i]>=cor)
{  //eligible to use this length of string
if(max1<darray[i])
{  max1=max(max1,darray[i]);index=i;
}
else
{   if(max1==darray[i] && darray[index]>darray[i])
{   index=i;
}
}
}
}
if(index==-10)
{  //no string that can be used
val=0;break;
}
else
{  cor=max1;cnt++;
x.push_back(darray[index]);y.push_back(darray[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
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

### Re: 10020 - Minimal Coverage

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;
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;
mend=nend;
nend=-1;
idx=-1;

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

}

}
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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 10020 - Minimal Coverage

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

satyaanveshi
New poster
Posts: 2
Joined: Fri Dec 11, 2009 4:28 pm

### Re: 10020 - Minimal Coverage

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],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],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];
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];
cin>>mat[j];
if(mat[j] ==0 && mat[j]==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]>ans[qq])
{
long temp=ans[tt];
ans[tt]=ans[qq];
ans[qq]=temp;

temp=ans[tt];
ans[tt]=ans[qq];
ans[qq]=temp;
}
}
}
//Bubble Sort Ends

for(long k=1;k<=terms;k++)
cout<<ans[k]<<" "<<ans[k]<<endl;

}

if(i!=test)
cout<<endl;
}

}

// Greedy Algorithm
void greedy(long l,long r,long mat[MAX],long size)
{
if(l==r)
return;

long dist=0,dist1;
long mark;

for(long i=1;i<=size;i++)
{
dist1= min(r,mat[i])-  max(l,mat[i]);
if(dist1>dist)
{
dist=dist1;
mark=i;
}
}

if(dist==0)
{
resultant=false;
return;
}

terms++;
ans[terms]=mat[mark];
ans[terms]=mat[mark];

greedy(l,max(l,mat[mark]),mat,size);
greedy(min(r,mat[mark]),r,mat,size);
}
``````

valkov
New poster
Posts: 20
Joined: Tue Jul 20, 2010 3:11 pm

### Re: 10020 - Minimal Coverage

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
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 10020 - Minimal Coverage

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

mgavin2
New poster
Posts: 43
Joined: Sat Jul 28, 2012 6:29 pm

### Re: 10020 - Minimal Coverage

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

``````
all that matters is AC

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10020 - Minimal Coverage

Input:

Code: Select all

``````1

10
0 8
1 9
8 10
0 0``````
Correct output:

Code: Select all

``````2
0 8
8 10``````
Check input and AC output for thousands of problems on uDebug!