Codeforces: 61 E. Enemy is weak

2

Problem Link : http://codeforces.com/contest/61/problem/E

Solution Idea:

    In this problem we need to count the number of triple inverse triplets on a given array. A triple inverse triplet is three positions i, j, k on an array A=[] such that i < j  Aj > Ak.

    Now to solve this problem we need some range update and query data structure like segment tree or binary indexed tree. The idea is at first compress the array by mapping the numbers from range 1 to 10^6. After that read the array from reverse order and query the value of that mapped index on segment tree(let this mapped index is id)and store it on an array let name this array ara2=[]. After that increment the value of the index id+1 to n. It means that when we read any number from id+1 to n we can know that current number id have impact on this number. Here id is the k_th element of the triplet and all the number from id+1 to n is the j_th element of the triplet. Now each ara2[] index hold the number of inverse pair starting at id.

    Now read the array element from the reverse order again and do the same thing. This time we need another segment tree. This time when we stand on position id add the value of the segment tree of position id to the answer and update all position in the range id+1 to n by ara2[index_of_id]. Do this for the whole array.

    We can repeat this technique for 4,5,6 element inversion too.



#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

#define mx 1000006

ll tree[2][mx];
ll ara[mx],ara2[mx];

void update(int id, int idx, ll val)
{
    for(; idx<mx && idx; idx+=idx&-idx)
        tree[id][idx]+=val;
}

ll query(int id, int idx)
{
    ll ret=0;
    for(; idx; idx-=idx&-idx)
        ret+=tree[id][idx];
    return ret;
}

vector<ll>v;

int main()
{

//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);

    int n;
    sf(n);
    v.pb(0);
    loop1(i,n)
    {
        sfl(ara[i]);
        v.pb(ara[i]);
    }
    sort(all(v));

    ll ans=0;

    for(int i=n; i>0; i--)
    {
        int id=lower_bound(all(v),ara[i])-v.begin();
        ara2[i]=query(0,id);
        update(0,id+1,1);
//        update(0,id-1,-1);
    }

    for(int i=n; i>0; i--)
    {
        int id=lower_bound(all(v),ara[i])-v.begin();
        ans+=query(1,id);
        update(1,id+1,ara2[i]);
//        update(1,id-1,-ara2[i]);
    }

    printf("%lld\n",ans);

    return 0;
}

Advertisements

Codeforces: 877E. Danil and a Part-time Job

Problem Link : http://codeforces.com/contest/877/problem/E

Solution Idea:

    Run a dfs on the given for getting the Euler tour order or inorder traversal order. Then the tree is converted to a liner 1D array. Now we can apply range query and update on this array.

    Now use a range update query data structure. Here I have used segment tree. Now initialize the tree with the initial value and now our job is to just toggle a subtree of the given tree and perform query operation. Use a propagation for the update and answer the query.



#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

#define mx 200005
#define segment_tree int l=n*2,r=l+1,mid=(b+e)/2
pii info[mx];
vector<int>g[mx];
int cnt=0;
int maps[mx],ara[mx];

void dfs(int u, int par)
{
    info[u].ff=++cnt;
    maps[cnt]=u;
    for(int i=0;i<SZ(g[u]);i++)
    {
        int v=g[u][i];
        if(v==par) continue;
        dfs(v,u);
    }
    info[u].ss=cnt;
}

struct data
{
    int val, prop;
};

data tree[3*mx];

void push_down(int n, int b, int e)
{
    if(tree[n].prop%2)
    {
        segment_tree;
        tree[l].val=(mid-b+1)-tree[l].val;
        tree[l].prop++;
        tree[r].val=(e-mid)-tree[r].val;
        tree[r].prop++;
        tree[n].prop=0;
    }
}

void init(int n, int b, int e)
{
    if(b==e)
    {
        tree[n].val=ara[maps[b]];
        tree[n].prop=0;
        return;
    }
    segment_tree;
    init(l,b,mid);
    init(r,mid+1,e);
    tree[n].val=tree[l].val+tree[r].val;
}

void update(int n, int b, int e, int i, int j)
{
    if(b>j || e<i) return;
    if(b>=i && e<=j)
    {
        tree[n].val=(e-b+1)-tree[n].val;
        tree[n].prop++;
        return;
    }
    push_down(n,b,e);
    segment_tree;
    update(l,b,mid,i,j);
    update(r,mid+1,e,i,j);
    tree[n].val=tree[l].val+tree[r].val;
}

int query(int n, int b, int e, int i, int j)
{
    if(b>j || e<i) return 0;
    if(b>=i && e<=j) return tree[n].val;
    push_down(n,b,e);
    segment_tree;
    int p=query(l,b,mid,i,j);
    int q=query(r,mid+1,e,i,j);
    return p+q;
}

char str[10];

int main()
{

//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);

    int n;
    sf(n);
    for(int i=2;i<=n;i++)
    {
        int a;
        sf(a);
        g[a].pb(i);
    }

    for(int i=1;i<=n;i++) sf(ara[i]);
    dfs(1,1);
    init(1,1,n);
    int q;
    sf(q);
    while(q--)
    {
        int a;
        scanf(" %s %d",str,&a);
        if(str[0]=='g')
        {
            int x=query(1,1,n,info[a].ff,info[a].ss);
            printf("%d\n",x);
        }
        else
        {
            update(1,1,n,info[a].ff,info[a].ss);
        }
    }



    return 0;
}

Codeforces : 495C Treasure

This one is one of my favorite. 🙂


/*
User ID: Tanmoy_Datta
Link : http://codeforces.com/contest/495/problem/C
*/

#include <bits/stdc++.h>

#define pii pair <int,int>
#define sc scanf
#define pf printf
#define Pi 2*acos(0.0)
#define ms(a,b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define MP make_pair
#define oo 1<<29
#define dd double
#define ll long long
#define EPS 10E-10
#define ff first
#define ss second
#define MAX 10000
#define SZ(a) (int)a.size()
#define getint(a) scanf("%d",&a)
#define loop(i,n) for(int i=0;i<n;i++)
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define inf 1000000
#define rtintlim 46340
#define llim 9223372036854775808
#define rtllim 3037000499
#define ull unsigned long long
#define I int

using namespace std;

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int c,d,a,b;
    c=d=a=b=0;
    string str;
    cin>>str;
    int len=SZ(str);
    for(int i=0; i<len; i++)
    {
        if(str[i]=='(')
        {
            a++;
            c++;
        }
        if(str[i]==')')
        {
            b++;
            if(c!=0)
                c--;
        }
        if(str[i]=='#')
        {
            d++;
            c=0;
        }
        if(b+d>a)
        {
            cout<<-1<<endl;
            return 0;
        }
    }

    if(c>0)
    {
        cout<<-1<<endl;
        return 0;
    }

    for(int i=1; i<d; i++)
    {
        cout<<1<<endl;
        b++;
    }
    cout<<a-b<<endl;
    return 0;
}

Codeforces: 508C Anya and Ghosts


/*
User ID: Tanmoy_Datta
Link : http://codeforces.com/problemset/problem/508/C
*/

#include <bits/stdc++.h>

#define pii pair <int,int>
#define sc scanf
#define pf printf
#define Pi 2*acos(0.0)
#define ms(a,b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define MP make_pair
#define oo 1<<29
#define dd double
#define ll long long
#define EPS 10E-10
#define ff first
#define ss second
#define MAX 120
#define SZ(a) (int)a.size()
#define getint(a) scanf("%d",&a)
#define loop(i,n) for(int i=0;i<n;i++)
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define inf 100000
#define rtintlim 46340
#define llim 9223372036854775808
#define rtllim 3037000499
#define ull unsigned long long
#define I int

using namespace std;
ll ara[350];
int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    ms(ara,-1000000);
    int m,t,r;
    cin>>m>>t>>r;
    vector<int>v;
    int num;
    for(int i=0; i<m; i++)
    {
        cin>>num;
        v.pb(num);
    }
    if(t<r)
        cout<<-1<<endl;
    else
    {
        int ans=0;
        //reverse(all(v));
        for(int i=0; i<m; i++)
        {
            int c=0;
            for(int j=1; j<=r; j++)
            {
                if(ara[j]+t>=v[i])
                    c++;
            }
            if(c==r)
                continue;
            else
            {
                //ans+=c;
                c=0;
                for(int j=1; j<=r; j++)
                {
                    if(ara[j]+t<v[i])
                    {
                        ara[j]=v[i]-(++c);
                        ans++;
                    }
                }

            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

Codeforces 508B Anton and currency you all know


/*
User ID: Tanmoy_Datta
Link : http://codeforces.com/problemset/problem/508/B
*/

#include <bits/stdc++.h>

#define pii pair <int,int>
#define sc scanf
#define pf printf
#define Pi 2*acos(0.0)
#define ms(a,b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define MP make_pair
#define oo 1<<29
#define dd double
#define ll long long
#define EPS 10E-10
#define ff first
#define ss second
#define MAX 120
#define SZ(a) (int)a.size()
#define getint(a) scanf("%d",&a)
#define loop(i,n) for(int i=0;i<n;i++)
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define inf 100000
#define rtintlim 46340
#define llim 9223372036854775808
#define rtllim 3037000499
#define ull unsigned long long
#define I int

using namespace std;

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    string str;
    cin>>str;
    int lenth=SZ(str);
    int last=str[lenth-1]-'0';
    int a=0;
    int pos=-1,val=-1,dif=1000;
    for(int i=0; i<lenth-1; i++)
    {
        int d=(str[i]-'0');
        if(d%2==0)
        {
            if(last>d)
            {
                char c=str[i];
                str[i]=str[lenth-1];
                str[lenth-1]=c;
                a=1;
                break;
            }
            else
                pos=i;
        }
    }
    if(a)
        cout<<str<<endl;
    else
    {
        if(pos!=-1)
        {
            char c=str[pos];
            str[pos]=str[lenth-1];
            str[lenth-1]=c;
            cout<<str<<endl;
        }
        else
            cout<<-1<<endl;
    }
    return 0;
}

Codeforces 508A Pasha and Pixels


/*
User ID: Tanmoy_Datta
Link : http://codeforces.com/contest/508/problem/A
*/

#include <bits/stdc++.h>

#define pii pair <int,int>
#define sc scanf
#define pf printf
#define Pi 2*acos(0.0)
#define ms(a,b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define MP make_pair
#define oo 1<<29
#define dd double
#define ll long long
#define EPS 10E-10
#define ff first
#define ss second
#define MAX 120
#define SZ(a) (int)a.size()
#define getint(a) scanf("%d",&a)
#define loop(i,n) for(int i=0;i<n;i++)
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define inf 100000
#define rtintlim 46340
#define llim 9223372036854775808
#define rtllim 3037000499
#define ull unsigned long long
#define I int

using namespace std;
bool ara[1010][1010];
bool test=0,test2=0;
int ans=0;
int dirx1[]= {0,0,-1,-1};
int diry1[]= {0,-1,0,-1};

int dirx2[]= {0,0,-1,-1};
int diry2[]= {0,1,0,1};

int dirx3[]= {0,0,1,1};
int diry3[]= {0,1,0,1};

int dirx4[]= {0,0,1,1};
int diry4[]= {0,-1,0,-1};

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    ll n,m,k;

    ms(ara,0);
    cin>>n>>m>>k;
    for(int i=1; i<=k; i++)
    {
        int a,b;
        cin>>a>>b;
        ara[a][b]=true;
        if(i>=4 && !test2)
        {
            int cnt=0;
            {
                for(int j=0; j<4; j++)
                {
                    int c=a+dirx1[j];
                    int d=b+diry1[j];
                    if(c>0 && c<=n && d>0 && d<=m)
                    {
                        if(ara[c][d])
                            cnt++;
                    }
                }
                if(cnt!=4)
                {
                    cnt=0;
                    for(int j=0; j<4; j++)
                    {
                        int c=a+dirx2[j];
                        int d=b+diry2[j];
                        if(c>0 && c<=n && d>0 && d<=m)
                        {
                            if(ara[c][d])
                                cnt++;
                        }
                    }
                }

                if(cnt!=4)
                {
                    cnt=0;
                    for(int j=0; j<4; j++)
                    {
                        int c=a+dirx3[j];
                        int d=b+diry3[j];
                        if(c>0 && c<=n && d>0 && d<=m)
                        {
                            if(ara[c][d])
                                cnt++;
                        }
                    }
                }

                if(cnt!=4)
                {
                    cnt=0;
                    for(int j=0; j<4; j++)
                    {
                        int c=a+dirx4[j];
                        int d=b+diry4[j];
                        if(c>0 && c<=n && d>0 && d<=m)
                        {
                            if(ara[c][d])
                                cnt++;
                        }
                    }
                }
            }
            if(cnt>=4 && !test2)
            {
                test=1;
                ans=i;
                test2=1;
            }
        }
    }
    if(test)
    {
        cout<<ans<<endl;
        return 0;
    }
    cout<<0<<endl;
    return 0;
}

Codeforces 495B – Modular Equations

This is a very interesting divisor count problem.


/*
User ID: Tanmoy_Datta
Link : http://codeforces.com/problemset/problem/495/B
*/

#include <bits/stdc++.h>

#define pii pair <int,int>
#define sc scanf
#define pf printf
#define Pi 2*acos(0.0)
#define ms(a,b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define MP make_pair
#define oo 1<<29
#define dd double
#define ll long long
#define EPS 10E-10
#define ff first
#define ss second
#define MAX 10000
#define SZ(a) (int)a.size()
#define getint(a) scanf("%d",&a)
#define loop(i,n) for(int i=0;i<n;i++)
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define inf 1000000
#define rtintlim 46340
#define llim 9223372036854775808
#define rtllim 3037000499
#define ull unsigned long long
#define I int

using namespace std;

/* Bits operation */
int Set(int n,int pos)  { return n = n | 1<<pos;}
bool check(int n,int pos) { return n & 1<<pos;}
int Reset(int n, int pos) { return n=n & ~(1<<pos);}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    ll a,b;
    cin>>a>>b;
    if(a==b)
        cout<<"infinity"<<endl;
    else
    {
        a-=b;
        int ans=0;
        for(int i=1;i*i<=a;i++)
        {
            if(a%i==0)
            {
                if(i>b)
                    ans++;
                if(a/i!=i && (a/i)>b)
                    ans++;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}