TCS codevite 2014 problem: Super ASCII String Checker

Problem : Super ASCII String Checker

In the Byteland country a string "S" is said to super ascii string if and only if count of each character in the string is equal to its ascii value.

In the Byteland country ascii code of 'a' is 1, 'b' is 2 ...'z' is 26.

Your task is to find out whether the given string is a super ascii string or not.

Input Format:

First line contains number of test cases T, followed by T lines, each containing a string "S".

Output Format:

For each test case print "Yes" if the String "S" is super ascii, else print "No"

Constraints:

1<=T<=100

1<=|S|<=400, S will contains only lower case alphabets ('a'-'z').

Sample Input and Output

SNo.	Input	Output
1	2 bba scca	Yes No

Explanation:

In case 1, viz. String "bba" -
The count of character 'b' is 2. Ascii value of 'b' is also 2.
The count of character 'a' is 1. Ascii value of 'a' is also 1.
Hence string "bba" is super ascii.

Solution:

#include<iostream>

using namespace std;

int c[26];

int main(){

    int t,len,flag=1;;

    string s;

    cin>>t;

    while(t--){

        cin>>s;

        len=s.length();

        for(int i=0;i<len;i++)

            c[int(s[i])-int('a')]++;

        for(int i=0;i<26;i++){

            if(!(c[i]==0 || c[i]==i+1))

                flag=0;

        }

        if(flag==1)

            cout<<"Yes\n";

        else

            cout<<"No\n";

        for(int i=0;i<26;i++)

            c[i]=0;

        flag=1;

    }

    return 0;

}

TCS codevite 2014 question with solution Matrix Rotations

Problem : Matrix Rotations

You are given a square matrix of dimension N. Let this matrix be called A. Your task is to rotate A in clockwise direction byS degrees, where S is angle of rotation. On the matrix, there will be 3 types of operations viz. 

1. Rotation

   Rotate the matrix A by angle S, presented as input in form of A S 

2. Querying

   Query the element at row K and column L, presented as input in form of Q K L

3. Updation

   Update the element at row X and column Y with value Z,  presented as input in form of U X Y Z

Print the output of individual operations as depicted in Output Specification

Input Format:

Input will consist of three parts, viz.
1. Size of the matrix (N)
2. The matrix itself (A = N * N)
3. Various operations on the matrix, one operation on each line. (Beginning either with A, Q or U)

-1 will represent end of input.

Note:

• Angle of rotation will always be multiples of 90 degrees only.
• All Update operations happen only on the initial matrix. After update all the previous rotations have to be applied on the updated matrix

Output Format:

For each Query operation print the element present at K-L location of the matrix in its current state.

Constraints:

1<=N<=1000

1<=Aij<=1000

0<=S<=160000

1<=K, L<=N

1<=Q<=100000

Sample Input and Output

SNo.	Input	Output
1	2 1 2 3 4 A 90 Q 1 1 Q 1 2 A 90 Q 1 1 U 1 1 6 Q 2 2 -1	3 1 4 6

Solution:

#include<iostream>

using namespace std;

int n,mat[1000][1000],initial[1000][1000];

int temp[1000][1000];

//void print();

void transpose();

void rotate(int);

int main(){

    int x,y,z;

    int total=0;

char c;

cin>>n;

for(int i=0;i<n;i++){

    for(int j=0;j<n;j++){

        cin>>mat[i][j];

        initial[i][j]=mat[i][j];

}

}

while(true){

    cin>>c;

    if(c=='A'){

        cin>>x;

        rotate(x);

        total+=x;

    }

    else if(c=='Q'){

        cin>>x>>y;

        cout<<mat[x-1][y-1]<<endl;

    }

    else if(c=='U'){

            cin>>x>>y>>z;

        for(int i=0;i<n;i++){

            for(int j=0;j<n;j++)

                mat[i][j]=initial[i][j];

        }

        mat[x-1][y-1]=z;

        rotate(total);

        //print();

    }

    else

        break;

}

return 0;

}

void transpose(){

 for(int i=0;i<n;i++){

    for(int j=0;j<n;j++){

        temp[j][n-i-1]=mat[i][j];

    }

 }

 for(int i=0;i<n;i++){

    for(int j=0;j<n;j++){

        mat[i][j]=temp[i][j];

    }

 }

}

void rotate(int x){

int t=x/90;

t=t%4;

while(t--){

    transpose();

       // print();

}

}/*

void print(){

    cout<<"printing matrix\n";

for(int i=0;i<n;i++){

    for(int j=0;j<n;j++){

        cout<<mat[i][j]<<" ";

    }

    cout<<endl;

}

}*/

TCS codevite 2014 Question with solution

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;

}*/