gsmcoder97's blog

By gsmcoder97, history, 8 years ago, In English

I have been solving some problems recently and they tend to have the following query at the end:

Given n segments a1,a2 
                 b1,b2
                 .
                 .
                 .
And some numbers of an array x1, x2, x3, . . . 

I want to find the segments in which each of these numbers appear. There might be more than one segment so I want all the segments in which they appear.

How do I approach this question?

Thank you.

Full text and comments »

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

By gsmcoder97, history, 8 years ago, In English
[This](http://codeforces.net/contest/652/problem/E) problem is a very interesting one. 
We have to check whether there exists some path between two nodes in a graph such that that path contains at least one edge with value 1.
After spending a lot of time, I had to see the editorial and was intrigued by the solution and the explanation.
We assume that the two points are present in some two biconnected components of the same graph(Lets say A and B).
After decomposing the graph into biconnected components we apply dfs from component A to component B and find whether the path contains at least one.
If we were not going to use this approach, then we would have to use multiple dfs traversals; perhaps including recursion.
I found this use of biconnected components really interesting.
Does anyone have any collection or references of questions that I can practice on biconnected components in a graph(perhaps constructing a DAG on them etc.)
Thank You

Full text and comments »

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

By gsmcoder97, history, 8 years ago, In English

I started coding square root decomposition myself and submitted my code for Little Elephant And Array(http://codeforces.net/contest/220/problem/B); however, I am getting compilation error. Is there some error in my code? How can I make it more optimal?

struct x{
    int ct[size1]; int mini, maxi;
};
x block[size1];
void cons(int n, int a[]){
    int p=floor(sqrt(n));
    for(int i=0;i<n;i++){block[i/p+1].ct[a[i]]++; block[i/p+1].mini=min(block[i/p+1].mini,a[i]); block[i/p+1].maxi=max(block[i/p+1].maxi,a[i]);}
}
void query(int l,int r,int n, int a[], int &ans){
    int p=floor(sqrt(n));
    int b1=(l-1)/p+1;
    int b2=(r-1)/p+1;
    //int ans=0;
    if(b1==b2){
        map<int,int> v;
        for(int i=(l-1);i<=(r-1);i++)v[a[i]]++;
        map<int,int>::iterator it=v.begin();
        for(;it!=v.end();it++)if(it->second==it->first)ans++;
    }
    else if(b1!=b2){
        map<int,int> v;
        for(int i=l;i<b1*p;i++)v[a[i]]++;
        for(int i=b1;i<b2;i++)for(int j=block[i].mini;j<=block[j].maxi;j++)v[j]+=block[i].ct[j];
        for(int i=b2*p;i<=r;i++)v[a[i]]++;
        map<int,int>::iterator it=v.begin();
        for(;it!=v.end();it++)if(it->second==it->first)ans++;
    }
}
int main(){
    int n,m; cin>>n>>m;
    int a[n]; for(int i=0;i<n;i++)cin>>a[i];
    cons(n,a);
    while(m--){
        int x,b; cin>>x>>b;
        int ans=0;
        query(x,b,n,a,ans); cout<<ans<<endl;
    }
    return 0;
}

Any help is appreciated. Thank you

Full text and comments »

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

By gsmcoder97, history, 8 years ago, In English

I was solving this problem Snow Sellers (http://codeforces.net/contest/48/problem/F) and I am having problem understanding the idea behind it. If I look at the input test case it is as follows: 2 3 10 4 4 4 5 5 8 1 2 5

According to the question, 2 are the number of days for which the winter goes on(sale); 3 are the number of the snow selling companies; and 10 is the amount of the snow he has to buy everyday exactly(not less and not more).

Now, my understanding is as follows: On the starting of the first day The first company was selling 4 cubic metres for 5 bourles; this means 1 cubic metre for 1.25 bourle. The second company was selling 4 cubic metres for 5 bourles; this means 1 cubic metre for 1.25 bourle. The third company was selling 8 cubic metres for 8 bourles; this means 1 cubic metre for 2 bourles. Thus, to buy 10 cubic metres on the first day, he will buy it from the first or second shop for 12.5 bourles.

On the starting of the second day The first company was selling 4 cubic metres for 4 bourles; this means 1 cubic metres for 1 bourle. The second company was selling 4 cubic metres for 3 bourles; this means 1 cubic metre for 0.75 bourle. The third company was selling 4 cubic metres for 3 bourles; this means 1 cubic metre for 0.75 bourle. Thus, to buy 10 cubic metres on the second day, we will buy it from the second or third shop for 7.5 bourles.

Hence, the total amount is 7.5+12.5=20 bourles.

But, the otuput of the first test case is 22. Please help. Thank you.

Full text and comments »

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

By gsmcoder97, history, 8 years ago, In English

I was attempting this question. Kefa and Park but I am getting WA in test case 10. Can anyone please help. Link: http://codeforces.net/contest/580/submission/18113202 Thanks

Full text and comments »

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