Monday, July 02, 2018

[TCS] Online Communities - Even Groups (CodeVita) Problem [Solved]

Problem : Online Communities - Even Groups
In a social network, online communities refer to the group of people with an interest towards the same topic. People connect with each other in a social network. A connection between Person I and Person J is represented as C I J. When two persons belonging to different communities connect, the net effect is merger of both communities which I and J belonged to.

We are only interested in finding out the communities with the member count being an even number. Your task is to find out those communities.

Input Format:

Input will consist of three parts, viz.

1. The total number of people on the social network (N)
2.Queries 
  • C I J, connect I and J
  • Q 0 0, print the number of communities with even member-count
-1 will represent end of input.

Output Format:

For each query Q, output the number of communities with even member-count
Constraints:

1<=N<=10^6

1<=I, J<=N

Sample Input and Output


SNo. Input Output
1
5
Q 0 0
C 1 2
Q 0 0
C 2 3
Q 0 0
C 4 5
Q 0 0
-1

0
1
0
1



Solution:
//Problem: Online communities- Even groups

#include<iostream>
using namespace std;
int comm[1000001],n;
void mergecom(int,int);
//void print();
int even(int);
int main(){
    int x,y,comNo=1;
    char c;
    cin>>n;
    while(true){
        cin>>c;
        if(c=='C'){
            cin>>x>>y;
            if(comm[x]==0 && comm[y]==0){
                comm[x]=comm[y]=comNo;
                comNo++;
            }
            else if(comm[x]==0){
                comm[x]=comm[y];
            }
            else if(comm[y]==0){
                comm[y]=comm[x];
            }
            else if(comm[x]>comm[y]){
                mergecom(comm[y],comm[x]);
                comNo--;
            }
            else if(comm[y]>comm[x]){
                mergecom(comm[x],comm[y]);
                comNo--;
            }
        }
        else if(c=='Q'){
            cin>>x>>y;
            cout<<even(comNo)<<endl;
        }
        else
            break;
    }

return 0;
}

void mergecom(int x,int y){
    for(int i=0;i<=n;i++){
        if(comm[i]==y)
            comm[i]=x;
        else if(comm[i]>y)
            comm[i]--;
    }
}
int even(int comNo){
int count =0,temp=0;
for(int i=1;i<comNo;i++){
    for(int j=0;j<=n;j++){
        if(comm[j]==i)
            temp++;
    }
    if(temp%2==0 && temp!=0){
        count++;
    }
    temp=0;
}
return count;
}
/*
void print(){
for(int i=0;i<=n;i++)
    cout<<i<<comm[i]<<" ";
cout<<endl;
}*/


Consider the following example. 

Dhaniram wants to buy a TV. He needs to pay Rs 2000/- per month for 12 installments to own the TV. If let's say he gets 4% interest per annum on his savings bank account, then Dhaniram will need to deposit a certain amount in the bank today, such that he is able to withdraw Rs 2000/- per month for the next 12 months without requiring any additional deposits throughout. 

Your task is to find out how much Dhaniram should deposit today so that he gets assured cash flows for a fixed period in the future, given the rate of interest at which his money will grow during this period. 

Input Format: 

First line contains desired cash flow M 
Second line contains period in months denoted by T 
Third line contains rate per annum R expressed in percentage at which deposited amount will grow 

Output Format: 

Print total amount of money to be deposited now rounded off to the nearest integer 

Constraints:
M > 0

T > 0

R >= 0

Calculation should be done upto 11-digit precision


Sample Input and Output

SNo. Input Output
500
3
12

1470
6000
3
5.9

17824
500
2
0

1000
www.matterhere.com - Nareddula Rajeev Reddy (NRR)
Programming Geek
Source: programmaniaa blog.

*To get the more, view the [TCS] Online Communities - Even Groups (CodeVita) Problem [Solved]. These are only for reference purpose.

* Ask us, what you want?
EmoticonEmoticon