Tahlil's blog

By Tahlil, 12 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +18
  • Vote: I do not like it

By Tahlil, 13 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • -4
  • Vote: I do not like it

By Tahlil, 13 years ago, In English

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 :)

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By Tahlil, 14 years ago, In English
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 .

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By Tahlil, 14 years ago, In English
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 .


Full text and comments »

  • Vote: I like it
  • +6
  • Vote: I do not like it

By Tahlil, 14 years ago, In English
Can anyone please suggest me some Bitmask problems other than those of UVA site. It would be a great help :)

Thank You.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By Tahlil, 14 years ago, In English
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[110],arr [110];
int flg[110];
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;
}

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By Tahlil, 14 years ago, In English
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  :).

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By Tahlil, 14 years ago, In English
Can anyone give me some nim game problems link of Basic to advance level ?
Thank You :)

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it