TCS CodeVita 2016 Round2 Question

 Mate in two
 Decrypt the Crypt
 Crack the Password
 Verify JSON Object Validity
 The Mystery of Sky
 Collecting Candies
 the Vita Sum
 Game of Marbles

Problem : Mate In Two

Background

A Chess board position is accurately captured by Forsyth-Edwards notation and is

abbreviated as FEN. A FEN "record" defines a particular game position, all in one line of
text and using only the ASCII character set. A FEN record consists of six fields. A complete
description of the FEN format to represent Chess positions can be found here

For the purpose of this problem, only consider first of the six fields of FEN. Before we
describe the problem, let us look at how FEN maps to a board position. The following 5
images show board positions and its corresponding FEN representation.

Figure 1.

This board position depicts initial position before

any side has made a move. In FEN format this board
position is represented as

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR
 Let's say, White plays e4. Then the board position looks like shown below

Figure 2.

This board position depicts the Chess board after

White has played e4. In FEN format this board position
is represented as

rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR

Similarly, 3 more half-moves are depicted in following diagrams

Figure 3. Figure 4. Figure 5.

The FENs corresponding to Figure 3, 4 and 5 are represented as

3. rnbqkbnr/pppp1ppp/8/4p3/4P3/8/PPPP1PPP/RNBQKBNR

4. rnbqkbnr/pppp1ppp/8/4p3/4PP2/8/PPPP2PP/RNBQKBNR

5. rnbqkbnr/pppp1ppp/8/8/4Pp2/8/PPPP2PP/RNBQKBNR
Wikipedia describes first field of FEN format as follows

Piece placement (from white's perspective). Each rank is described, starting with rank 8
and ending with rank 1; within each rank, the contents of each square are described from
file "a" through file "h". Following the Standard Algebraic Notation (SAN), each piece is
identified by a single letter taken from the standard English names (pawn = "P", knight =
"N", bishop = "B", rook = "R", queen = "Q" and king = "K").[1] White pieces are designated
using upper-case letters ("PNBRQK") while black pieces use lowercase ("pnbrqk"). Empty
squares are noted using digits 1 through 8 (the number of empty squares), and "/"
separates ranks

Statement

Given a board position in FEN format, your task is to find out all move(s) that lead to a
forced mate. White to play and win in 2 moves.

Input Format:

1. First line contains single FEN record, which corresponds to a particular

board position

Output Format:

1. The output must be printed as follows

a. A string in format by "< move format >-< move format >-< move
format >", where first move is white move, second is black move and third
is again a white move
b. Where < move format > is move represented in format
"fromSquaretoSquare"
2. See Example section for better understanding of output format

Constraints:

1. The board position will always be White to move and mate in 2

 2. Since we focus on only first part of the FEN, we are essentially ignoring
possibility of Castling being a mating move. Hence our test cases don't contain
FENs which give rise to such positions.
3. There is no need to handle En Passant positions. There are no test cases
involving En Passant moves.
4. No need to implement pawn promotion rules. Our test cases do not contain
positions which will lead to a pawn getting promoted and inflicting a mate.
5. There is exactly one forced mating sequence in our test cases. So once a
forced mating sequence is found, there is no need to process further.

Sample Input and Output

SNo. Input Output

1
r1b2rk1/1p4pR/p2pppn1/6q1/3NP1P1/2N2P2/PPP4Q/1K5R h7g7-g8g7-h2h7

2
5r1k/p4p1p/5P1N/1p1p4/2pP3P/8/PP4RK/8 g2g8-f8g8-h6f7

Explanation:

Board position for sample input 1: Mate enforcing moves for input 1:

Figure 6.
Figure 7.
Board position for sample input
Mate enforcing moves for input 2:
2:

Figure 9.
Figure 8.

Problem : Decrypt the Crypt

Statement

Walter uses multiple applications at his workplace. He was assigned a unique password of
variable lengths for each application (maximum length being 10). The only common factor
among them was that all the passwords were a combination of 10 distinct characters.
Walter created an algorithm to encrypt these passwords and wrote the codes on his desk
to avoid a situation in which he would not be able to recollect a password.

Given as an input, is an encoded password and a list of 10 unique characters. Write a

program that obtains the password by reverting the algorithm used by Walter.

Algorithm used by Walter to encode his password is as follows:

1. Walter observes all his passwords and lists down every distinct character.
He assigns an index value to each character from 0 to 9. (Note: This list will be
provided as an input to the program). This list MUST contain 10 DISTINCT
characters.
2. He then replaces every character in the password with the corresponding
index value to convert the password to a 10 digit numeric value.
3. The leftmost digit in this number sequence is noted; let's say 'A'. Now,
starting from the leftmost position, every digit in the number is added to the digit
on its right. The last digit in the sequence is added to 'A'.
4. Step 3 provides new sequences of numbers. He then scans through each of
the summations and if any of the summation results in a value greater than 9, it is
subtracted by 10, and its position is noted (Say B).
 5. He then lists every digit from 0 to 9 separated by '|' character and prepends
each digit with its position in the sequence as noted in 'B'. The resulting sequence
after this step is saved (Say C).
6. The encoded password would therefore be
< value_of_C >||< contents_of_array_B > < Value_of_A >

Decrypt the encrypted password that has been created by Walter using the above
algorithm to compute the actual password!

Print -1 if there is any error in the inputs.

Input Format:
1. First line contains the encoded password as it should be according to
Walter's algorithm
2. Second line contains 10 unique characters

Output Format:

Obtained password by reverting the algorithm. Print -1 if there is any error in the inputs.
Constraints:
1. Second line of input MUST contain 10 DISTINCT characters.
2. Encoded password should be in format
< value_of_C >|| < contents_of_array_B >

Sample Input and Output

SNo. Input Output

1 0|1|2|43|14|5|6|7|308|29||0149
@@Z$$
*Acf$Zd&T@

2 0|1|2|43|14|5|6|7|308|29||0149
-1
*Acf$Zd&T

Explanation of Test Case 1:

NOTE: - The following are the steps used to encrypt the password. Your task is to reverse
the logic and decrypt the encrypted string provided as input, and get back the clear-text
password.
1. Consider input characters and its position

Input character list:*Acf$Zd&T@

Position :0 1 2 3 4 5 6 7 8 9
 2.
(Note: The character list will not contain more than 10 characters and each
character must be unique)
3. Now replace the characters in the password with the position value of the
respective character as defined in step 1, to convert the password into a numeric
value.

Password :@@Z$$
Numeric value:9 9 5 4 4
4.
(Note: Remember leftmost value (Say A) = 9)
5. Starting from the left most position, add each digit to the digit on its right.
Add the last digit with the first digit in the sequence

Numeric value of password:9 9 5 4 4

Addition : 18 14 9 8 13
6.
7. For each addition result equal to or greater than 10, subtract it by 10 and
note its position.

Additive step output :18 14 9 8 13

Selective subtraction:8 4 9 8 3
Numeric value :0 1 4
8.
(Note: Remember the selective subtraction step positions obtained (Say B) = 014)
9. The password will follow the following format

Format:0|1|2|3|4|5|6|7|8|9
10. Now, each number in this format is pre-appended with the positions of the
occurrence of the respective number in the output obtained in selective
subtraction step of Step 4.

Encrypted password:0|1|2|43|14|5|6|7|038|29
11.
(Note: Say C = 0|1|2|43|14|5|6|7|038|29)
12. The final encrypted password will be of the following format to account for
the calculations performed in generating the encrypted password

Encrypted password (format):< C >||< B >< A >

Encrypted password :0|1|2|43|14|5|6|7|308|29||0149

Explanation of Test Case 2:

Second line of input contains 9 characters only hence prints -1

Problem : Crack the Password
Statement

Atul does lots of online transactions and has accounts in multiple banks, but to remember
his passwords he created his own encryption technique and wrote down the enciphered
passwords in a notepad. But he finds it very time consuming to decipher those passwords
so he has asked for your help to develop a program to do the task quickly.

The approach he takes to encipher is,

1. First he writes down his password in a square matrix P of dimension N,
sequentially from the first element (see example for better explanation). He
chooses N such that N^2 is the least number above the length of the password. He
then starts filling the matrix row-wise from top to bottom. If any matrix element
remains blank, he fills all those blanks with the last element e.g. if the last element
filled is z then he fills all other remaining elements in the matrix by z .
2. Then he creates new matrix A of the same dimensions such that every A(i,j)
= P(j,i). Next he assigns the value of the alphabet in the password to that
corresponding element in the matrix. So 'a' is substituted by 1, 'b' by 2, so on.
Alphabets are only lower case. Also passwords contain characters from a to z only.
3. Then he finds another matrix B such that, the solution to the following
equation gives a matrix with all the elements of principal diagonal as 1 and rest as
0, which is also called the eMat( encrypted matrix ) .

Your are provided with the eMat (encrypted matrix) or the matrix B, your task is to find all
possible passwords and print them.

Example:
Let the password be "passwords" as it has 9 characters , the most appropriate matrix will
be a 3X3 matrix, hence the matrix will be

After Step 1:

After step 2:
After step 3:

The eMat for the given matrix will be

-0.783783783780.18918918919 0.70270270270
-0.118503118500.07900207900 0.09563409563
0.87733887734 -0.25155925156 -0.72557172557

Input Format:
1. First line contains integer N, which is the dimension of square matrix eMat
2. Next N lines contain N space separated values (11-digit precision after
decimal point) representing the eMat.

Output Format:

In a single line print the password, if multiple password values are possible print them
separated by space, sorted by ascending order of their lengths.
Constraints:

1. When eMat is converted to Matrix A, round off the numbers in the matrix A
to its nearest integer value to recover the alphabets in the password

Sample Input and Output

SNo. Input Output

3
1 -0.78378378378 0.18918918919 passwords
0.70270270270
 -0.11850311850 0.07900207900
0.09563409563
0.87733887734 -0.25155925156 -
0.72557172557

2
2 0.06666666667 -0.06666666667 pas pass
-0.00350877193 0.05614035088

Problem : Verify JSON Object validity

Statement

A JSON object is a key-value pair data structure that is enclosed within { }. A sample JSON
object would look like
{
"key1":"value1",
"key2":"value2",
"key3": {
"key4":"value4",
"key5":"value5"}
"key6":"value6",
"key7":[
{
"key8":"value8"
}]
}

Given a JSON object, ignore the literal values of the object and check whether the
distinguishing characters and notation of the object are valid to determine if the JSON
object is valid or not.

Note:

1. Key3 points to another JSON object (Concept of nesting of JSON objects).

2. Key7 points to an array of JSON objects.
You may wish to refer site1 to get a more formal description of JSON grammar. site2,site3;
are also good resources to understand JSON specifications.

Input Format:

1. First line contains a pattern of JSON without any literal

Output Format:

Print 1 if pattern is valid, -1 otherwise.

Constraints:
 1. A JSON object should start with '{' and ends with a '}'.
2. The key and value should be separated by a ':'.
3. A ',' suggests an additional JSON property.
4. An array only consists of JSON objects. It cannot contain a "key":"value" pair
by itself.

Example 1:

Input
{:[{},{}]}

Output
1

Explanation
{
"Key": [{
"Key": "Value"
}, {
"Key": "Value"
}]
}
Pattern is following all constraints hence prints 1

Example 2:

Input
{:{[]},{}}

Output
-1

Explanation
Convert this pattern in a JSON Object

{
"Key": {
[
"Key": "Value"
]
},
{
"Key": "Value"
}
}
Constraint 4 "An array only consists of JSON objects. It cannot contain a "key":"value" pair
by itself." not followed here, so it's a invalid pattern, hence prints -1

Problem : The Mystery of Sky

Statement

Stark is a 10 year old kid and he loves stars. So, he decided every day he will capture a
picture of a sky. After doing this for many days he found very interesting observations.

Every day the total number of stars in the sky is same as days completed for a calendar
year. He noticed, on Saturday's and Sunday's that there are no stars in the sky. Stark's
camera does not have wide angle capture feature so he could only capture maximum of
50 stars at a time. So, he assumed that there are only 50 stars in the sky that day. Also, the
camera discharges every 4th day and he is not be able to click any picture that day. So let's
say, if the first day of calendar (01/01/0001) starts on a Monday then on Thursday he can't
click any pictures. Then resuming on Friday he can take pictures until Sunday, but can't
take picture on Monday, followed by downtime on Friday, then Tuesday, then Saturday
etc. When the camera discharges he considers 0 stars that day.

You are his programmer friend and want to help him. You need to write a code which will
tell him on a particular date how many stars Stark's camera was able to click.

You can assume Stark has an ancient camera and your first input will be the day for date
(01/01/0001) and then followed by any date on which Stark wants to find out the number
of stars in the sky.
Input Format:

Every line of input will contain a Day at date 01/01/0001 in dd/mm/yyyy format followed
by a Date in the same format (on which we have to count the stars)
Output Format:
For valid Input
Count of the number of stars in the sky on the given date

For Invalid Input

Print "Invalid Date" for invalid date

Print "Invalid Day" for invalid day

Sample Input and Output

SNo. Input Output Explanation

1 Monday
Invalid Date
30/02/1990
2
Thursday Invalid Day
 Its 24th day of the year and neither is
3 Wednesday
24 Saturday/Sunday nor has the camera discharged
24/01/2056
on this day.

Problem : Collecting Candies

Statement

Krishna loves candies a lot, so whenever he gets them, he stores them so that he can eat
them later whenever he wants to.

He has recently received N boxes of candies each containing Ci candies where Ci

represents the total number of candies in the ith box. Krishna wants to store them in a
single box. The only constraint is that he can choose any two boxes and store their joint
contents in an empty box only. Assume that there are infinite number of empty boxes
available.

At a time he can pick up any two boxes for transferring and if both the boxes say contain X
and Y number of candies respectively, then it takes him exactly X+Y seconds of time. As he
is to eager to collect all of them he has approached you to tell him the minimum time in
which all the candies can be collected.

Input Format:

1. First line of input is number of test case T

2. Each test case is comprised of two inputs
a. First input of a test case is the number of boxes N
b. Second input is N integers delimited by whitespace denoting number
of candies in each box

Output Format:

Print minimum time required, in seconds, for each of the test case. Print each output on a
new line.

Constraints:

1. 1 ≤T≤10
2. 1 ≤N≤ 10000
3. 1 ≤ [Candies in each box] ≤ 100009

Sample Input and Output

SNo. Input Output Explanation

1 1 19 4 boxes, each containing 1, 2, 3 and 4 candies
4 respectively.
1234 Adding 1 + 2 in a new box takes 3 seconds
Adding 3 + 3 in a new box takes 6 seconds
Adding 4 + 6 in a new box takes 10 seconds
Hence total time taken is 19 seconds. There could
be other combinations also, but overall time does
not go below 19 seconds.

5 boxes, each containing 1, 2, 3, 4 and 5 candies

respectively.
Adding 1 + 2 in a new box takes 3 seconds
1 Adding 3 + 3 in a new box takes 6 seconds
2 5 33 Adding 4 + 5 in a new box takes 9 seconds
12345 Adding 6 + 9 in a new box takes 15 seconds
Hence total time taken is 33 seconds. There could
be other combinations also, but overall time does
not go below 33 seconds.

Problem : The Vita Sum

Statement

Tom the cat is brushing up his Math skills. He has a bag containing N balls of different
colors. Now Tom can randomly pick any even number of balls from the bag. Tom wants to
find out the sum of all such combinations of balls that he can pull out from the bag. He can
pull out at max K balls in one pick.
Input Format:

First line contains two space separated numbers N and K

Output Format:

The output is the sum of all the combinations of balls he can pull out modulo 10^9+7 i.e.
(1000000007)
Constraints:
1. 0<=N,k<=10^14
2. N >= k

Sample Input and Output

SNo. Input Output Explanation

1 44 8 We need 4C0 + 4C2+ 4C4= 1+6+1=8

2 83 29 We need 8C0 + 8C2= 1+28=29

 Problem : Games of Marbles
Statement

Darrell and Sally are two best friends. They had a large collection of marbles. They devised
a game with it to play in their free time which will also help them to improve their math.
One of them will have to select a certain number of marbles and give a hint to find the
number. The other will have to guess the first number that matches the given criteria and
vice versa.

Your task is to act as a judge for this game. When the player finds the answer, you will
have to verify the answer. If answer is right, add 10 points to that player. If the player
passes the question, you will have to give the right answer (no change in points in this
case). You should also announce the winner at the end of the game.

Hint to find the number:

When the marbles are put into a group of x1, x2, x3,...(where x1, x2, x3 can be any number
from 1 to 100), it falls into a perfect group.(No marble is left without a group).

Example: - When Darrell says the number falls into a perfect set when she groups them
into sets of 3 and 5, the answer could be 15 or 30 and so on. Since the first number that
matches the criteria is 15, 15 will be the answer.(Explanation: when 15 marbles is put into
groups of 3, We will get 5 sets of 3 marbles each and when it is put into groups of 5, we
will get 3 sets of 5 marbles each. For 16 marbles, we will get 5 sets of 3 marbles each and
one marble will be left without a proper group. So 16 cannot be the answer)

NOTE: - Please have a look at Sample Input and Output before you read the Input and
Output specification
Input Format:

The input will contain

1. Number of input lines N adhering to the following specification
a. Lines will be of two types either a Question Posing line or Answer
Giving line
b. Question posing line has to appear before any answer giving line
c. Question Posing line starts with Player Name and Answer Giving line
starts with 'A'
2. Second line will be a Question posing line whose format is where Perfect
Sets are depicted in the format <X 1
,X2,...Xn> where 2<=n<=7 and 1<=X n<=100

3. Third line must be an Answer Giving line which is the answer to the
precedingQuestion Posing line. The format of the Answer Giving line is as follows :
a. answer above can only be an integer number OR it will be a constant
string "PASS"
b. An integer number represents the value of the answer given by the
Player
c. If the Player does not know the answer she will "PASS" the question
4. Fourth line onwards, if they exist, will be alternating series of Question
Posing and Answer Giving lines in case of Valid inputs
5. In case of any Invalid Question Posing line, requisite output must be printed
for all previous Valid Question posing line(s).
6. Processing should stop at Invalid input line after printing required message
in output. See output specifications and sample test cases to understand points 5)
and 6) better

Output Format:
1. First line of output must reiterate the question in the following
format < Player Name >'s question is : X 1,X2,X3...,Xn>

7. Second line should be an evaluation of the first Answer Giving line of the
input. The evaluation message will either be { Correct Answer or Wrong Answer}
8. If the answer
. is correct, output, : 10points
a. is wrong, output, : 0points
b. is "PASS"-ed by the player,
i.output "Question is PASSed"
ii.output "Answer is: " where correct_answer_value is the correct
answer for the question passed by the player.
 iii.output ": 0points"
c. Overall points collected by players have to be tracked and output
when all valid inputs are processed
9. If all inputs are valid, after processing all the inputs, the final output should
be comprised of the following 4 lines
. Output "Total Points:" on fourth last line
a. Output ": points" on 3rd last line, where Player1 is the one who first
posed the question
b. Output ": points" on 2nd last line, where Player2 is the one who first
answered the question
c. If there is a winner Output "Game Result: is winner" or "Game
Result: Draw"
10. Print "Invalid Input" in case of invalid input or failing constraint

Constraints:
0. 0 < N <= 10
1. Player Names are Case-sensitive
2. Number of inputs in a Question posing line will be 2<=n<=7 and
1<=Xn<=100
3. <X1 ,X2,X3...,Xn> can only be integers

Sample Input and Output

SNo. Input Output

Sally's question is: 3,5

Correct Answer
Darrell: 10points
4
Darrell's question is: 4,8
Sally 3,5
Correct Answer
1 A Darrell 15
Sally: 10points
Darrell 4,8
Total Points:
A Sally 8
Sally: 10points
Darrell: 10points
Game Result: Draw

Darrell's question is: 5,6

4
Correct Answer
Darrell 5,6
Sally: 10points
2 A Sally 30
Sally's question is: 3,5
Sally 3,5
Question is PASSed
A Darrell PASS
Answer is: 15
 Darrell: 0points
Total Points:
Darrell: 0points
Sally: 10points
Game Result: Sally is winner

2
3 Darrell Invalid Input
A Sally 15

4
Sally's question is: 3,5
Sally 3,5
Correct Answer
4 A Darrell 15
Darrell: 10points
Darrell
Invalid Input
A Sally 15

Sally's question is: 3,5

Wrong Answer
2 Darrell: 0points
5 Sally 3,5 Total Points:
A Darrell 3 Sally: 0points
Darrell: 0points
Game Result: Draw

Sally's question is: 3,5,15

Correct Answer
2 Darrell: 10points
6 Sally 3,5,15 Total Points:
A Darrell 15 Sally: 0points
Darrell: 10points
Game Result: Darrell is winner