Separate the numbers challenge

Problem statement
A numeric string, s, is beautiful if it can be split into a sequence of two or more positive integers, 1_1, a_2, \dots, a_n, satisfying the following conditions:

  1. a_i - a_{i-1} = 1 for any 1 \textless i \le n (i.e., each element in the sequence is 1 more than the previous element).
  2. No a_i contains a leading zero. For example, we can split s=10203 into the sequence \left[1, 02, 03\right], but it is not beautiful because 02 and 03 have leading zeroes.
  3. The contents of the sequence cannot be rearranged. For example, we can split s=312 into the sequence \left[3, 1, 2\right], but it is not beautiful because it breaks our first constraint (i.e., 1 - 3 \ne 1).

The diagram below depicts some beautiful strings:

You must perform q queries, where each query consists of some string s. For each query, print whether or not the string is beautiful on a new line. If it’s beautiful, print YES x, where x is the first number of the increasing sequence (if there are multiple such values of x, choose the smallest); otherwise, print NO instead.

Input Format
The first line contains an integer denoting (the number of strings to evaluate).
Each of the subsequent lines contains some string for a query.

Constraints
1 \le q \le 10
1 \le |s| \le 32
Each character in s is a decimal digit from 0 to 9 (inclusive).

Output Format
For each query, print its answer on a new line (i.e., either YES x where x is the smallest first number of the increasing sequence, or NO).

Sample Input 0

Sample Output 0

Explanation 0
The first three numbers are beautiful (see the diagram above). The remaining numbers are not beautiful:

For s = 101103, all possible splits violate the first and/or second conditions.
For s = 010203, it starts with a zero so all possible splits violate the second condition.
For s = 13, the only possible split is \left[1,3\right], which violates the first condition.
For s = 1, there are no possible splits because s only has one digit.

Solution

 

An interesting game challenge

Problem statement
Andy loves playing games. He wants to play a game with his little brother, Bob, using an array, A, of n distinct integers. The rules are as follows:

  • Bob always plays first and the two players move in alternating turns.
  • In a single move, a player chooses the maximum element currently present in the array and removes it as well as all the other elements to its right. For example, if A = \left[2,3,5,4,1\right], then it becomes A = \left[2,3\right] after the first move because we remove the maximum element (i.e., 5) and all elements to its right (i.e., 4 and 1).
  • The modifications made to the array during each turn are permanent, so the next player continues the game with the remaining array. The first player who is unable to make a move loses the game.

Andy and Bob play g games. Given the initial array for each game, can you find and print the name of the winner on a new line? If Andy wins, print ANDY; if Bob wins, print BOB.

Input Format
The first line contains a single integer denoting g (the number of games). The 2\times g subsequent lines describe each game array over two lines:

  1. The first line contains a single integer, n, denoting the number of elements in A.
  2. The second line contains n distinct space-separated integers describing the respective values of a_0, a_1, \dots, a_{n-1} for array A.

Constraints
Array contains n distinct integers.
1 \le g \le 100
1 \le n \le 10^5
1 \le a_i \le 10^9
The sum of n over all games does not exceed 10^5.

Output Format
For each game, print the name of the winner on a new line (i.e., either BOB or ANDY).

Sample Input 0

Sample Output 0

Explanation 0
Andy and Bob play the following two games:

1.
Initially, the array looks like this:

In the first move, Bob removes 6 and all the elements to its right, resulting in A = \left[5,2\right]:

In the second move, Andy removes 5 and all the elements to its right, resulting in A = \left[\right]:

At this point, the array is empty and Bob cannot make any more moves. This means Andy wins, so we print ANDY on a new line.

2.
In the first move, Bob removes 3 and all the elements to its right, resulting in A = \left[\right]. As there are no elements left in the array for Andy to make a move, Bob wins and we print BOB on a new line.

Solution

 

Gena playing Hanoi challenge

Problem statement
The Tower of Hanoi is a famous game consisting of 3 rods and a number of discs of incrementally different diameters. The puzzle starts with the discs neatly stacked on one rod, ordered by ascending size with the smallest disc at the top. The game’s objective is to move the entire stack to another rod, obeying the following rules:

  1. Only one disc can be moved at a time.
  2. Each move consists of taking the topmost disc from a stack and moving it to the top of another stack.
  3. No disc may be placed on top of a smaller disc.

Gena has a modified version of the Tower of Hanoi. His Hanoi has 4 rods and N discs ordered by ascending size. He made a few moves (following the rules above), but stopped and lost his place. He wants to restore the tower to its original state by making valid moves. Given the state of Gena’s Hanoi, help him calculate the minimum number of moves needed to restore the tower to its original state.

Note: Gena’s rods are numbered from 1 to 4. All discs are initially located on rod 1.

Input Format
The first line contains a single integer, N, denoting the number of discs.
The second line contains N space-separated integers, where the i^{th} integer is the index of the rod where the disk with diameter i is located.

Constraints
1 \le N \le 10

Output Format
Print the minimum number of moves Gena must make to restore the tower to its initial, ordered state on the first rod.

Sample Input

Sample Output

Explanation
3 moves are enough to build the tower. Here is one possible solution:

Solution
We will use BFS to solve this challenge. We will use a helper array minForTower with minForTower[i] holding the size of the smallest disc located at tower i. The validMovesFromState() method will compute and return a Set<Integer[]> of all valid directly subsequent moves that can be made from a given tower-disc allocation. We will store visited states in an array int[] visited = new int[(int) Math.pow(4, n)] using a key. The array length is 4^N since we can have a maximum of 4^N possible tower-disc allocations/states. Each state has an integer key. For example, given a state \left[1, 4, 1\right], a key is an integer representing that allocation. Bits 2i and 2i+1 of the key represent the tower (Tower 0 = 00_b, Tower 1 = 01_b, Tower 2 = 10_b, Tower 3 = 11_b). For \left[1, 4, 1\right] the key is 12 = 001100_b.

We then do a BFS putting the states in a queue along with the depth of the given state. The depth or number of steps it took us to get to that state is stored at index 0 of the state array. Each time we reach our goal state we check we update our minimum if necessary.

The full code is listed below.

Full code

 

The power sum challenge

Find the number of ways that a given integer, X, can be expressed as the sum of the N^{th} power of unique, natural numbers.

Input Format
The first line contains an integer X.
The second line contains an integer N.

Constraints
1 \le X \le 1000
2 \le N \le 10

Output Format
Output a single integer, the answer to the problem explained above.

Sample Input 0

Sample Output 0

Explanation 0
If X = 10 and N=2, we need to find the number of ways that 10 can be represented as the sum of squares of unique numbers.

10 = 1^2 + 3^2

This is the only way in which 10 can be expressed as the sum of unique squares.

Sample Input 1

Sample Output 1

Explanation 1
100 = 10^2 = 6^2 + 8^2 = 1^2 + 3^2 + 4^2 + 5^2 + 7^2

Sample Input 2

Sample Output 2

Solution

 

Minimum loss challenge

Problem statement
Lauren has a chart of distinct projected prices for a house over the next n years, where the price of the house in the i^{th} year is p_i. She wants to purchase and resell the house at a minimal loss according to the following rules:

The house cannot be sold at a price greater than or equal to the price it was purchased at (i.e., it must be resold at a loss). The house cannot be resold within the same year it was purchased. Find and print the minimum amount of money Lauren must lose if she buys the house and resells it within the next years.

Note: It’s guaranteed that a valid answer exists.

Input Format
The first line contains an integer, n, denoting the number of years of house data. The second line contains space-separated long integers describing the respective values of p_1, p_2,\dots, p_n.

Constraints
2\le n \le 2 \times 10^5 1 \le p_i \le 10^{16} All the prices are distinct. It’s guaranteed that a valid answer exists.

Output Format
Print a single integer denoting the minimum amount of money Lauren must lose if she buys and resells the house within the next n years.

Sample Input 0

Sample Output 0

Explanation 0
Lauren buys the house in year 1 at price p_1 = 5 and sells it in year 3 at p_3 = 3 for a minimal loss of 5 - 3 = 2.

Sample Input 1

Sample Output 1

Explanation 1
Lauren buys the house in year 2 at price p_2 = 7 and sells it in year 5 at p_5 = 5 for a minimal loss of 7 - 5 = 2.

Sample Input & Output 3
minimum-loss-input
minimum-loss-output

Solution
Naive approach
The naive approach is to iterate over each price p_i and compare it with all the subsequent prices, storing any new found minimum loss based on the two rules stated in the problem statement. This obviously has a running time of \mathcal{O}(n^2).

Binary Search Tree (BST) approach
We can construct a BST from the prices array. The construction has a running time of \mathcal{O}(nlogn). We then go through all the nodes. Starting at node x we traverse up (go to its parent) the BST as long as the current node is not a left child of its parent (or no parent is available). If the current node is a left child then we return the value of its parent. This value is the smallest value that is greater than the value of the original/starting node x. Searching the BST for every node has a total worst case running time of \mathcal{O}(nlogn).

Full code

 

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