Category SPOJ

SPOJ – SHPATH – The Shortest Path

Arunima Mandal Leave a comment

Problem: https://www.spoj.com/problems/SHPATH/

Level: Easy

Code:



#include <bits/stdc++.h>

#define pii     pair<int,int>
#define MAX     10004
#define INF     INT_MAX

using namespace std;

int dijkstra(int src, int dst, vector<vector<pii> > &adj)
{
    vector<int> dis(MAX, INF);
    dis[src]=0;
    priority_queue<pii, vector<pii>, greater<pii> > pq;
    pq.push({0,src});
    while(!pq.empty())
    {
        int u=pq.top().second;
        int cost=pq.top().first;
        pq.pop();
        if(dis[u]<cost) continue;

        for(int i=0; i<adj[u].size(); i++)
        {
            int v=adj[u][i].first;
            cost=adj[u][i].second;
            if(dis[u]+cost<dis[v])
            {
                dis[v]=dis[u]+cost;
                pq.push({dis[v], v});
            }
        }
    }
    return dis[dst];
}

unordered_map<string,int> ump;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int node;
        cin>>node;
        int from=1;

        vector<vector<pii> > adj(MAX);
        for(int i=0; i<node; i++)
        {
            string s;
            cin>>s;
            ump[s]=from;
            int edge;
            cin>>edge;
            for(int j=0; j<edge; j++)
            {
                int to, cost;
                cin>>to>>cost;
                adj[from].push_back({to,cost});
                adj[to].push_back({from,cost});
            }
            from++;
        }
        int query;
        cin>>query;
        for(int i=0; i<query; i++)
        {
            string src,dst;
            cin>>src>>dst;
            cout<<dijkstra(ump[src],ump[dst],adj)<<endl;
        }
    }
    return 0;
}

SPOJ – EZDIJKST – Easy Dijkstra Problem

Arunima Mandal Leave a comment

Problem: https://www.spoj.com/problems/EZDIJKST/

Note: This is a pretty straightforward problem of basic Dijkstra implementation.

In case of the Wrong Answer:

  1. Notice that the input is a Directed graph, not an undirected graph. Take care of it while creating the adjacency matrix of the graph.
  2. Notice that while pushing in the priority queue, you should push the updated cost of the current node as the first element of the pair and then the node itself as the 2nd element of the pair.

In case of the Time Limit Exceeded:

The funny thing in my case is, I got the time limit exceeded because I declared the Dijkstra function as int but was not returning any integer at first, instead I was directly printing the output inside that function. I had no idea that this fault can result in a “time limit exceeded” verdict. As I didn’t notice that at first, I debugged the code for so much time, and lastly noticed that the return type of the function should be void as I was not returning anything there. That fix made my code Accepted in SPOJ! Later, I kept the function type as int and returned the result from there.

Code:

#include <bits/stdc++.h>

#define INF             INT_MAX
#define MAX             10004
#define pii             pair<int,int>

using namespace std;

int dijkstra(int src, int dst, vector<vector<pii>> &adj)
{
    vector<int> dis(MAX, INF);
    dis[src]=0;

    priority_queue<pii, vector<pii>, greater<pii> >pq;
    pq.push({0, src}); // Insert source in priority queue and initialize its distance as 0.

    while(!pq.empty())
    {
        int u=pq.top().second;
        int cost=pq.top().first;
        pq.pop();

        //Optimization in priority queue:
        //Since the pq can hold same node more than once with different costs,
        //no need to process the nodes which has already been updated to shorter distance
        if(dis[u]<cost) continue;

        for(int i=0; i<adj[u].size(); i++)
        {
            int v=adj[u][i].first;
            cost=adj[u][i].second;

            if(dis[v]>dis[u]+cost)
            {
                dis[v]=dis[u]+cost;
                pq.push({dis[v], v});
            }
        }
    }
    return dis[dst];
}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t;
    cin>>t;
    for(int z=0; z<t; z++)
    {
        int node,edge;
        cin>>node>>edge;

        vector<vector<pair<int,int> > > adj(MAX);

        for(int i=0; i<edge; i++)
        {
            int from,to,cost;
            cin>>from>>to>>cost;
            adj[from].push_back({to, cost});
            //adj[to].push_back({from, cost}); //If undirected graph
        }

        int src,dst;
        cin>>src>>dst;

        int min_distace=dijkstra(src, dst, adj);

        if(min_distace==INF) cout<<"NO"<<endl;
        else cout<<min_distace<<endl;
    }
    return 0;
}

SPOJ – VEXPROF – The angry professor

Arunima Mandal Leave a comment

Problem Link:
http://www.spoj.com/problems/VEXPROF/

Note:
This is an implementation problem. I found it in the “hashing” category of A2 Online judge and still now I can’t relate it with hashing. If anyone can, please let me know, I would be grateful.
I think this problem statement is not clear, it’s ambiguous and incomplete. It should be clearer because according to the problem statement there can be many different solutions with different answers.
Here “at least k” leads to the main confusion with no other specifications. So I have tried to solve it in a different way and got WA. The only logic with which I got AC, was the following-

The main trick is – when the same element at indices k*i (where i=1,2,3…..) with consecutive indices appear, only then we will take more than k students. Only by assuming this, I got AC. If the same I assumed whenever the consecutive indices with the same element are in other indices, then it should also consider the same, but the AC solution didn’t. I don’t know why.

I think the problem needed to specify the maximum/minimum answer in the problem statement as there can be many answers according to the present statement.

Solution: 

#include <bits/stdc++.h>

#define pf                  printf
#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 sffff(a,b,c,d)      scanf("%d %d %d %d",&a,&b,&c,&d)
#define sffffl(a,b,c,d)     scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
#define sfffff(a,b,c,d,e)   scanf("%d %d %d %d %d",&a,&b,&c,&d,&e)
#define sfffffl(a,b,c,d,e)  scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e)
#define sfc(a)              scanf("%c",&a)
#define ms(a,b)             memset(a,b,sizeof(a))
#define pb(a)               push_back(a)
#define db                  double
#define ll                  long long
#define ull                 unsigned long long
#define pii                 pair<int,int>
#define pll                 pair<long,long>
#define ff                  first
#define ss                  second
#define sz(x)               (int)x.size()
#define all(x)              x.begin(),x.end()
#define CIN                 ios_base::sync_with_stdio(0); cin.tie(0)
#define max3(a, b, c)       max(a, b) > max(b, c) ? max(a, b) : max(b, c)
#define min3(a, b, c)       min(a, b) < min(b, c) ? min(a, b) : min(b, c)
#define for0(i,n)           for(int i=0;i<n;i++)
#define for1(i,n)           for(int i=1;i<=n;i++)
#define forrev(i,n)         for(int i=n-1; i>=0; i--)
#define forab(i,a,b)        for(int i=a;i<=b;i++)
#define forba(i,b,a)        for(int i=b;i>=a;i--)
#define stlloop(x)          for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b)           __gcd(a, b)
#define lcm(a, b)           ((a)*((b)/gcd(a,b)))
#define case1(z)            cout<<"Case "<<z<<": "
#define case2(z)            printf("Case %d: ",z)
#define PI                  acos(-1) //3.14159265358979323846264338328
#define valid(tx,ty)        tx>=0 && tx<row && ty>=0 && ty<col
#define intlim              2147483648
#define MAX                 1000006
#define inf                 100000008

/*
ll power(int n,int p)
{
    ll ans=1;
    for1(i,p) ans*=n;
    return ans;
}

ll m=1000001;
ll bigmod(ll n,ll p)
{
    if(p==0) return 1;
    else if(p%2==0)
    {
        ll x=(bigmod(n,p/2))%m;
        return (x*x)%m;
    }
    else return ((n%m)*(bigmod(n,p-1)%m))%m;
}

*/

/*------------------------------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
/*---------------------------------------------------------------------*/

using namespace std;

ll a[100005];

int main()
{
    //CIN;
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t,n,k;
    sf(t);
    for1(z,t)
    {
        sff(n,k);
        for1(i,n) sf(a[i]);
        sort(a+1,(a+1)+n);
        int b=k,sum=0;
        for(int i=b;i<=n;i+=b)
        {
            for(int j=1,l=k-1;l>0;j++,l--) sum+=a[i]-a[i-j];
            /// The main trick is the following
            int c=1;
            while(c!=0)
            {
                if(a[i+1]==a[i]) i++;
                else c=0;
            }
        }
        pf("%d\n",sum);
    }

    return 0;
}

SPOJ – ACMCEG2B – FIGUREFUL

Arunima Mandal Leave a comment

Problem Link: http://www.spoj.com/problems/ACMCEG2B/

Solution:

#include <bits/stdc++.h>

#define pf                  printf
#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 sffff(a,b,c,d)      scanf("%d %d %d %d",&a,&b,&c,&d)
#define sffffl(a,b,c,d)     scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
#define sfffff(a,b,c,d,e)   scanf("%d %d %d %d %d",&a,&b,&c,&d,&e)
#define sfffffl(a,b,c,d,e)  scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e)
#define sfc(a)              scanf("%c",&a)
#define ms(a,b)             memset(a,b,sizeof(a))
#define pb(a)               push_back(a)
#define db                  double
#define ll                  long long
#define ull                 unsigned long long
#define pii                 pair<int,int>
#define pll                 pair<long,long>
#define ff                  first
#define ss                  second
#define sz(x)               (int)x.size()
#define all(x)              x.begin(),x.end()
#define CIN                 ios_base::sync_with_stdio(0); cin.tie(0)
#define max3(a, b, c)       max(a, b) > max(b, c) ? max(a, b) : max(b, c)
#define min3(a, b, c)       min(a, b) < min(b, c) ? min(a, b) : min(b, c)
#define for0(i,n)           for(int i=0;i<n;i++)
#define for1(i,n)           for(int i=1;i<=n;i++)
#define forrev(i,n)         for(int i=n-1; i>=0; i--)
#define forab(i,a,b)        for(int i=a;i<=b;i++)
#define forba(i,b,a)        for(int i=b;i>=a;i--)
#define stlloop(x)          for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b)           __gcd(a, b)
#define lcm(a, b)           ((a)*((b)/gcd(a,b)))
#define case1(z)            cout<<"Case "<<z<<": "
#define case2(z)            printf("Case %d: ",z)
#define PI                  acos(-1) //3.14159265358979323846264338328
#define valid(tx,ty)        tx>=0 && tx<row && ty>=0 && ty<col
#define intlim              2147483648
#define MAX                 1000006
#define inf                 100000008

ll power(int n,int p)
{
    ll ans=1;
    for1(i,p) ans*=n;
    return ans;
}

ll m=1000001;
ll bigmod(ll n,ll p)
{
    if(p==0) return 1;
    else if(p%2==0)
    {
        ll x=(bigmod(n,p/2))%m;
        return (x*x)%m;
    }
    else return ((n%m)*(bigmod(n,p-1)%m))%m;
}


/*------------------------------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
/*---------------------------------------------------------------------*/

using namespace std;

map<pii,string> mp;

int main()
{
    //CIN;
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n,t,x,y;
    string s;
    sf(n);
    for0(i,n)
    {
        sff(x,y);
        cin>>s;
        pii z=make_pair(x,y);
        mp[z]=s;
    }
    sf(t);
    for1(z,t)
    {
        sff(x,y);
        pii w=make_pair(x,y);
        cout<<mp[w]<<endl;
    }

    return 0;
}

SPOJ – YODANESS – Yodaness Level

Arunima Mandal Leave a comment

Problem link: SPOJ – YODANESS – Yodaness Level

Solution :  This problem is of relatively easy logic as a BIT problem. About like the logic of the problem SPOJ – Inversion Count. But do not compare with that. Because the logic is not same but the concept is about similar. So you have to catch the concept by yourself in pen n paper, you will get your simple logic 🙂

#include <bits/stdc++.h>

#define pf                  printf
#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 sffff(a,b,c,d)      scanf("%d %d %d %d",&a,&b,&c,&d)
#define sffffl(a,b,c,d)     scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
#define sfffff(a,b,c,d,e)   scanf("%d %d %d %d %d",&a,&b,&c,&d,&e)
#define sfffffl(a,b,c,d,e)  scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e)
#define sfc(a)              scanf("%c",&a)
#define ms(a,b)             memset(a,b,sizeof(a))
#define pb(a)               push_back(a)
#define db                  double
#define ll                  long long
#define ull                 unsigned long long
#define pii                 pair<int,int>
#define ff                  first
#define ss                  second
#define sz(x)               (int)x.size()
#define all(x)              x.begin(),x.end()
#define CIN                 ios_base::sync_with_stdio(0); cin.tie(0)
#define max3(a, b, c)       max(a, b) > max(b, c) ? max(a, b) : max(b, c)
#define min3(a, b, c)       min(a, b) < min(b, c) ? min(a, b) : min(b, c)
#define for0(i,n)           for(int i=0;i<n;i++)
#define for1(i,n)           for(int i=1;i<=n;i++)
#define forrev(i,n)         for(int i=n-1; i>=0; i--)
#define forab(i,a,b)        for(int i=a;i<=b;i++)
#define forba(i,b,a)        for(int i=b;i>=a;i--)
#define stlloop(x)          for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b)           __gcd(a, b)
#define lcm(a, b)           ((a)*((b)/gcd(a,b)))
#define case1(z)            cout<<"Case "<<z<<": "
#define case2(z)            printf("Case %d: ",z)
#define PI                  acos(-1) //3.14159265358979323846264338328
#define valid(tx,ty)        tx>=0 && tx<row && ty>=0 && ty<col
#define intlim              2147483648
#define MAX                 100005
#define inf                 100000008

ll power(int n,int p)
{
    ll ans=1;
    for1(i,p) ans*=n;
    return ans;
}

ll m=1000001;
ll bigmod(ll n,ll p)
{
    if(p==0) return 1;
    else if(p%2==0)
    {
        ll x=(bigmod(n,p/2))%m;
        return (x*x)%m;
    }
    else return ((n%m)*(bigmod(n,p-1)%m))%m;
}


/*------------------------------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
/*---------------------------------------------------------------------*/

using namespace std;

ll tree[30004],input[30004];
map<string,int> mp;
vector<string> v;

ll query(ll idx)
{
    ll sum=0;
    while(idx>0)
    {
        sum+=tree[idx];
        idx-= idx & (-idx);
    }
    return sum;
}

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

int main()
{
    CIN;
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    int t;
    cin>>t;
    for1(z,t)
    {
        int n,c=0;
        cin>>n;
        string s,ss,str;
        for1(i,n)
        {
            cin>>s;
            v.pb(s);
        }
        for1(i,n)
        {
            cin>>s;
            c++;
            mp[s]=c;
        }
        for0(i,sz(v)) {input[i+1]=mp[v[i]];}
        ll ans=0;
        for1(i,n)
        {
            update(input[i],1,n);
            ll x=query(input[i]-1);
            ans+=(input[i]-x-1);
        }
        cout<<ans<<endl;
        mp.clear();
        v.clear();
        ms(tree,0);
    }

    return 0;
}