Sunday 18 June 2017

Almost Shortest Path (UVa 12144, UVaLive 4210, Regionals 2008 >> Latin America - South America) 


  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva ), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

#include<bits/stdc++.h>
using namespace std;

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 502

struct Z
{
    int v, cost;
    bool operator < (const Z &p) const
    {
        return p.cost<cost;
    }
};

Z z, z2;

int shortest[MX], forbidden[MX][MX];
vector<Z> adj[MX];
vector<int> parent[MX];
priority_queue<Z>pq;

int dijkstra(int src, int dst, int node)
{
    for(int i=0; i<node; i++)
        shortest[i]=1e9;

    z.v = src;
    z.cost = 0;
    pq.push(z);
    shortest[src]=0;

    while(!pq.empty())
    {
        z = pq.top();
        pq.pop();

        int l = adj[z.v].size();

        for(int i=0; i<l; i++)
        {
            z2 = adj[z.v][i];
            if(forbidden[z.v][z2.v]==1) continue;
            if(shortest[z2.v]>shortest[z.v]+z2.cost)
            {
                parent[z2.v].clear();
                parent[z2.v].push_back(z.v);
                z2.cost = shortest[z2.v]= shortest[z.v]+z2.cost;
                pq.push(z2);
            }
            else if(shortest[z2.v]==shortest[z.v]+z2.cost)
                parent[z2.v].push_back(z.v);

        }
    }
    return shortest[dst];
}

void removeEdge(int src, int dst)
{
    if(dst==src) return;
    for(int i=0;i<parent[dst].size();i++)
    {
        forbidden[ parent[dst][i] ][dst] = 1;
        removeEdge(src, parent[dst][i]);
    }
return;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int tc,kk=1, node, edge, u, v, cost, src, dst;

    while(cin>>node>>edge && node)
    {
        cin>>src>>dst;


        for(int i=0; i<edge; i++)
        {
            cin>>u>>v>>cost;

            z.v = v;
            z.cost = cost;
            adj[u].push_back(z);
        }

        int tmp = 1e9;
        int mn = dijkstra(src, dst, node); //initial

        if(mn<1e9)
        {
            removeEdge(src, dst); //remove edges of shortest
            tmp = dijkstra(src, dst, node); //second time
        }
        if(tmp==1e9) tmp = -1;
        cout<<tmp<<endl;


        CLR(forbidden);
        for(int i=0;i<node;i++)
        {
            adj[i].clear();
            parent[i].clear();
        }
    }
    return 0;
}
at 2 comments:
Labels: , ,

Thursday 8 June 2017

Reverse Integer (LeetCode) 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int reverse(int x) {
        
        bool flag = false;
        if(x<0)
        {
            flag = true;
            x*=-1;
        }
        int rev = 0;
        while(x)
        {
            if((rev*10)/10 != rev) return 0; // checking overflow
            rev = rev*10 + x%10;
            x/=10;
        }
        
        if(flag) rev*=-1;
        
        return rev;
    }
};
at No comments:
Labels:

Median of Two Sorted Arrays (LeetCode) 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int l1 = nums1.size();
        int l2 = nums2.size();
        if(l1>l2)
            return findMedianSortedArrays(nums2, nums1);
        int k = (l1+l2-1)>>1;
        int lft = 0, rgt = l1;
        while(lft<rgt)
        {
            int md = (lft+rgt)>>1;
            if(nums1[md]<nums2[k-md])
                lft = md+1;
            else rgt = md;
        }
        double x, y;
        
        if(lft>0 && (k-lft)>=0) 
            x = max(nums1[lft-1], nums2[k-lft]);
        else if(lft>0)
            x = nums1[lft-1];
        else if(k-lft>=0)
            x = nums2[k-lft];
            
        if((l1+l2) & 1) return x; //total odd size, single median
        
        if(lft<l1 && (k-lft+1)<l2)
            y = min(nums1[lft], nums2[k-lft+1]);
        else if(lft<l1)
            y = nums1[lft];
        else if((k-lft+1)<l2)
            y = nums2[k-lft+1];
        return (x+y)/2.0;
        
    }      
    
};
at No comments:
Labels:

Sunday 4 June 2017

Football (UVa 12673, UVaLive 6530, Regionals 2013 >> Latin America) 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva ), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

#include<bits/stdc++.h>
using namespace std;

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

struct match{
    int score, receive;
    bool operator < (const match &m) const{
        return m.score-m.receive < score-receive ;
    }
};

match mth[MX];

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tc,kk=1, n, g;
    //cin>>tc;
    while(cin>>n>>g)
    {
        for(int i=0;i<n;i++)
            cin>>mth[i].score>>mth[i].receive;
        sort(mth, mth+n);

        int point = 0;

        for(int i=0;i<n;i++)
        {
            //cout<<mth[i].score<<" "<<mth[i].receive<<endl;
            if(mth[i].score>mth[i].receive)
                point += 3;
            else if(mth[i].score==mth[i].receive)
            {
                if(g>0)
                {
                    point += 3;
                    g--;
                }
                else point += 1;
            }
            else if(mth[i].score<mth[i].receive)
            {
                if(g>(mth[i].receive-mth[i].score))
                {
                    point += 3;
                    g= g-(mth[i].receive-mth[i].score)-1;
                }
                else if(g==(mth[i].receive-mth[i].score))
                {
                    point += 1;
                    g= g-(mth[i].receive-mth[i].score);
                }
                
            }
        }
        cout<<point<<endl;
    }
    return 0;
}
at No comments:
Labels: , ,

Saturday 3 June 2017

Proving Equivalences (UVa 12167, UVaLive 4287, Regionals 2008 >> Europe - Northwestern) 


  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

#include<bits/stdc++.h>
using namespace std;

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

vector<int>adj[20002];
stack<int>stk;

int t, lo[20002], tim[20002], vis[20002], sccrm[20002], scc, done;

void tarjan_scc(int u)
{
    t++;
    vis[u]=1;
    lo[u]=tim[u]=t;
    stk.push(u);

    for(int i=0;i<adj[u].size();i++)
    {
        int v = adj[u][i];
        if(!vis[v])
        {
            tarjan_scc(v);
            lo[u]=min(lo[u], lo[v]);
        }
        else if(vis[v]==1)
            lo[u]=min(lo[u], tim[v]);
    }

    if(lo[u]==tim[u])
    {
        scc++;
        do{
            done = stk.top();
            stk.pop();
            sccrm[done]=scc;
            vis[done]=2;
        }while(done!=u);
    }
return;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int kk=1, tc, n, m, u, v;
    string s;
    cin>>tc;
    while(tc--)
    {
        cin>>n>>m;
        t=scc=0;
        while(!stk.empty()) stk.pop();
        for(int i=1;i<=n;i++)
        {
            adj[i].clear();
            vis[i]=0;
        }

        while(m--)
        {
            cin>>u>>v;
            adj[u].push_back(v);
        }
        for(int i=1;i<=n;i++)
            if(!vis[i])
                tarjan_scc(i);

        // checking zero indegree and outdegree of scc
        bool hasIndegree[scc+2], hasOutdegree[scc+2];
        CLR(hasIndegree);
        CLR(hasOutdegree);

        for(int i=1;i<=n;i++)
            for(int j=0;j<adj[i].size();j++)
                if(sccrm[i]!=sccrm[adj[i][j]]) //not in same scc
                {
                    hasIndegree[sccrm[i]]=true;
                    hasOutdegree[sccrm[adj[i][j]]]=true;
                }
        int zeroIndgree=0, zeroOutdegree=0;
        for(int i=1;i<=scc;i++)
        {
            if(!hasIndegree[i]) zeroIndgree++;
            if(!hasOutdegree[i]) zeroOutdegree++;
        }
        if(scc==1) cout<<0<<endl;
        else cout<<max(zeroIndgree, zeroOutdegree)<<endl;
        //cout<<"Case "<<kk++<<": "<< <<"\n";
    }

    return 0;
}
at No comments:
Labels: , ,

Thursday 1 June 2017

Interval Product (UVa 12532, UVaLive 6139, Regionals 2012 >> Latin America) 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva ), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

#include<bits/stdc++.h>
using namespace std;

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

int z1, z2, node[MX*4];

void insert(int idx, int st, int ed, int s, int e, int val)
{
    if(st==s && ed==e)
    {
        if(val>0) node[idx]=1;
        else if(val<0) node[idx]=-1;
        else node[idx]=0;
        return;
    }
    int mid=(st+ed)>>1, lft=idx<<1, rgt=lft|1;
    if(e<=mid) insert(lft, st, mid, s, e, val);
    else if(s>mid) insert(rgt, mid+1, ed, s, e, val);
    else
    {
        insert(lft, st, mid, s, mid, val);
        insert(rgt, mid+1, ed, mid+1, e, val);
    }
    node[idx] = node[lft] * node[rgt];
    return;
}

int query(int idx, int st, int ed, int s, int e)
{
    if(st==s && ed==e)
    {
        return node[idx];
    }
    int mid=(st+ed)>>1, lft=idx<<1, rgt=lft|1;
    if(e<=mid) return query(lft, st, mid, s, e);
    else if(s>mid) return query(rgt, mid+1, ed, s, e);
    else return query(lft, st, mid, s, mid)*query(rgt, mid+1, ed, mid+1, e);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int tc,kk=1, n, q, x, y;
    char c;
    string s;
    while(cin>>n>>q)
    {
        for(int i=1;i<=n*4;i++)
            node[i]=1;

        for(int i=1; i<=n; i++)
        {
            cin>>x;
            insert(1, 1, n, i, i, x);
        }
        while(q--)
        {
            cin>>c>>x>>y;
            if(c=='C')
                insert(1, 1, n, x, x, y);
            else
            {
                z1 = query(1, 1, n, x, y);
                //cout<<z1.pos<<" "<<z1.neg<<" "<<z1.zero<<endl;
                if(z1==0)
                    cout<<"0";
                else if(z1<0)
                    cout<<"-";
                else cout<<"+";
            }
        }
        cout<<endl;
    }
    return 0;
}
at No comments:
Labels: , ,
Subscribe to: Posts (Atom)