### Tahlil's blog

By Tahlil, 6 years ago, , Hello. My friends and I tried to solve this problem of this website.

http://www.gogeometry.com/problem/problem001.htm

But we could not. Can anyone please provide a proof of this problem? Thanks. By Tahlil, 8 years ago, , You will be given several intervals. Every input of an interval consists of 3 numbers ai,bi,ci where a and b are the starting and ending of the interval. From all the intervals you have to find a set of integers Z which have ci number of common integers between ai and bi . You have to find out the minimum size of Z.

Input:

6 8 3
8 10 3
1 3 1

output : 6

I saw this problem in many sites. But could not solve it. I tried but could not find any solution. Can anyone please explain how to solve this. Thanks very much :)

EDIT : The link of the problem is here http://acm.tju.edu.cn/toj/showp1664.html By Tahlil, 8 years ago, , Hi , I have a very poor knowledge in combinatorics. But I want to improve that. So i need direction how to do that. If anyone can suggest me any book, tutorial, online articles or any other ways so that I can learn combinatorics then it would be very big help. Thanks :) math,
By Tahlil, 8 years ago, , It says for test case 8 in the checker log " wrong output format Unexpected end of file - token expected ".
What does that mean?? And i couldn't understand why my code gives wrong output . And i am sure that the problem is in the function prn() where the move operations are printed. Can any one please help?

Thank you . By Tahlil, 9 years ago, , Wrong problem statement is now almost a regular incident .I hope this will be fixed soon.

And i don't know if anyone else feels this but problem statements are getting hard to understand for me. If its not my problem than i think this also should be fixed . bug,
By Tahlil, 9 years ago, , Can anyone please suggest me some Bitmask problems other than those of UVA site. It would be a great help :)

Thank You. help,
By Tahlil, 9 years ago, , I read the tutorial of contest 27 . But in that time i already coded a solution which is greedy i think. Here is what i do

1) I calculate for each segment, with how many segment it intersects.
2)Then for each segment 1 to m
--if it has min one intersection and if it doesn't intersect with others who are already been put outside and if it is not already been put outside , I color it to keep track of the segments put outside.And i also store this segment so that i can check it with the other segments who will be put outside in the future to check intersection.Then break and go to step 1.

And i do the above process until i find that i can not put anymore segments outside. And at last i check if there is any collision between the segments. If there then i output impossible else i output who are colored as outside and who are not colored as inside :)

But this code fails for test case 23 :(
Is my procedure is ok ?? Can anyone explain please.  Here is my code

#include <sstream>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <string.h>
#define inf 99999999

using namespace std;
typedef struct
{
int x,y,cnt;
}Ind;
Ind ar,arr ;
int flg;
bool fl;
int i,j,ed,mn,mx,node,edge;
void find()  // checking for every segment how many times intersected with other segments
{
int i,j;
fl = 0;
for(i=0;i<edge;i++)
{
ar[i].cnt=0;
if(!flg[i])
for(j=0;j<edge;j++)
{
if(i==j || flg[j])continue;
if(ar[i].x>=ar[j].x && ar[i].y<=ar[j].y)continue;
if(ar[i].x>=ar[j].y || ar[i].y<=ar[j].x)continue;
if(ar[i].x<=ar[j].x && ar[i].y>=ar[j].y)continue;
ar[i].cnt++;
fl = 1;
}
}
}
bool chek(int i)  // checking if puting outside the current segment causes intersection with other segments which are already outside
{
int j;
for(j=0;j<ed;j++)
{
if(ar[i].x>=arr[j].x && ar[i].y<=arr[j].y)continue;
if(ar[i].x>=arr[j].y || ar[i].y<=arr[j].x)continue;
if(ar[i].x<=arr[j].x && ar[i].y>=arr[j].y)continue;
return 0;
}
return 1;
}
int main()
{
//freopen("out.txt","w",stdout);
while(cin>>node>>edge)
{
for(i=0;i<edge;i++)
{
cin>>ar[i].x>>ar[i].y;
mn = min (ar[i].x,ar[i].y);
mx = max (ar[i].x,ar[i].y);
ar[i].x = mn;
ar[i].y = mx;
}
ed=0;
do
{
find();
fl=0;
for(i=0;i<edge;i++)
{
if(ar[i].cnt && chek(i) && !flg[i])
{
arr[ed].x = ar[i].x;
arr[ed++].y = ar[i].y;
flg[i]=1;
fl=1;
break;
}
}
}while(fl);
find();
if(fl)
{
cout<<"Impossible";
return 0;
}
for(i=0;i<edge;i++)
{
//
if(flg[i])cout<<"o";
else  cout<<"i";
}
}
return 0;
} By Tahlil, 9 years ago, , Hi can anyone please explain to me what happens when the usual loosing/wining condition of a nim game is reversed ? Like the person who takes the last stone looses. I can't find any solution to that. How can i find who is the winner or looser at that situation??
Thanks  :). By Tahlil, 9 years ago, ,  