TCS CodeVita 2014 Problems - Round 1

CodeVita coding contest from Tata Consultancy Services (TCS) lets you pit your skills against contestants around the globe.
Students from India, New Zealand, Australia, South Africa, Peru, Mexico, Colombia, and Uruguay are participating this year in CodeVita 2014.

Round 1 and Round 2 is completed and top 5% coders from Round 2 will participate in Round 3.

CodeVita Round-1 Problems

A : 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.


B : Problem : Zombie World

Zoya has developed a new game called Zombie World. The objective of the game is to kill all zombies in given amount of time. More formally,
- N represents the total number of zombies in the current level
- T represents the maximum time allowed for the current level
- P represents the initial energy level a player starts with
- Ei defines the energy of the i-th zombie
- D defines the minimum energy the player needs, to advance to the next level

When a player energy is greater than or equal to the i-th zombie's energy, the player wins. Upon winning, the player will be awarded with an additional energy equal to the difference between current zombie energy and the player energy.
One unit of time will be taken to complete the fight with a single zombie.

Rules of the game:- 
- At any given time, a player can fight with only one zombie
- Player is allowed to choose any one zombie to fight with.

Your task is to determine whether the player will advance to the next level or not, if he plays optimally.

Input Format: 
The first line contains the number of test cases (K)

Each test case consists of three parts:
1. The total number of zombies (N) and the maximum time allowed (T)
2. Array of size N, which represents the energy of zombies (E)
3. The initial energy level a player (P) and the minimum energy required to advance (D)

Output Format: 
Print "Yes" if a player can advance to the next level else print "No".

Constraints:
1<=K<=10
1<=N<=50
1<=Ei<=500
1<=T<=100
1<=D<=2000
1<=P<=500

Sample Input and Output

SNo.	Input	Output
1	1 2 3 4 5 5 7	Yes

C : Stone Game - One Four

Alice and Bob are playing a game called "Stone Game". Stone game is a two-player game. Let N be the total number of stones. In each turn, a player can remove either one stone or four stones. The player who picks the last stone, wins. They follow the "Ladies First" norm. Hence Alice is always the one to make the first move. Your task is to find out whether Alice can win, if both play the game optimally.

Input Format: 
First line starts with T, which is the number of test cases. Each test case will contain N number of stones.

Output Format: 
Print "Yes" in the case Alice wins, else print "No".

Constraints:
1<=T<=1000
1<=N<=10000

Sample Input and Output

SNo.	Input	Output
1	3 1 6 7	Yes Yes No

D : Trace the Rats

Given a square maze (A) of dimension N, every entry (Aij) in the maze is either an open cell 'O' or a wall 'X'. A rat can travel to its adjacent locations (left, right, top and bottom), but to reach a cell, it must be open. Given the locations of R rats, can you find out whether all the rats can reach others or not?

Input Format: 
Input will consist of three parts, viz.

1. Size of the maze (N)
2. The maze itself (A = N * N)
3. Number of rats (R)
4. Location of R rats (Xi, Yi)

Note: 
(Xi,Yi) will represents the location of the i-th rat.
Locations are 1-index based.

Output Format: 
Print "Yes" if the rats can reach each other, else print "No"

Constraints:
1<=N<=350
Aij = {'O','X'}
1<=R<=N*N
1<=Xi<=N
1<=Yi<=N

Sample Input and Output

SNo.	Input	Output
1	3 O O X O X O O O X 4 1 1 1 2 2 1 3 2	Yes
2	3 O O X O X O O O X 4 1 1 1 2 2 1 2 3	No

E : 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

Explanation:
For first query there are no members in any of the groups hence answer is 0.
After C 1 2, there is a group (let's take it as G1) with 1 and 2 as members hence total count at this moment is 1.
After C 2 3 total members in G1 will become {1, 2, 3} hence there are no groups with even count.
After C 4 5 there formed a new group G2 with {4, 5} as members, hence the total groups with even count is 1.


F : 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 by S 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

Explanation: 

Initial Matrix

1 2
3 4
After 90 degree rotation, the matrix will become
3 1
4 2
Now the element at A11 is 3 and A12 is 1.
Again the angle of rotation is 90 degree, now after the rotation the matrix will become
4 3
2 1
Now the element at A11 is 4.
As the next operation is Update, update initial matrix i.e.
6 2
3 4
After updating, apply all the previous rotations (i.e. 180 = two 90 degree rotations).
The matrix will now become
4 3
2 6
Now A22 is 6.


G : Compiler Design - Limit the Method Instructions

Raj is a newbie to the programming and while learning the programming language he came to know the following rules:
- Each program must start with '{' and end with '}'.
- Each program must contain only one main function. Main function must start with '<' and end with '>'.
- A program may or may not contain user defined function(s). There is no limitation on the number of user defined functions in the program. User defined function must start with '(' and end with ')'.
- Loops are allowed only inside the functions (this function can be either main function or user defined function(s)). Every loop must start with '{' and end with '}'.
- User defined function(s) are not allowed to be defined inside main function or other user defined function(s).
- Nested loops are allowed.
- Instructions can be anywhere inside the program.
- Number of instructions inside any user defined function must not be more than 100.

If any of the above conditions is not satisfied, then the program will generate compilation errors. Today Raj has written a few programs, but he is not sure about the correctness of the programs. Your task is to help him to find out whether his program will compile without any errors or not.

Input Format: 
First line starts with T, number of test cases. Each test case will contain a single line L, where L is a program written by Raj.

Output Format: 
Print "No Compilation Errors" if there are no compilation errors, else print "Compilation Errors".

Constraints:
1<=T<=100
L is a text and can be composed of any of the characters {, }, (, ), <, >and P, where P will represents the instruction.
L, comprised of characters mentioned above should be single spaced delimited.
Number of characters in the text, |L| < = 10000

Sample Input and Output

SNo.	Input	Output
1	3 { < > ( P ) } { < { } > ( { } ) ) { ( { } ) }	No Compilation Errors Compilation Errors Compilation Errors

Important Note: 
Please do not use package and namespace in your code. For object oriented languages your code should be written in one class.
Participants submitting solutions in C language should not use functions from <conio.h> / <process.h> as these files do not exist in gcc

CodeVita 2014 Problems - Round 2

Happy Coding!