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

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

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.

here is my code: 23522947 problem link: 750C - Новый год и рейтинг 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.

problem:link my submission:link

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

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

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.

problem link->MCOINS — Coins Game

my code-> codepad

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

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.

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

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