Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

mahim007's blog

By mahim007, history, 3 years ago, In English,

problem statement says,

Let

fn = a1 * fn-1 + b1 * fn-2 + c1 * gn-3

gn = a2 * gn-1 + b2 * gn-2 + c2 * fn-3

Find fn % M and gn % M. (% stands for the modulo operation.)

i tried, but can not derive the base matrix.actually i find it difficult when recurrent relation depends on more than one relation.how to derive the base matrix M for this kind of problem where one recurrent relation depends on one or more other recurrent relations?

please help :) :)

Read more »

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

By mahim007, history, 3 years ago, In English,

strange behaviour! my binary search actually gets stuck for test case number 84. i tried to debug it by printing some values but it just does nothing.i can't find out the bug.

problem link: 758C - Unfair Poll my submission: 24099377

Read more »

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

By mahim007, history, 3 years ago, In English,

problem link :510C - Fox And Names my solution : 23772782

what i do here is marking new character coloumn wise and building the sequence. But getting wrong answer in a large test case,can't find out the bug,any help will be appreciated.

Read more »

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

By mahim007, history, 3 years ago, In English,

here is my code: 23522947 problem link: 750C - New Year and Rating i used left boundary and right boundary for managing lowest and highest possible values.but can't manage to get accepted. what is wrong in my logic,someone help me to find that.

Read more »

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

By mahim007, history, 5 years ago, In English,

problem:link my submission:link

Read more »

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

By mahim007, history, 5 years ago, In English,

problem=>link my code is given below.

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mx 20009
ll vis[2*mx],order[2*mx],finish[2*mx],t=0,leader[2*mx],parent;
vector<ll>G[2*mx],GR[2*mx],ans;
map<ll,int>M;

void dfs_rev(ll u){
    vis[u]=1;
    for(ll i=0;i<GR[u].size();i++){
        ll v=GR[u][i];
        if(!vis[v]){
            dfs_rev(v);
        }
    }
    t++;
    finish[u]=t;
}

void dfs(ll u){
    vis[u]=1;
    leader[u]=parent;
    for(ll i=0;i<G[u].size();i++){
        ll v=G[u][i];
        if(!vis[v]){
            dfs(v);
        }
    }
}

int SCC(ll u,ll v){
    return leader[u]==leader[v];
}

int main(){
    ll T,t,i,j,k,u,v,n,e;
    scanf("%lld",&T);
    for(t=1;t<=T;t++){
        scanf("%lld %lld",&e,&n);
        for(i=1;i<=e;i++){
            scanf("%lld %lld",&u,&v);
            if(u>0){
                if(v>0){
                    G[n+u].push_back(v); G[n+v].push_back(u);
                    GR[v].push_back(n+u); GR[u].push_back(n+v);
                }
                else{
                    G[n+u].push_back(n-v); G[-v].push_back(u);
                    GR[n-v].push_back(n+u); GR[u].push_back(-v);
                }
            }
            else{
                if(v>0){
                    G[-u].push_back(v); G[n+v].push_back(n-u);
                    GR[v].push_back(-u); GR[n-u].push_back(n+v);
                }
                else{
                    G[-u].push_back(n-v); G[-v].push_back(n-u);
                    GR[n-v].push_back(-u); GR[n-u].push_back(-v);
                }
            }
        }

        memset(vis,0,(2*n+1)*sizeof(ll));
        for(i=2*n;i>0;i--){
            if(!vis[i]){
                dfs_rev(i);
            }
            order[finish[i]]=i;
        }

        memset(vis,0,(2*n+1)*sizeof(ll));
        for(i=2*n;i>0;i--){
            if(!vis[order[i]]){
                parent=order[i];
                dfs(order[i]);
            }
        }

        for(i=2*n;i>0;i--){
            u=order[i];
            if(u>n){
                if(SCC(u,u-n)) break;
                if(M.find(leader[u])==M.end()){
                    M[leader[u]]=1;
                    M[leader[u-n]]=0;
                }
            }
            else{
                if(SCC(u,u+n)) break;
                if(M.find(leader[u])==M.end()){
                    M[leader[u]]=1;
                    M[leader[u+n]]=0;
                }
            }
        }
        printf("Case %lld: ",t);
        if(i>0){
            printf("No\n");
        }
        else{
            printf("Yes\n");
            for(i=1;i<=n;i++){
                if(M[leader[i]]==1){
                    ans.push_back(i);
                }
            }
            printf("%lld",ans.size());
            for(i=0;i<ans.size();i++){
                printf(" %lld",ans[i]);
            }
            printf("\n");
        }
        for(i=0;i<=2*n;i++){
            G[i].clear();
            GR[i].clear();
        }
        M.clear();
        ans.clear();
        //memset(order,0,(2*n+1)*sizeof(ll));
        memset(finish,0,(2*n+1)*sizeof(ll));
        memset(leader,0,(2*n+1)*sizeof(ll));
    }
    return 0;
}

Read more »

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

By mahim007, history, 5 years ago, In English,

pls give me some critical test cases and help me to find out what is going wrong :( :( :( it is a simple 0-1 knapsack problem.

problem link=>uva 11003(Boxes)

my code=>codepad link

Read more »

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

By mahim007, history, 5 years ago, In English,

I tried a lots of I/O.and my program makes correct ans.but still WA.pls help me to find the bug.

problem link=>uva-10313 — Pay the Price

my code=>codepad

any critical I/O,suggestions,tips would be greatly appreciated.

Read more »

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

By mahim007, history, 5 years ago, In English,
 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

By mahim007, history, 5 years ago, In English,

very simple bigmod problem and the solution is simple also.but the SPOJ judge gives me WA :( problem link:NYSFNE — Short form of New Year

my code link:codepad

Read more »

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

By mahim007, history, 5 years ago, In English,

it seems to be ok,but giving wa,may be a small bug.but i can't find it.pls help me to find the bug.or suggest me if i misunderstand anything.

problem link->558B - Amr and The Large Array my submission->12243341

thanks in advance.

Read more »

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

By mahim007, history, 5 years ago, In English,

problem link:maximum sum from spoj [problem:http://www.spoj.com/problems/KGSS]

my code:

#include<bits/stdc++.h>
using namespace std;
#define mx 100009
#define ll long long int
ll arr[mx];
//ll tree[mx*4];
//ll state=0;
struct nd{
    ll high;
    ll sum;
};
nd tree[mx*4];
ll ans=-1;
ll res;
void init(ll node,ll l,ll r){
    if(l==r){
        tree[node].high=arr[l]; //cout<<"lf node:"<<node<<" val:"<<tree[node].high<<endl;
        tree[node].sum=arr[l];
        return;
    }
    ll Left=node*2;
    ll Right=node*2+1;
    ll mid=(l+r)/2;
    init(Left,l,mid);
    init(Right,mid+1,r);
    tree[node].high=max(tree[Left].high,tree[Right].high);
    ll hh=-1;
    hh=max(hh,tree[Left].high+tree[Right].high);
    hh=max(hh,tree[Left].sum);
    hh=max(hh,tree[Right].sum);
    tree[node].sum=hh; //cout<<"node:"<<node<<" val:"<<tree[node].sum<<" high:"<<tree[node].high<<endl;
}

ll query(ll node,ll l,ll r,ll i,ll j){
    if(l>j || r<i){
        return 0;
    }
    if(l>=i && r<=j){//cout<<"node:"<<node<<" val:"<<tree[node].sum<<endl;  cout<<"l:"<<l<<" r:"<<r<<endl;
        if(tree[node].sum>res){
            res=tree[node].sum;
        }
        return tree[node].high;
    }
    ll Left=node*2;
    ll Right=node*2+1;
    ll mid=(l+r)/2;
    ll p1=query(Left,l,mid,i,j);
    ll p2=query(Right,mid+1,r,i,j);
    if(p1+p2>res){ //cout<<p1<<"+"<<p2<<endl;
        res=p1+p2;
    }
    return max(p1,p2);
}

void update(ll node,ll l,ll r,ll pos,ll val){
    if(l>pos || r<pos){
        return;
    }
    if(l==r){
        tree[node].high=val;
        tree[node].sum=val;
        return;
    }
    ll Left=node*2;
    ll Right=node*2+1;
    ll mid=(l+r)/2;
    update(Left,l,mid,pos,val);
    update(Right,mid+1,r,pos,val);
    tree[node].high=max(tree[Left].high,tree[Right].high);
    tree[node].sum=max(tree[node].sum,tree[Left].high+tree[Right].high);
}

int main(){
    ll n,i,j;
    while(scanf("%lld",&n)==1){
        for(i=1;i<=n;i++){
            scanf("%lld",&arr[i]);
        }
        init(1,1,n);
        char ch;
        ll q;
        scanf("%lld",&q);
        getchar();
        for(i=1;i<=q;i++){
            scanf("%c",&ch);
            if(ch=='Q'){
                ll x,y; //cout<<"Q pressed"<<endl;
                scanf("%lld %lld",&x,&y);
                query(1,1,n,x,y);
                printf("%lld\n",res);
                res=-1;
                //state=0;
            }
            else{
                ll x,y;
                scanf("%lld %lld",&x,&y);
                update(1,1,n,x,y);
            }
            getchar();
        }
    }
    return 0;
}

Read more »

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

By mahim007, history, 5 years ago, In English,

pls give me critical input for which my code fails and suggest me anything :)

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
char s[1000009];
int main(){ //freopen("12467 output","w",stdout);
    ll t,T,i,j,n,ln;
    scanf("%lld",&T);
    getchar();
    for(t=1;t<=T;t++){
        gets(s);
        ln=strlen(s); //cout<<ln<<endl;
        string m,mx;
        for(i=0,j=ln-1;j>=0;j--){
            if(s[i]==s[j]){
                m+=s[i];
                i++; //cout<<m<<endl;
            }
            else{
                if(m.size()>mx.size()){
                    mx=m;
                }
                m.clear();
                i=0;
                if(s[i]==s[j]){
                    m+=s[i];
                    i++;
                }
            }
        }
        //if(m.size()==0 &&mx.size()==0){
        //    mx=s[0];
        //}
        //else if(m.size()*2==ln && mx.size()==0){
        //    mx=s;
        //}
        if(m.size()>mx.size()){
            mx=m;
        }
        reverse(mx.begin(),mx.end());
        cout<<mx<<endl;
    }
    return 0;
}

Read more »

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