Word in string challenge

Problem statement
We say that a string, s, contains the word hackerrank if a subsequence of the characters in s spell the word hackerrank. For example, haacckkerrannkk does contain hackerrank, but haacckkerannk does not (the characters all appear in the same order, but it’s missing a second r).

More formally, let p_0, p_1, \dots, p_9 be the respective indices of h, a, c, k, e, r, r, a, n, k in string s. If p_0 \textless p_1, \textless p_2 \dots \textless p_9 is true, then s contains hackerrank.

You must answer q queries, where each query i consists of a string, s_i. For each query, print YES on a new line if s_i contains hackerrank; otherwise, print NO instead.

Input Format
The first line contains an integer denoting q (the number of queries).
Each line i of the q subsequent lines contains a single string denoting s_i.

Output Format
For each query, print YES on a new line if s_i contains hackerrank; otherwise, print NO instead.

Sample Input 0

Sample Output 0

Solution

 

Recursive Digit Sum challenge

Problem statement
We define super digit of an integer x using the following rules:

  • If x has only 1 digit, then its super digit is x.
  • Otherwise, the super digit of x is equal to the super digit of the digit-sum of x. Here, digit-sum of a number is defined as the sum of its digits.

For example, super digit of 9875 will be calculated as:

You are given two numbers n and k. You have to calculate the super digit of P.

P is created when number n is concatenated k times. That is, if n = 123 and k = 3, then P=123123123.

Input Format
The first line contains two space separated integers, n and k.

Constraints
1 \le n \textless 10^{100000}
1 \le k \le 10^{5}

Output Format
Output the super digit of P, where P is created as described above.

Sample Input 0

Sample Output 0

Explanation 0
Here n=148 and k=3, so P=148148148.

Sample Input 1
recursive-digit-sum-input-1

Sample Output 1
recursive-digit-sum-output-1

Solution

 

Crossword Puzzle challenge

Problem statement
A 10 \times 10 Crossword grid is provided to you, along with a set of words (or names of places) which need to be filled into the grid. The cells in the grid are initially, either + signs or - signs. Cells marked with a + have to be left as they are. Cells marked with a - need to be filled up with an appropriate character.

Input Format
The input contains 10 lines, each with 10 characters (which will be either + or - signs).
After this follows a set of words (typically nouns and names of places), separated by semi-colons (;).

Constraints
There will be no more than ten words. Words will only be composed of upper-case A-Z characters. There will be no punctuation (hyphen, dot, etc.) in the words.

Output Format
Position the words appropriately in the 10 \times 10 grid, and then display the 10 \times 10 grid as the output. So, your output will consist of 10 lines with 10 characters each.

Sample Input 0

Sample Output 0

Sample Input 1

Sample Output 1

Solution

 

Password Cracker challenge

Problem statement
There are N users registered on a website CuteKittens.com. Each of them have a unique password represented by pass[1], pass[2], \dots, pass[N]. As this a very lovely site, many people want to access those awesomely cute pics of the kittens. But the adamant admin don’t want this site to be available for general public. So only those people with passwords can access it.

Yu being an awesome hacker finds a loophole in their password verification system. A string which is concatenation of one or more passwords, in any order, is also accepted by the password verification system. Any password can appear 0 or more times in that string. He has access to each of the N passwords, and also have a string loginAttempt, he has to tell whether this string be accepted by the password verification system of the website.

For example, if there are 3 users with password {abra, ka, dabra}, then some of the valid combinations are abra (pass[1]), kaabra (pass[2]+pass[1]), kadabraka (pass[2]+pass[3]+pass[2]), kadabraabra (pass[2]+pass[3]+pass[1]) and so on.

Input Format
First line contains an integer T, the total number of test cases. Then T test cases follow.
First line of each test case contains N, the number of users with passwords. Second line contains N space separated strings, pass[1] pass[2] \dots pass[N], representing the passwords of each user. Third line contains a string, loginAttempt, for which Yu has to tell whether it will be accepted or not.

Constraints
1 \le T \le 10
1 \le N \le 10
pass[i] \ne pass[j], 1 \le i \textless j \le N
1 \le length(pass[i]) \le 10, where\ i \in \left[1,N\right]
1 \le length(loginAttempt) \le 2000
loginAttempt and pass[i] contains only lowercase latin characters (‘a’-‘z’).

Output Format
For each valid string, Yu has to print the actual order of passwords, separated by space, whose concatenation results into loginAttempt. If there are multiple solutions, print any of them. If loginAttempt can’t be accepted by the password verification system, then print WRONG PASSWORD.

Sample Input 0

Sample Output 0

Explanation 0
Sample Case #00: wedowhatwemustbecausewecan is the concatenation of passwords {we, do, what, we, must, because, we, can}. That is

Note that any password can repeat any number of times.

Sample Case #01: We can’t create string helloworld using the strings {hello",planet`}.

Sample Case #02: There are two ways to create loginAttempt (abcd). Both pass[2] = "abcd" and pass[1] + pass[3] = "ab cd" are valid answers.

Sample Input 1

Sample Output 1

Solution
We can solve this problem recursively and use memoization to avoid running out of time. The basic algorithm goes as follows:
– Iterate over all indices i of loginAttempt:
– Split loginAttempt into two parts left = loginAttempt.substring(0,i) and right = loginAttempt.substring(i).
– Call isValid(left) and isValid(right).
– If both calls return true, then loginAttempt is valid.

Full code

 

Cipher challenge

Problem statement
Jack and Daniel are friends. They want to encrypt their conversation so that they can save themselves from interception by a detective agency. So they invent a new cipher. Every message is encoded to its binary representation B of length N. Then it is written down K times, shifted by 0,1,\dots, K-1 bits.
If B=1001010 and K=4 it looks so:

Then calculate XOR in every column and write it down. This number is called S. For example, XOR-ing the numbers in the above example results in

Then the encoded message S and K are sent to Daniel.

Jack is using this encoding algorithm and asks Daniel to implement a decoding algorithm.
Can you help Daniel implement this?

Input Format
The first line contains two integers N and K.
The second line contains string S of length N+K+1 consisting of ones and zeros.

Output Format
Decoded message of length N, consisting of ones and zeros.

Constraints
1 \le N \le N^{6}
1 \le K \le N^{6}
|S| = N + K - 1
It is guaranteed that S is correct.

Sample Input#00

Sample Output#00

Sample Input#01

Sample Output#01

Explanation
Input#00

Input#01

Solution

 

Sansa and XOR

Problem statement
Sansa has an array. She wants to find the value obtained by XOR-ing the contiguous subarrays, followed by XOR-ing the values thus obtained. Can you help her in this task?

Note: \left[5,7,5\right] is contiguous subarray of \left[4,5,7,5\right] while \left[4,7,5\right] is not.

Input Format
First line contains an integer T, number of the test cases.
The first line of each test case contains an integer n, number of elements in the array.
The second line of each test case contains n integers that are elements of the array.

Constraints
1 \le T \le 5
2 \le n \le 10^{5}
1 \le numbers\ in\ array \le 10^{8}

Output Format
Print the answer corresponding to each test case in a separate line.

Sample Input

Sample Output

Explanation
Test case #00:
 1 \oplus 2 \oplus 3 \oplus (1 \oplus 2) \oplus (2 \oplus 3) \oplus (1 \oplus 2 \oplus 3) = 2

Test case #01:
 4 \oplus 5 \oplus 7 \oplus 5 \oplus (4 \oplus 5) \oplus (5 \oplus 7) \oplus (7 \oplus 5) \oplus (4 \oplus 5 \oplus 7) \oplus (5 \oplus 7 \oplus 5) \oplus (4 \oplus 5 \oplus 7 \oplus 5) = 0

Solution
We will solve our problem based on the fact whether n is even or odd.

n is even
First we will consider the case when n is even. For each x in the array we know that it appears 1 times by its own and n-1 times with the other numbers in the array during the XOR equation (see explanation above). Consider for example the following array:

\left[4, 5, 7, 5\right]

We will consider the two 5‘s as different. So we just rewrite the array as follows:

\left[4, 5, 7, 5^{*}\right]

Then, 4 will appear once by its own and n-1 times within the other subarrays: 4 \oplus (4 \oplus 5) \oplus (4 \oplus 5 \oplus 7) \oplus (4 \oplus 5 \oplus 7 \oplus 5^{*}).

Similarly for 5. It will appear once by its own and n-1 times within the other subarrays: (4 \oplus 5) \oplus 5 \oplus (5 \oplus 7) \oplus (5 \oplus 7 \oplus 5^{*}).

7 will also appear once by its own and n-1 times within the other subarrays: (4 \oplus 5 \oplus 7) \oplus (5 \oplus 7) \oplus 7 \oplus (7 \oplus 5^{*}).

5^{*} will also appear once by its own and n-1 times within the other subarrays:  (4 \oplus 5 \oplus 7 \oplus 5^{*}) \oplus (5 \oplus 7 \oplus 5^{*}) \oplus (7 \oplus 5^{*}) \oplus 5^{*}.

Since n is even and every integer 4, 5, 7 and 5^{*} appears even times in the XOR equation, the end result of the equation will be 0 when n is even. This can be easily seen by rearranging the XOR equation:

 4 \oplus 5 \oplus 7 \oplus 5^{*} \oplus (4 \oplus 5) \oplus (5 \oplus 7) \oplus (7 \oplus 5^{*}) \oplus (4 \oplus 5 \oplus 7) \oplus (5 \oplus 7 \oplus 5^{*}) \oplus (4 \oplus 5 \oplus 7 \oplus 5^{*}) = (4 \oplus 4 \oplus 4 \oplus 4) \oplus (5 \oplus 5 \oplus 5 \oplus 5) \oplus (7  \oplus 7 \oplus 7 \oplus 7)  \oplus (5^{*}\oplus 5^{*}\oplus 5^{*}\oplus 5^{*}) = 0 \oplus 0 \oplus 0 \oplus 0 = 0

n is odd
For the case when n is odd consider the array \left[1, 2, 3\right].
Then, 1 will appear once by its own and n-1 times within the other subarrays: 1 \oplus (1 \oplus 2) \oplus (1 \oplus 2 \oplus 3).

2 which is located at index i will appear i times with items to its left, once alone, (n-1)-i times with items to its right and once together with all items: (1 \oplus 2) \oplus 2 \oplus (2 \oplus 3) \oplus (1 \oplus 2 \oplus 3). Altogether a total of i + 1 + ((n-1)-i) + 1 = n+1 which is an even number of times. An integer that is XORed with its self an even number of times results in 0.

3 will appear once by its own and n-1 times within the other subarrays: (1 \oplus 2 \oplus 3) \oplus (2 \oplus 3) \oplus 3.

In summary for the case that n is odd we only need to XOR items at indices 0, 2, 4, 6, \dots since the elements at those indices appear an odd number of times. XORing an element with its self an odd number of times, results in that same number.

This can be easily seen by rearranging the XOR equation:

 1 \oplus 2 \oplus 3 \oplus (1 \oplus 2) \oplus (2 \oplus 3) \oplus (1 \oplus 2 \oplus 3) = (1 \oplus 1 \oplus 1) \oplus (2 \oplus 2 \oplus 2 \oplus 2) \oplus (3  \oplus 3 \oplus 3) = 1 \oplus 0 \oplus 3 = 2

Full code

 

Sum vs XOR

Problem Statement
Given an integer, n, find each x such that:

0 \le x \le n
n + x = n \oplus x

where \oplus denotes the bitwise XOR operator. Then print an integer denoting the total number of x‘s satisfying the criteria above.

Input Format
A single integer, n.

Constraints
0 \le n \le 10^{15}

Output Format
Print the total number of integer x‘s satisfying both of the conditions specified above.

Sample Input

Sample Output

Explanation

For n=5, the x values 0 and 2 satisfy the conditions:

5 + 0 = 5 \oplus 0 = 5
5 + 2 = 5 \oplus 2 = 7

Thus, we print 2 as our answer.

Solution

 

Simplified chess engine

Chess is a very popular game played by hundreds of millions of people. Nowadays, we have chess engines such as Stockfish and Komodo to help us analyze games. These engines are very powerful pieces of well-developed software that use intelligent ideas and algorithms to analyze positions and sequences of moves, as well as find tactical ideas. Consider the following simplified version of chess:

  • Board: It’s played on a 4 \times 4 board between two players named Black and White.

  • Pieces and Movement:

    • White initially has w pieces and Black initially has b pieces.
    • There are no Kings and no Pawns on the board. Each player has exactly one Queen, at most two Rooks, and at most two minor pieces (i.e., a Bishop and/or Knight).
    • Each piece’s possible moves are the same as in classical chess, and each move made by any player counts as a single move.
    • There is no draw when positions are repeated as there is in classical chess.
  • Objective: The goal of the game is to capture the opponent’s Queen without losing your own.

Given m and the layout of pieces for g games of simplified chess, implement a very basic (in comparison to the real ones) engine for our simplified version of chess with the ability to determine whether or not White can win in \le m moves (regardless of how Black plays) if White always moves first. For each game, print YES on a new line if White can win under the specified conditions; otherwise, print NO.

Input Format
The first line contains a single integer, g, denoting the number of simplified chess games. The subsequent lines define each game in the following format:

  • The first line contains three space-separated integers denoting the respective values of w (the number of White pieces), b (the number of Black pieces), and m (the maximum number of moves we want to know if White can win in).

  • The w + b subsequent lines describe each chesspiece in the format t c r, where t is a character \in \{Q,N,B,R\} denoting the type of piece (where Q is Queen, N is Knight, B is Bishop, and R is Rook), andc and r denote the respective column and row on the board where the figure is placed (where c \in \{A,B,C,D\} and r \in \{1,2,3,4\}). These inputs are given as follows:

  • Each of the w subsequent lines denotes the type and location of a White piece on the board.
  • Each of the b subsequent lines denotes the type and location of a Black piece on the board.

Constraints
It is guaranteed that the locations of all pieces given as input are distinct.
1 \le g \le 200
1 \le w,b \le 5
1 \le m \le 6
Each player initially has exactly one Queen, at most two Rooks and at most two minor pieces.

Output Format
For each of the g games of simplified chess, print whether or not White can win in \le m moves on a new line. If it’s possible, print YES; otherwise, print NO.

Sample Input 0

Sample Output 0

Explanation 0
We play g=1 games of simplified chess, where the initial piece layout is as follows:

White is the next to move, and they can win the game in 1 move by taking their Knight to A4 and capturing Black’s Queen. Because it took 1 move to win and 1 \le m, we print YES on a new line.

Additional Sample Input
input 1 expected output 1
input 2 expected output 2

Solution
Just to have an overview of the how the different chess pieces move, I have listed the moves below for quick reference:

Queen Knight Bishop Rook

Next, we need to figure out a strategy. Since the goal of the game is to capture the opponent’s Queen without losing your own a player can (1) avoid moves that put his Queen in jeopardy and (2) make a move that takes his Queen out of danger if the Queen happens to be in danger.

We are going to solve this problem using recursion. At this point it is worth noting the fact that depending on what player’s turn it is, a winning board has a different outcome depending on the current player. This will be important when handling return values from our recursive function calls. More on that later.

The board will internally be represented using an int[][] board array of size 4 \times 4. We also need to distinguish the White player pieces from the Black player pieces. I will use odd numbers for the pieces belonging to the White player and even numbers for the pieces belonging to the Black player:

Next, we are going to store all possible movement directions for each piece in a dedicated array:

Wer are going to also define some helper functions that will help us determine if a given row and column are within board limits and if a movement to a given square is valid:

The player parameter in the isValid(...) valid function takes two possible values: 1 when we are calling isValid(...) for the White player and 0 when we are calling isValid(...) for the Black player. isValid(...) returns true if we are within board limits and the square we are planning to move is not occupied by one of our own pieces. It return false otherwise.

Next, we are going to define helper functions, that we can call for a given board to determine if White or Black have won the game. That is, if the opponent does not have a Queen on the board:

player takes two possible values: 1 when we are calling isWinForPlayer(...) for the White player and 0 when we are calling isWinForPlayer(...) for the Black player. It returns true if the player wins and false otherwise.

We also define a function that returns the position of a player’s Queen on the board:

Next, we need a function that lets us know if the Queen of a player is safe in a given board:

Note above that for Queen, Bishop and Rook we take the movement directions and try them out for lengths 1\dots 4. This is not the case for a Knight (see Knight movement illustration above) where the movement does not have a variable length. Also notice for Queen, Bishop and Rook, if any piece is in the way we do not need to check the positions beyond that square since it blocks any opponent’s piece beyond that point.

Now that we have implemented our helper functions we can proceed with the actual algorithm. We are going to solve this by calling our main function canWhiteWin(int[][] board, int m, int player) recursively. Our exit conditions will be reaching the limit of our allowed number of moves, reaching a state where White wins or reaching a state where Black wins:

canWhiteWin(...) is called for every possible positions the player can move a piece and for all the player’s pieces on the board. A player recursively calls canWhiteWin(...) only for valid positions and if his Queen is safe in the resulting board. canWhiteWin(...) returns true if White player can win and false otherwise. We need to handle the result after every recursive function call differently depending on the current player. If the current player who called canWhiteWin(...) is White and the resulting value is true we do not need to examine any further positions. We exit by returning true, since White has found a move from the current board state that guaranties a win, no matter how Black plays next. If the current player who called canWhiteWin(...) is Black and the resulting value is false, we exit by returning false since from the current board state Black can make a move that results in White losing.

For Queen, Bishop and Rook we take the movement directions and try them out for lengths 1\dots 4. This is not the case for a Knight (see Knight movement illustration above) where the movement does not have a variable length. Also notice for Queen, Bishop and Rook, if any piece is in the way we do not need to check the positions beyond that square since it blocks the route to a square beyond that point.

Finally, if White cannot make a move, because his Queen would not be safe we return false. If a Black cannot make a move and m>1 we return true since black will be forced to make a move that puts his Queen at risk, which White can take in his next move.

That’s it! The full algorithm is listed below.

Full code

 

3Sum closest challenge

Problem statement
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Sample Input

Sample Output

Solution

 

Summary ranges challenge

Problem statement
Given a sorted integer array without duplicates, return the summary of its ranges for consecutive numbers.

For example, given [0,1,2,4,5,7], return [0\rightarrow 2,4\rightarrow 5,7].

Solution