Ankur's Blog

let's start Code

Showing posts with label UVA. Show all posts
Showing posts with label UVA. Show all posts

Lyndon factorization

, , , No comments

Resources:

CP_Algorithms 

visualize 

wikipedia 

Problem link: 719 - Glass Beads 

Solution:

 

Share:
Read More

10104 - Euclid Problem

, , , No comments
Share:
Read More

11029 - Leading and Trailing

, , No comments
Share:
Read More

1230 - MODEX

, , No comments
Share:
Read More

1121 - Subsequence

, , No comments
1121 - Subsequence

Topic: two pointer

explanation: Shakil Ahmed's Blog

solution 01:

 

Share:
Read More

793 - Network Connections

, , No comments

793 - Network Connections

Topic : DSU

Solution 01:


 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
#include <bits/stdc++.h>
using namespace std;

#define INF 1<<30
#define MAX 10005
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

int parent[MAX];

void Initialization(int n)
{
  for(int i = 0; i <= n; i++)
    parent[i] = i;
}

int find_parent(int x)
{
  if(parent[x] == x)
    {
        return x;
    }
  return parent[x] = find_parent(parent[x]);
}

void make_union(int x, int  y)
{
  parent[find_parent(x)] = find_parent(y);
  //parent[find_parent(y)] = find_parent(x);
}

bool isUnion(int x, int y)
{
  return find_parent(x) == find_parent(y);
}

int main()
{
    //FASTIO
    ///*
    //double start_time = clock();
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
   #endif
    //*/

    int t;
    cin >> t;
    bool space = false;
    for(int cs = 0; cs < t; cs++, space = true){
      Initialization(MAX);
      if(space)cout << endl;
        int N;
        cin >> N;
        getchar();
        int yes = 0, no = 0;
           string str;
            int x,y;
        while(getline(cin, str)){
          if(str == "")break;
          char ch;
          stringstream S(str);
         // S >> ch;
          S >> ch >>x >> y;
            if(ch == 'c'){
                make_union(x,y);
            }
            else{
                //cerr << parent[x] << " "<<parent[y]<<endl;
                if(isUnion(x,y))yes++;
                else no++;
            }
        }
        cout << yes << ","<<no<<endl;
    }


      //double end_time = clock();
    //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
   return 0;
}

Share:
Read More

11503 - Virtual Friends

, , , No comments

11503 - Virtual Friends

Topic: DSU

solution 01:


 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
#include <bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define MAX 100005
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

int parent[MAX*2], Rank[MAX];

void Initialization()
{
  for(int i = 0; i <= MAX; i++)
    parent[i] = i, Rank[i] = 1;
}

int find_parent(int x)
{
  if(parent[x] == x)
    {
        return x;
    }
  return parent[x] = find_parent(parent[x]);
}

void make_union(int x, int  y)
{
    int p = find_parent(x);
    int q = find_parent(y);
    if(p != q){
        if(Rank[p] < Rank[q])
            swap(p,q);
        parent[q] = p;
        Rank[p] += Rank[q];
    }
}

bool isUnion(int x, int y)
{
  return find_parent(x) == find_parent(y);
}

int main()
{
    //FASTIO
    /*
    //double start_time = clock();
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
   #endif
    //*/

    int t;
    cin >> t;
    while(t--){
        Initialization();
        int F;
        cin >> F;
        int cnt = 1;
        map<string, int> mp;
        map<int, int>res;
        map<int,int>visit,ans;
        for(int i = 1; i <= F; i++){
            string s1,s2;
            cin >> s1 >> s2;
            if(mp[s1] == 0)mp[s1] = cnt++;
            if(mp[s2] == 0)mp[s2] = cnt++;
            int x = mp[s1];
            int y = mp[s2];
            make_union(x,y);
            cout << Rank[find_parent(x)]<<endl;
            //cerr << Rank[find_parent(x)] << " " <<Rank[find_parent(y)]<<endl;
        }
    }

      //double end_time = clock();
    //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
   return 0;
}

Share:
Read More

10685 - Nature

, , No comments

10685 - Nature

Topic: ডিসজয়েন্ট সেট

Solution 01:


 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
#include <bits/stdc++.h>
using namespace std;

#define INF 1<<30
#define MAX 10005
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

int parent[5005];

void Initialization(int n)
{
  for(int i = 0; i <= n; i++)
    parent[i] = i;
}

int find_parent(int x)
{
  if(parent[x] == x)
    {
        return x;
    }
  return parent[x] = find_parent(parent[x]);
}

void make_union(int x, int  y)
{
  parent[find_parent(x)] = find_parent(y);
  //parent[find_parent(y)] = find_parent(x);
}

bool isUnion(int x, int y)
{
  return find_parent(x) == find_parent(y);
}

int main()
{
    //FASTIO
    /*
    //double start_time = clock();
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
   #endif
    //*/

    int c,r;
    while(1){
        cin >> c >> r;
        if(c == 0 && r == 0)break;
        map<string, int> mp;
        for(int i = 1; i <= c; i++){
            string s;
            cin >> s;
            mp[s] = i;
        }
        Initialization(c);
        for(int i = 1; i <= r; i++){
            string str1, str2;
            cin >> str1 >> str2;
            int x = mp[str1];
            int y = mp[str2];
                make_union(y,x);
        }
        int mx = 0;
        map<int,int>ans;
        for(int i = 1; i <= c; i++){
            int k = find_parent(i);
            //cerr << i << "---->"<<k<< endl;
            ans[k]++;
            mx = max(mx,ans[k]);
        }
        cout << mx << endl;
    }

      //double end_time = clock();
    //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
   return 0;
}

Share:
Read More

459 - Graph Connectivity

, , , No comments

459 - Graph Connectivity

Topic: Union Find Algorithm

ডাটা স্ট্রাকচার: ডিসজয়েন্ট সেট(ইউনিয়ন ফাইন্ড)

Solution 01:



 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
#include <bits/stdc++.h>
using namespace std;

#define INF 1<<30
#define MAX 10005
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

int parent[100];

void Initialization(int n)
{
  for(int i = 0; i <= n; i++)
    parent[i] = i;
}

int find_parent(int x)
{
  if(parent[x] == x)return x;
  return parent[x] = find_parent(parent[x]);
}

void make_union(int x, int  y)
{
  parent[find_parent(x)] = find_parent(y);
}

bool isUnion(int x, int y)
{
  return find_parent(x) == find_parent(y);
}

int main()
{
 // FASTIO
   /*
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
   #endif
    //*/
     int t,i , cs;
    bool space = false;
    scanf("%d",&t);
    getchar();
    for ( cs = 1 ; cs <= t ; cs++ , space = 1)
    {    if(space) printf("\n");
         char lim;
         string str;
        cin>>lim;
        getchar();
        Initialization(lim-'A');
        int ans = lim-'A' + 1;
        while(getline(cin,str) && str!="")
        {
           // cerr << str << endl;
            int x = str[0]-'A';
            int y = str[1]-'A';
            if(!isUnion(x,y)) make_union(x,y) , ans-- ;

        }
      
        cout<<ans<<endl;
    }
   return 0;
     //double end_time = clock();
    //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
}

Share:
Read More

216 - Getting in Line

, No comments

216 - Getting in Line

Topic: Travelling Salesman Problem

Solution 01: Github gist


  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
#include<bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define MAX 100005
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

typedef long long ll;
vector<pair<int,int> >v;
double graph[20][20], TSP;
 int n;
 vector<int> path;

 void path_print(){
  //cerr<<"Enter---\n";
  //for(int i = 0; i < path.size(); i++)cout << path[i] << " ";
    //cout << endl;
  for(int i = 0; i < path.size()-1; i++){
    int x = path[i];
    int y = path[i+1];
    cout <<"Cable requirement to connect ("<<v[x].first<<","<<v[x].second<<") to ("<<v[y].first<<","<<v[y].second<<") is "<<fixed<<setprecision(2)<<graph[x][y]<<" feet.\n";
    cerr << v[x].first << " "<<v[x].second<<endl;
  }
 }

double tsp(int s, double mn)
{
    vector<int>vertex;
    for(int i = 0; i < n; i++){
        if(i != s)
            vertex.push_back(i);
    }

    double min_path = 99999999.0;
    do{
        double current_pathweight = 0.0;
        int k = s;
        for(int i = 0; i < vertex.size(); i++){
            current_pathweight += graph[k][vertex[i]];
            k = vertex[i];
        }
        //current_pathweight += graph[k][s];

        //min_path = min(min_path, current_pathweight);
        if(min_path > current_pathweight && mn > current_pathweight){
          min_path = current_pathweight;
          path.clear();
          path.push_back(s);
          for(int i = 0; i < vertex.size(); i++)path.push_back(vertex[i]);
        }
    }while(next_permutation(vertex.begin(), vertex.end()));
    return min_path;
}

void print()
{
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      cout << setw(3)<<graph[i][j] << " ";
    }
    cout << endl;
  }
}


int main()
{
    //FASTIO
   /* 
   //double start_time = clock();
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
  #endif
    //*/
    int cnt = 0;
    while(cin >> n && n){
      TSP = 0.0;
      for(int i = 0; i < n;i++){
        int x,y;
        cin >> x >> y;
        v.push_back({x,y});
      }
      for(int i = 0; i < n; i++){
        int x1 = v[i].first;
        int y1 = v[i].second;
        for(int j = i+1; j < n; j++){
          int x2 = v[j].first;
          int y2 = v[j].second;
          double D = sqrt(((x1-x2)*(x1-x2)) + ((y1-y2)*(y1-y2))) + 16.0;
          graph[i][j] = D;
          graph[j][i] = D;
         // cerr << x1 << " "<<y1 << " "<<x2 << " "<<y2<<endl;
        }
        //cerr<<"\n";
      }
      //print();
      double mn = 999999.0;
      for(int i = 0; i < n; i++){
         TSP = tsp(i, mn);
         mn = min(TSP, mn);
      }

      cout << "**********************************************************\n";
      cout << "Network #"<<++cnt<<"\n";
      path_print();
      cout <<"Number of feet of cable required is "<<fixed<<setprecision(2)<< mn<<".\n";
      path.clear();
      v.clear();
    }

        //double end_time = clock();
  //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
   
    return 0;
}

Share:
Read More

12461 - Airplane

, , , No comments

12461 - Airplane

EXPLANATION

Solution:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
#include<bits/stdc++.h>
using namespace std;

int main()
{
int n;
while(cin >> n && n){
cout << "1/2\n";
}
return 0;
}

Share:
Read More

315 - Network

, , , No comments

315 - Network

Topic : Graph Theory(AP)

Solution 01:



 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
#include<bits/stdc++.h>
using namespace std;

#define Max 100000
vector<int> graph[Max];
int parent[Max];
int low[Max];
int d[Max];
int visited[Max];
bool isArticulationPoint[Max];
int Time = 0;

void dfs(int u, int root)
{
    Time = Time + 1;
    visited[u] = Time;
    d[u] = low[u] = Time;
    int noOfChildren = 0;
    for(int i = 0; i <graph[u].size(); i++){
        int v = graph[u][i];
        if(v == parent[u])continue;
        parent[v] = u;
        if(visited[v]) low[u] = min(low[u], d[v]);
        else{
            noOfChildren = noOfChildren + 1;
            dfs(v, root);
            low[u] = min(low[u], low[v]);
            if(low[v] >= d[u] and u != root)isArticulationPoint[u] = true;
        }
    }
    if(u == root and noOfChildren > 1)isArticulationPoint[u] = true;
}

int main()
{
    int n,x,y;
    char c;
    while(cin >> n && n)
    {
        Time = 0;
        for(int t = 0; t <= n; t++){
            graph[t].clear();
            parent[t]= low[t] = d[t] = visited[t] = 0;
            isArticulationPoint[t] = false;
        }
        while(scanf("%d", &x) == 1 && x)
        {
            while(scanf("%d%c", &y, &c) == 2)
            {
                graph[x].push_back(y);
                    graph[y].push_back(x);
                if(c == '\n') break;
            }
        }
        dfs(1, 1);
        cout << count(isArticulationPoint+1, isArticulationPoint+n+1, true)<<endl;
    }
    return 0;
}

Share:
Read More

11456 - Trainsorting

, No comments

11456 - Trainsorting

Solution:01



 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
#include<bits/stdc++.h>
using namespace std;
#define Max 2005

int main()
{
    int a[Max], x[Max], y[Max];
    ios_base::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        for(int i = 0; i < n; i++){
            cin >> a[i];
        }
        int ans = 0;
        for(int i = n-1; i >=0 ; i--){
            x[i] = 1;
            y[i] = 1;
            for(int k = i+1; k < n; k++){
                if(a[i] < a[k]){
                    x[i] = max(x[k]+1, x[i]);
                }
                if(a[i] > a[k]){
                    y[i] = max(y[k]+1, y[i]);
                }
            }
            ans = max(ans, x[i]+y[i]-1);
        }
        cout << ans << endl;
    }
    return 0;
}

Share:
Read More

11417 - GCD

, , No comments

11417 - GCD 


 Topic: GCD


Code:

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

typedef long long ll;

int main()
{

   //double start_time = clock();
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
  #endif
    int n;
    while(cin >> n && n){
      int ans = 0;
    for(int i = 1; i < n; i++){
      for(int j = i+1; j <= n; j++){
        ans += __gcd(i,j);
      }
    }
    cout << ans << endl;
  }

    return 0;
}

Share:
Read More

UVA-10130

, No comments
Problem link: UVA-10130

Topic: Knapsack


Solution:

#include<bits/stdc++.h>
using namespace std;
int wt[12345], val[12345];

int Knapsack(int w, int wt[], int val[], int n)
{
    int k[n+1][w+1];

    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j <= w; j++)
        {
            if(i == 0 || j == 0)k[i][j] = 0;
            else if(wt[i-1] <= j)
                k[i][j] = max(val[i-1]+k[i-1][j-wt[i-1]], k[i-1][j]);
            else k[i][j] = k[i-1][j];
        }
    }
    return k[n][w];
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        memset(val, 0, sizeof(val));
        memset(wt, 0, sizeof(wt));
        scanf("%d",&n);
        for(int i = 0; i < n; i++)
        {
            scanf("%d%d",&val[i], &wt[i]);
        }
        int k,W;
        scanf("%d",&k);
        int ans =0;
        while(k--)
        {
            int x;
            scanf("%d",&x);
            ans += Knapsack(x, wt, val, n);
        }
        printf("%d\n", ans);
    }
    return 0;
}

Share:
Read More

About

let's start CODE

Popular Posts

  • E-maxx training part - 01
                             Binary Exponentiation 1230 - MODEX              Solution 11029 - Leading and Trailing      Solution I...
  • 11029 - Leading and Trailing
    11029 - Leading and Trailing  Topic: Binary Exponentiation  
  • A - Frog 1
    A - Frog 1 Solution 01: IH19980412 //copy 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 2...