10685 - Nature

Problem Link


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

const int MAXN = 5005;
int parent[MAXN];

void opt()
{
    for(int i = 1; i < MAXN; 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()
{
    int C, R;
    while(cin>>C>>R && C+R!=0)
    {
        opt();
        map<string, int>mp;
        map<int,int>ans;
        int p = 0, c, mx = 0;
        c = C;
        while(C--)
        {
            string s;
            cin>>s;
            mp[s] = ++p;
        }

        while(R--)
        {
            int a, b;
            string s, predator;
            cin>>s>>predator;
            a = mp[s];
            b = mp[predator];
            make_union(a,b);
        }
        for(int i = 1; i <= c; i++)
        {
            int k = find_parent(i);
            ans[k]++;
            mx = max(mx, ans[k]);
        }
        cout<<mx<<endl;
    }

    return 0;
}

459 - Graph Connectivity

Problem Link

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

const int MAXN = 30;
int parent[MAXN];

void opt()
{
    for(int i = 1; i < MAXN; 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()
{
    int T, t;
    cin>>T;
    t = T;
    getchar();
    while(T--)
    {
        if(t-1!=T)
            cout<<endl;
        opt();
        int n;
        char ch;
        string s;
        cin>>ch;
        getchar();
        n = 1 + (ch - 'A');
        while(getline(cin,s) && s!="")
        {
            int a, b;
            a = 1 + (s[0] - 'A');
            b = 1 + (s[1] - 'A');
            if(!isUnion(a,b))
            {
                make_union(a,b);
                n--;
            }
        }
        cout<<n<<endl;
    }

    return 0;
}

216 - Getting in Line

Problem Link

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

int n;
vector<int>path;
double dist[MAX][MAX];

double TSP()
{
    vector<int>vertex;
    for(int i = 1; i <= n; i++)
            vertex.push_back(i);
    double min_path = numeric_limits<double>::max();

    do
    {
        double curr_pathweight = 0.0;
        for(int i = 0; i < vertex.size(); i++)
        {
            curr_pathweight += dist[vertex[i]][vertex[i+1]];
        }
        if(min_path > curr_pathweight)
        {
            min_path = curr_pathweight;
            path = vertex;
        }
    }
    while(next_permutation(vertex.begin(), vertex.end()));

    return min_path;
}


int main()
{
    int test = 0;
    while(cin>>n && n)
    {
        memset(dist, 0.0, sizeof(dist));
        double x[10], y[10];
        for(int i = 1; i <= n; i++)
            cin>>x[i]>>y[i];
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                dist[i][j] = sqrt(((x[i]-x[j]) * (x[i] - x[j])) + ((y[i] - y[j]) * (y[i] - y[j]))) + 16.00;
            }
        }
        cout<<"**********************************************************"<<endl;
        cout<<"Network #"<< ++test<<endl;
        double ans = TSP();
        for(int i = 0; i < path.size()-1; i++)
        {
            int pin = path[i];
            int pin1 = path[i+1];
            cout<<fixed<<setprecision(2)<<"Cable requirement to connect ("<<(int)x[pin]<<","<<(int)y[pin]<<") to ("<<(int)x[pin1]<<","<<(int)y[pin1]<<") is "<<dist[pin][pin1]<<" feet."<<endl;
        }
        cout<<fixed<<setprecision(2)<<"Number of feet of cable required is "<<ans<<"."<<endl;
    }

    return 0;
} 

787 - Maximum Sub-sequence Product

Problem Link

My Solution:


import java.math.BigInteger;
import java.math.BigDecimal;
import java.util.Scanner;

class Main {
   
    public static void main (String[] args) {
      
        Scanner scr = new Scanner(System.in);
        BigInteger n, pin, curr_max, curr_min, prev_max = null, prev_min = null, ans = null;
        Boolean flag = true;
        pin = new BigInteger("-999999");
        while(scr.hasNext()) {
          
            n = scr.nextBigInteger();
          
            if(n.equals(pin)) {
              
                System.out.println(ans);
                flag = true;
              
            }
          
            else if(flag) {
              
                flag = false;
                curr_max = n;
                curr_min = n;
                prev_max = n;
                prev_min = n;
                ans = n;
              
            }
          
            else {
              
                BigInteger temp, temp1, temp2;
                temp = prev_max.multiply(n);
                temp1 = prev_min.multiply(n);
                temp2 = temp1.max(n);
                curr_max = temp2.max(temp);
                temp2 = temp1.min(n);
                curr_min = temp2.min(temp);
                ans = ans.max(curr_max);
                prev_max = curr_max;
                prev_min = curr_min;
              
            }
          
        }
      
    }
   
}

10034 - Freckles

Problem Link

এখানে N টা points দেওয়া থাকবে , প্রতিটা point কে একেকটা নোড ধরবো আর একটা থেকে আরেকটার distance হবে একটা edge এর weight। যদি (x₁,y₁) & (x₂,y₂) দুইটা point হয়, তাহলে-
                               distance between two points = √( (x₁ - x₂)² + (y₁-y₂)² )
বাকিটা কি করতে হবে এটা বুঝে যাওয়ার কথা ... না বুঝলেও সমস্যা নাই। এখন আমরা minimum weight পেতে MST ব্যবহার করব।

আরেকটা জিনিস খেয়াল রাখতে হবে, শেষ test case এর output print করার পর কোনো নতুন লাইন প্রিন্ট হবে না।

My Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<double, int>
const int MAX = 1005;
vector<pii> adj[MAX];
bool marked[MAX];

double Prim(int x)
{
    priority_queue<pii, vector<pii>, greater<pii> > Q;
    memset(marked, false, sizeof(marked));
    int y;
    double minimumcost = 0;
    pii p;
    Q.push(mp(0, x));

    while(!Q.empty())
    {
        p = Q.top();
        Q.pop();
        x = p.second;
        if(marked[x]==true)
            continue;
        minimumcost += p.first;
        marked[x] = true;
        for(int i = 0; i < adj[x].size(); i++)
        {
            y = adj[x][i].second;
            if(marked[y]==false)
                Q.push(adj[x][i]);
        }
    }
    return minimumcost;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        for(int i = 0; i < MAX; i++)
            adj[i].clear();
        int n;
        double minimumcost;
        double x[105], y[105];
        cin>>n;
        for(int i = 1; i <= n; i++)
            cin>>x[i]>>y[i];
        for(int i = 1; i <= n; i++)
        {
            for(int j = i+1; j <= n; j++)
            {
                double s;
                s = sqrt(pow(x[j]-x[i],2) + pow(y[j]-y[i],2));
                adj[i].push_back(mp(s,j));
                adj[j].push_back(mp(s,i));
            }
        }

        minimumcost = Prim(1);
        cout<<fixed<<setprecision(2)<<minimumcost<<endl;
        if(T)
            cout<<endl;
    }

    return 0;
}

544 - Heavy Cargo

Problem Link

এটা modified shortest path finding algorithm(BFS/DFS/Dijkstra/Floyed Warshall যেকোন একটা) দিয়ে করতে হবে। যেহেতু input এর range অনেক ছোট তাই আমি Floyed Warshall দিয়ে করেছি।

My Code: 

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

int n, r;
int d[205][205];

void FloyedWarshall()
{
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                d[i][j] = d[j][i] = max(d[i][j],min(d[i][k],d[k][j]));
}

int main()
{
    for(int t = 1; scanf("%d %d",&n,&r) && (n!=0 && r!=0); t++)
    {
        map<string,int>name;
        string u, v, Start, End;
        int cost, idx = 1;
        for(int i = 0; i < 100; i++)
            for(int j = 0; j < 100; j++)
                if(i==j) d[i][j] = 0;
                else d[i][j] = -inf;
        for(int i = 0; i < r; i++)
        {
            cin>>u>>v>>cost;
            if(!name[u])
                name[u] = idx++;
            if(!name[v])
                name[v] = idx++;
            d[name[u]][name[v]] = cost;
            d[name[v]][name[u]] = cost;
        }
        FloyedWarshall();
        cin>>Start>>End;
        cout<<"Scenario #"<<t<<endl;
        cout<<d[name[Start]][name[End]]<<" tons"<<endl;
        cout<<endl;
        name.clear();
    }

    return 0;
}

10462 - Is There A Second Way Left?

Problem Link

একটা weighted undirected graph দেওয়া থাকবে। এখান থেকে আমাদের Second Best MST (Minimum spanning tree) বের করতে হবে। [এর আগে অবশ্যই Kruskal আর Prim এর উপর ভাল idea থাকা লাগবে, না থাকলে এই লিঙ্কটা দেখে আসব।]

তিন ধাপে আমরা এটা সমাধান করতে পারি।
১) graph connected কিনা check করব, যদি connected না হয় তাহলে "No way" প্রিন্ট করব। 
২) এখন MST বের করতে হবে এবং যে edge গুলো MST এর part ঐ গুলো চিহ্নিত করতে হবে।
৩) আগের edge গুলো (যা MST এর part ছিল) একটি একটি বাদ দিয়ে MST তৈরি করতে হবে আর এর minimum value টা নিতে হবে। এইভাবেই আমরা Second Best MST পাব।

My Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int, int>
const int MAX = 300;
int id[MAX], nodes, edges, cnt = 0;
pair<ll, pii> p[MAX];
vector<int>edge;

void initialize()
{
    for(int i = 0; i < MAX; i++)
        id[i] = i;
}

int root(int x)
{
    if(id[x] == x)
        return x;
    return id[x] = root(id[x]);
}

void make_union(int x, int y)
{
    id[root(x)] = id[root(y)];
}

ll Kruskal()
{
    initialize();
    cnt = 0;
    int x, y, flag = 0;
    ll cost, minimumcost = 0;
    for(int i = 0; i < edges; i++)
    {
        x = p[i].second.first;
        y = p[i].second.second;
        cost = p[i].first;

        if(root(x)!=root(y))
        {
            flag++;
            cnt++;
            edge.push_back(i);
            minimumcost += cost;
            make_union(x,y);
        }
    }
    if(flag==nodes-1)
        return minimumcost;
    return -1;
}

ll SBMST()  ///function to find second best MST
{
    ll maximum = 1e18;

    for(int j = 0; j < cnt; j++)
    {
        initialize();
        int x, y, flag = 0;
        ll cost, minimumcost = 0;
        for(int i = 0; i < edges; i++)
        {
            if(edge[j]!=i)  ///age use hoise emn value baad dibo
            {
                x = p[i].second.first;
                y = p[i].second.second;
                cost = p[i].first;

                if(root(x)!=root(y))
                {
                    flag++;
                    minimumcost += cost;
                    make_union(x,y);
                }
            }
        }
        //cout<<minimumcost<<endl;
        if(flag==nodes-1)
            maximum = min(minimumcost,maximum);  ///minimum value ta nibo
    }

    if(maximum!=1e18)
        return maximum;
    return -1;
}

int main()
{
    int T;
    cin>>T;
    for(int t = 1; t <= T; t++)
    {
        int u, v;
        ll weight;
        cin>>nodes>>edges;
        for(int i = 0; i < edges; i++)
        {
            cin>>u>>v>>weight;
            p[i] = mp(weight, mp(u,v));
        }

        sort(p, p + edges);

        cout<<"Case #"<<t<<" : ";
        if(Kruskal()==-1)
            cout<<"No way"<<endl;
        else
        {
            ll minimumcost = SBMST();

            if(minimumcost==-1)
                cout<<"No second way"<<endl;
            else
                cout<<minimumcost<<endl;
        }

        for(int i = 0; i < MAX; i++)  /// Reset the pair (er chaite valo way jana nai -_-)
        {
            p[i].first = 0;
            p[i].second.first = 0;
            p[i].second.first = 0;
        }
        edge.clear();
    }

    return 0;
}

674 - Coin Change

Problem link

It is a classical problem of Coin change problem.
In this problem test case number has no limit(>10^7). So, if you call recursion function for each test case it must get WA. To get ride off this problem you have to do pre-calculation and store answer in a array.

My Code is given below:

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

int A[] = {1,5,10,25,50};
int table[7490];

void coin_change()
{
    memset(table,0,sizeof(table));

    table[0] = 1;

    for(int i = 0; i < 5; i++)
        for(int j = A[i]; j <= 7489; j++)
            table[j] += table[j-A[i]];
}

int main()
{
    int make;
    coin_change();
    while(cin>>make)
    {
        cout<<table[make]<<endl;
    }

    return 0;
}

10130 - SuperSale

Problem Link

This is a classical 0-1 Knapsack Problem.
To solve this problem please read this first.

Now, first try by yourself.
If you get any difficulty , you can get help from my solution...

//Time Complexity O(item * bag_weight * G)
#include<bits/stdc++.h>
using namespace std;

int weight[10000], value[10000];

int knapsack(int bag_weight, int item)
{
    int K[item+1][bag_weight+1];
    for(int i = 0; i <= item; i++)
    {
        for(int w = 0; w <= bag_weight; w++)
        {
            if(i==0 || w==0)
                K[i][w] = 0;
            else if(weight[i-1]<=w)
                K[i][w] = max(K[i-1][w], K[i-1][w-weight[i-1]]+value[i-1]);
            else
                K[i][w] = K[i-1][w];
        }
    }

    return K[item][bag_weight];
}

int main()
{
    int T;
    cin>>T;
    for(int t = 0; t < T; t++)
    {
        int A[31] = {0}, sum = 0;
        int n;
        cin>>n;
        for(int i = 0; i < n; i++)
            cin>>value[i]>>weight[i];
        int G, MG;
        cin>>G;
        for(int i = 0; i < G; i++)
        {
            cin>>MG;
            if(A[MG]==0)
                A[MG] = knapsack(MG,n);
            sum+=A[MG];
        }
        cout<<sum<<endl;
    }
    return 0;
}

686 - Goldbach's Conjecture (II)

Problem Link

For any integer n (n ≥ 4) there exist two prime numbers p1 and p2 such that p1 + p2 = n. In a problem we might need to find the number of essentially different pairs (p1, p2), satisfying the condition in the conjecture for a given even number n (4 ≤ n ≤ 2 15). (The word ‘essentially’ means that for each pair (p1, p2) we have p1 ≤p2.)
For example, for n = 10 we have two such pairs: 10 = 5 + 5 and 10 = 3 + 7.

Thus my solution in C++ :

1.  #include<bits/stdc++.h>
2. using namespace std;
3. #define MAX 10000000  ///~10^7
4. bool prime[MAX];
5. vector <int> p;
6. void sieve()
7. {
8.     memset(prime,0,sizeof(prime));
9.     prime[0]=prime[1]=1;
10.     for(int i = 4; i < MAX; i += 2)
11.     {
12.         prime[i] = 1;
13.     }
14.     for(int i = 3; i*i < MAX; i += 2)
15.     {
16.         if(!prime[i])
17.         {
18.             for(int j = i*i; j < MAX; j += i)
19.                 prime[j] = 1; /// not prime
20.         }
21.     }
22.     for(int i = 2; i < MAX; i++)
23.         if(!prime[i])
24.             p.push_back(i);
25. }
26. int FindSol(int n)
27. {
28.     int res = 0;
29.     for(int i = 2; i <= n/2; i++)
30.         if(!prime[i] && !prime[n-i])
31.             res++;
32.     return res;
33. }
34. int main()
35. {
36.     int n;
37.     sieve();
38.     while(cin>>n && n)
39.         cout<<FindSol(n)<<endl;
40.     return 0;
41. }