hamidgasmi / training.computerscience.algorithms-datastructures Goto Github PK

Problem Introduction:
You have n ads to place on a popular Internet page.
For each ad, you know how much is the advertiser willing to pay for one click on this ad. You have set up n slots on your page and estimated the expected number of clicks per day for each slot.
Now, your goal is to distribute the ads among the slots to maximize the total revenue.

Problem Description
Task. Given two sequences:
A1 , . . . , An (Ai is the profit per click of the i-th ad) and
B1, . . . , Bn (Bi is the average number of clicks per day of the i-th slot).
We need to partition them into n pairs (Ai, Bj) such that the sum of their products is maximized.

Input Format.
The 1st line contains an integer n,
The 2nd one contains a sequence of integers A1, . . . , An
The 3rd one contains a sequence of integers B1, B2, . . . , Bn

Constraints.
1 ≤ n ≤ 10^3;
−10^5 ≤ Ai, Bi ≤ 10^5 for all 1 ≤ i ≤ n

Output Format.
Output the maximum value of the sum product

E.g. 1.
Input: 1
23
39
Output: 897 (897 = 23 · 39)

E.g., 2.
Input: 3
1 3 -5
-2 4 1
Output: 23 (23 = 3 · 4 + 1 · 1 + (−5) · (−2))

Tl and T2 are two very large binary trees, with Tl much bigger than T2. Create an algorithm to determine if T2 is a subtree of Tl.
A tree T2 is a subtree ofTi if there exists a node n in Ti such that the subtree of n is identical to T2.
That is, if you cut off the tree at node n, the two trees would be identical.

Cracking The Code Interview, pp. 111.

Given a positive integer, print the next smallest and the next largest number that have the same number of 1 bits in their binary representation.

Cracking The Code Interview, pp. 116.

Problem Introduction
Compute the length of a longest common subsequence of three sequences.

Problem Description
Task.
Given three sequences:
A = (A1,..., An),
B = (B1,..., Bm), and
C = (C1,..., Cl),
Find the length of their longest common subsequence,
i.e., the largest non-negative integer p such that there exist indices:
1 ≤ i1 < ··· < ip ≤ n,
1 ≤ j1 < ··· < jp ≤ m,
1 ≤ k1 < ··· < kp ≤ l such that
Ai1 = Bj1 = Ck1, ..., Aip = Bjp = Ckp

Input Format.
1st line: n.
2nd line: A1, ..., An
3rd line: m.
4th line: B1, ..., Bm
5th line: l
6th line: C1, ..., Cl

Constraints.
1 ≤ n, m, l ≤ 100;
−10^9 < Ai, Bi, Ci < 10^9

Output Format.
Output p

E.g. 1.
Input:
3
1 2 3
3
2 1 3
3
1 3 5
Output: 2 (A common subsequence of length 2 is (1, 3))

E.g. 2.
Input:
5
8 3 2 1 7
7
8 2 1 3 8 10 7
6
6 8 3 1 4 7
Output: 3 (1 common subsequence of length 3 in this case is (8, 3, 7). Another one is (8, 1, 7))

Implement a function to check if a binary tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that the heights of the two subtrees of any node never differ by more than one.

Cracking The Code Interview, pp. 110

Write a program to sort a stack such that the smallest items are on the top. You can use
an additional temporary stack, but you may not copy the elements into any other data structure
(such as an array). The stack supports the following operations: push, pop, peek, and isEmpty.

Cracking The Code Interview, pp. 99.

A binary search tree was created by traversing through an array from left to right and inserting each element.
Given a binary search tree with distinct elements, print all possible arrays that could have led to this tree.

EXAMPLE
Input:
2
/ \
1 3
Output: {2, 1, 3}, {2, 3, 1}

Cracking The Code Interview, pp. 110.

You are given two 32-bit numbers, N and M, and two bit positions, i and j.

Write a method to insert M into N such that M starts at bit j and ends at bit i.

You can assume that the bits j through i have enough space to fit all of M.
That is, if M = 10011, you can assume that there are at least 5 bits between j and i. You would not, for example, have j = 3 and i = 2, because M could not fully fit between bit 3 and bit 2.

EXAMPLE
Input:
N = 10000000000, M = 10011, i = 2, j = 6.
Output:
N = 10001001100.

Cracking The Code Interview, pp. 115.

An animal shelter, which holds only dogs and cats, operates on a strictly"first in, first
out" basis. People must adopt either the "oldest" (based on arrival time) of all animals at the shelter, or they can select whether they would prefer a dog or a cat (and will receive the oldest animal of that type).
They cannot select which specific animal they would like. Create the data structures to maintain this system and implement operations such as enqueue, dequeueAny, dequeueDog,
and dequeueCat.
You may use the built-in Linked List data structure.

Cracking The Code Interview, pp. 99.

Implement a function to check if a binary tree is a binary search tree.

Cracking The Code Interview, pp. 110

A monochrome screen is stored as a single array of bytes, allowing eight consecutive pixels to be stored in one byte.
The screen has width w, where w is divisible by 8 (that is, no byte will be split across rows).
The height of the screen, of course, can be derived from the length of the array and the width.

Implement a function that draws a horizontal line from (x1, y) to (x2, y).
The method signature should look something like:
drawLine(byte[] screen, int width, int x1, int x2, int y)

Cracking The Code Interview, pp. 116.

Write an algorithm to find the "next" node (i .e., in-order successor) of a given node in a
binary search tree. You may assume that each node has a link to its parent.

Cracking The Code Interview, pp. 110

Problem Introduction:
You are organizing a funny competition for children.
As a prize fund you have n candies.
You would like to use these candies for top k places in a competition with a natural restriction that a higher place gets a larger number of candies.
To make as many children happy as possible, you are going to find the largest value of k for which it is possible.

Problem Description
Task.
The goal of this problem is to represent a given positive integer n as a sum of as many pairwise distinct positive integers as possible.
To find the max k such that n can be written as:
A1 + · · · + Ak where A1, . . ., Ak are positive integers and
Ai != Aj for all 1 ≤ i < j ≤ k.

Input Format.
The input consists of a single integer n.

Constraints.
1 ≤ n ≤ 10^9

Output Format.
In the 1st line, output the maximum number k such that n can be represented as a sum of k pairwise distinct positive integers.
In the 2nd line, output k pairwise distinct positive integers
that sum up to n
If there are many such representations, output any of them.

E.g., 1.
Input: 6
Output:
3
1 2 3
E.g., 2.
Input: 8
Output:
3
1 2 5
E.g. 3.
Input: 2
Output:
1
2

Task. The goal in this problem is to find the minimum number of coins needed to change the input value
(an integer) into coins with denominations 1, 5, and 10.

Input Format. The input consists of a single integer m.

Constraints. 1 ≤ m ≤ 10^3 .

Output Format. Output the minimum number of coins with denominations 1, 5, 10 that changes m.

E.g. 1, Input: $2
Output: 2 (2 = 1 + 1)

E.g. 2, Input: $28
Output: 6 (28 = 10 + 10 + 5 + 1 + 1 + 1)

Task. The goal of this code problem is to implement an algorithm for the fractional knapsack problem.

Input Format.
The first line of the input contains the number n of items and the capacity W of a knapsack.
The next n lines define the values and weights of the items. The i-th line contains integers Vi and Wi —the value and the weight of i-th item, respectively.

Constraints.
1 ≤ n ≤ 10^3 , 0 ≤ W ≤ 2 · 10^6 ; 0 ≤ Vi ≤ 2 · 10^6 , 0 < Wi ≤ 2 · 10^6 for all 1 ≤ i ≤ n.
All the numbers are integers.

Output Format.
Output the maximal value of fractions of items that fit into the knapsack.
The absolute value of the difference between the answer of your program and the optimal value should be at most 10^−3 .
To ensure this, output your answer with at least four digits after the decimal point.

E.g. 1,
Input:
003 50
060 20
100 50
120 30
Output: 180.0000

E.g. 2,
Input:
001 10
500 30
Output: 166.6667

Problem Introduction
An inversion of a sequence A0,. . ., An−1 is a pair of indices
0 ≤ i < j < n such that Ai > Aj.
The number of inversions of a sequence in some sense measures how close the sequence is to being sorted.
E.g., a sorted (in non-descending order) sequence contains no inversions at all, while in a sequence sorted in descending order any two elements constitute an inversion (for a total of n(n − 1)/2 inversions).

Problem Description
Task.
The goal in this problem is to count the number of inversions of a given sequence.

Input Format.
The 1st line contains an integer n,
The 2nd contains a sequence of integers A0,..., An−1

Constraints.
1 ≤ n ≤ 10^5
1 ≤ Ai ≤ 10^9 for all 0 ≤ i < n

Output Format.
Output the number of inversions in the sequence.

E.g.,
Input:
5
2 3 9 2 9
Output: 2
The two inversions here are (1, 3) (A1 = 3 > 2 = A3 ) and (2, 3) (A2 = 9 > 2 = A3 ).

As we already know, a natural greedy strategy for the change problem does not work correctly for any set of denominations.
For example, if the available denominations are 1, 3, and 4, the greedy algorithm will change
6 cents using three coins (4 + 1 + 1) while it can be changed using just two coins (3 + 3). Your goal now is to apply dynamic programming for solving the Money Change Problem for denominations 1, 3, and 4.

Problem Description:
Input Format. Integer money.
Output Format. The minimum number of coins with denominations 1, 3, 4 that changes money.
Constraints. 1 ≤ money ≤ 10^3

E.g. 1,
Input: 2
Output: 2 (2 = 2 x 1).
E.g., 2.
Input: 34
Output: 9 (34 = 7 * 4 + 2 x 3).

Problem Introduction
In this problem, you will implement the binary search algorithm that allows searching very efficiently (even huge) lists, provided that the list is sorted.

Problem Description
Task.
The goal in this code problem is to implement the binary search algorithm.

Input Format.
The 1st line of the input contains an integer n and a sequence A0 < . . . < An-1 of n pairwise distinct positive integers in increasing order.
The 2nd line contains an integer k and k positive integers:
B0, . . . , Bk-1

Constraints.
1 ≤ n, k ≤ 10^4;
1 ≤ Ai ≤ 10^9 for all 0 ≤ i < n;
1 ≤ Bj ≤ 10^9 for all 0 ≤ j < k;

Output Format.
For all i from 0 to k − 1, output an index 0 ≤ j ≤ n − 1 such that Aj = Bi or −1 if there

E.g.,
Input:
5 1 5 8 12 13
5 8 1 23 1 11
Output:
2 0 -1 0 -1
In this sample, we are given an increasing sequence
A0 = 1, A1 = 5, A2 = 8, A3 = 12, A4 = 13 of length 5 and
5 keys to search: 8, 1, 23, 1, 11.
We see that A2 = 8 and A0 = 1, but the keys 23 and 11 do
not appear in the sequence A.
For this reason, we output a sequence 2, 0, −1, 0, −1. is no such index.

The problem statement is available here

Problem Introduction
You are given a set of bars of gold and your goal is to take as much gold as possible into your bag.
There is just one copy of each bar and for each bar you can either take it or not (hence you cannot take a fraction of a bar).

Problem Description
Task.
Given n gold bars, find the maximum weight of gold that fits into a bag of capacity W.

Input Format.
The 1st line of the input contains the capacity W of a knapsack and the number n of bars of gold.
The 2nd line contains n integers W0, ..., Wn−1 defining the weights of the bars of gold.

Constraints.
1 ≤ W ≤ 10^4;
1 ≤ n ≤ 300;
0 ≤ W0, ..., Wn−1 ≤ 10^5

Output Format.
Output the maximum weight of gold that fits into a knapsack of capacity W

E.g. 1,
Input:
10 3
148
Output: 9
Here, the sum of the weights of the first and the last bar is equal to 9.

Given a directed graph, design an algorithm to find out whether there is a route between two nodes.

Cracking The Code Interview, pp. 109.

You are given a list of projects and a list of dependencies (which is a list of pairs of projects, where the second project is dependent on the first project).
All of a project's dependencies must be built before the project is. Find a build order that will allow the projects to be built. If there is no valid build order, return an error.

EXAMPLE
Input:
projects: a, b, c, d, e, f
dependencies: (a, d), (f, b), (b, d), (f, a), (d, c)
Output: f, e, a, b, d, c

Cracking The Code Interview, pp. 110

Imagine a (literal) stack of plates. If the stack gets too high, it might topple.
Therefore, in real life, we would likely start a new stack when the previous stack exceeds some
threshold. Implement a data structure SetOfStacks that mimics this. SetOfStacks should be
composed of several stacks and should create a new stack once the previous one exceeds capacity.
SetOfStacks. push () and SetOfStacks. pop () should behave identically to a single stack
(that is, pop ( ) should return the same values as it would if there were just a single stack).

Cracking The Code Interview, pp. 98.

Problem Introduction
The edit distance between 2 strings is the minimum number of operations (insertions, deletions, and substitutions of symbols) to transform 1 string into another.
It is a measure of similarity of two strings.
Edit distance has applications, for example, in computational biology, natural language processing, and spell checking. Your goal in this problem is to compute the edit distance between two strings.

Problem Description
Task.
The goal of this problem is to implement the algorithm for computing the edit distance between 2 strings.

Input Format.
Each of the 2 lines of the input contains a string consisting of lower case latin letters.

Constraints.
The length of both strings is at least 1 and at most 100.

Output Format.
Output the edit distance between the given 2 strings.

E.g. 1.
Input:
ab
ab
Output: 0

E.g. 2.
Input:
short
ports
Output: 3
An alignment of total cost 3:
s h o r t −
− p o r t s

E.g. 3,
Input:
editing
distance
Output: 5
An alignment of total cost 5:
e d i − t i n g −
− d i s t a n c e

Problem Introduction
In this problem, your goal is to find the closest pair of points among the given n points.
This is a basic primitive in computational geometry having applications in, for example, graphics, computer vision, traffic-control systems.

Problem Description
Task.
Given n points on a plane, find the smallest distance between a pair of two (different) points.

Input Format.
The 1st line contains the number n of points. Each of the following n lines defines a point (Xi, Yi)

Constraints.
2 ≤ n ≤ 10^5
−10^9 ≤ Xi, Yi ≤ 10^9 are integers.

Output Format.
Output the minimum distance.
The absolute value of the difference between the answer
of your program and the optimal value should be at most 10^−3.
To ensure this, output your answer with at least four digits after the decimal point (otherwise your answer, while being computed correctly, can turn out to be wrong because of rounding issues).

E.g. 1.
Input:
2
0 0
3 4
Output:
5.0
There are only two points here. The distance between them is 5.

E.g. 2.
Input:
4
7 7
1 100
4 8
7 7
Output:
0.0
There are 2 coinciding points among the four given points. Thus, the minimum distance is zero.

Describe how you could use a single array to implement three stacks.

Cracking the code Interview, pp. 98.

FOLLOW UP
Implement a function popAt (int index) which performs a pop operation on a specific sub-stack.

Cracking The Code Interview, pp. 99.

Write a function to determine the number of bits you would need to flip to convert integer A to integer B.
EXAMPLE
Input: 29 (or: 11101), 15 (or: 01111)
Output: 2

Cracking The Code Interview, pp. 116.

Problem Introduction
You are given a primitive calculator that can perform the following 3 operations with the current number x: multiply x by 2, multiply x by 3, or add 1 to x.
Your goal is given a positive integer n, find the minimum number of operations needed to obtain the number n starting from the number 1.

Problem Description
Task.
Given an integer n, compute the minimum number of operations needed to obtain the number n
starting from the number 1.

Input Format.
The input consists of a single integer 1 ≤ n ≤ 10^6

Output Format.
In the 1st line, output the minimum number k of operations needed to get n from 1.
In the 2nd line output a sequence of intermediate numbers. That is, the 2nd line should contain positive integers A0,..., Ak−1 such that A0 = 1, Ak−1 = n and
for all 0 ≤ i < k − 1, Ai+1 is equal to either Ai+1, 2Ai, or 3Ai
If there are many such sequences, output any one of them.

E.g. 1,
Input: 1
Output:
0
1

E.g. 2,
Input: 5
Output:
3
1 2 4 5
Here, we first multiply 1 by 2 two times and then add 1. Another possibility is to first multiply by 3 and then add 1 two times. Hence “1 3 4 5” is also a valid output in this case.

E.g. 4,
Input: 96234
Output:
14
1 3 9 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234
Again, another valid output in this case is “1 3 9 10 11 33 99 297 891 2673 8019 16038 16039 48117 96234”.

Explain what the following code does:
((n & (n -1)) == 0) .

Cracking The Code Interview, pp. 116.

How would you design a stack which, in addition to push and pop, has a function min
which returns the minimum element? Push, pop and min should all operate in O(1) time.

Cracking The Code Interview, pp. 98.

Write a program to swap odd and even bits in an integer with as few instructions as possible
Example: bit 0 and bit 1 are swapped,
bit 2 and bit 3 are swapped, etc.

Cracking The Code Interview, pp. 116.

Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.

Cracking The Code Interview, pp. 110

Implement a MyQueue class which implements a queue using two stacks.

Cracking The Code Interview, pp. 99.

You are implementing a binary tree class from scratch which, in addition to insert, find, and delete, has a method getRandomNode() which returns a random node from the tree.
All nodes should be equally likely to be chosen.

Design and implement an algorithm for getRandomNode, and explain how you would implement the rest of the methods.

Cracking The Code Interview, pp. 111.

Given a real number between 0 and 1 (e.g., 0.72) that is passed in as a double, print the binary representation.
If the number cannot be represented accurately in binary with at most 32 characters, print "ERROR:'

Cracking The Code Interview, pp. 116.

You and two of your friends have just returned back home after visiting various countries.
Now you would like to evenly split all the souvenirs that all three of you bought.

Problem Description
Input Format.
The 1st line contains an integer n.
The 2nd line contains integers V1, ..., Vn separated by spaces.

Constraints.
1 ≤ n ≤ 20,
1 ≤ Vi ≤ 30 for all i.

Output Format.
Output 1, if it possible to partition V1,..., Vn into 3 subsets with equal sums, and 0 otherwise.

E.g. 1.
Input:
4
3 3 3 3
Output: 0

E.g. 2.
Input:
1
30
Output: 0

E.g. 3.
Input:
13
1 2 3 4 5 5 7 7 8 10 12 19 25
Output: 1
1 + 3 + 7 + 25 = 2 + 4 + 5 + 7 + 8 + 10 = 5 + 12 + 19.

Problem Introduction
Compute the length of a longest common subsequence of two sequences.

Problem Description
Task.
Given 2 sequences A = (A1, ..., An) and B = (B1, ..., Bm),
find the length of their longest common subsequence,
i.e., the largest non-negative integer p such that there exist indices 1 ≤ i1 < ··· < ip ≤ n and 1 ≤ j1 < ··· < jp ≤ m,
such that Ai1 = Bj1, ..., Aip = Bjp.

Input Format.
1st line: n.
2nd line: A1, A2, ..., An.
3rd line: m.
4th line: B1, B2, ..., Bm.

Constraints.
1 ≤ n, m ≤ 100;
−10^9 < Ai, Bi < 10^9

Output Format. Output p.

E.g. 1,
Input:
3
2 7 5
2
2 5
Output: 2
A common subsequence of length 2 is (2, 5).

E.g. 2,
Input:
1
7
4
1 2 3 4
Output: 0
The two sequences do not share elements.

E.g. 3,
Input:
4
2 7 8 3
4
5 2 8 7
Output: 2
One common subsequence is (2, 7).
Another one is (2, 8).

Given a sorted (increasing order) array with unique integer elements, write an algorithm
to create a binary search tree with minimal height.

Cracking The Code Interview, pp. 109

Problem Introduction:
Majority rule is a decision rule that selects the alternative which has a majority, that is, more than half the votes.
Given a sequence of elements A1, A2,..., An, you would like to check whether it contains an element that appears more than n/2 times.

Your goal is to use the divide-and-conquer technique to design an O(n log n) algorithm.

Problem Description
Task.
The goal in this code problem is to check whether an input sequence contains a majority element.
Input Format.
The 1st line contains an integer n,
The 2sd contains a sequence of n non-negative integers:
A0, A1,..., An−1
Constraints.
1 ≤ n ≤ 10^5
0 ≤ Ai ≤ 10^9 for all 0 ≤ i < n.

Output Format.
Output 1 if the sequence contains an element that appears strictly more than n/2 times, and 0 otherwise.

E.g. 1,
Input:
5
2 3 9 2 2
Output: 1 (2 is the majority element)

E.g. 2,
Input:
4
1 2 3 4
Output: 0 (There is no majority element in this sequence)

E.g. 3,
Input:
4
1 2 3 1
Output: 0 (This sequence doesn't have a majority element: the element 1 appears twice and hence is not a majority element).

You have an integer and you can flip exactly one bit from a 0 to a 1.
Write code to find the length of the longest sequence of 1s you could create.
EXAMPLE
Input: 1775 (or: 11011101111)
Output: 8

Cracking The Code Interview, pp. 116.

Problem Introduction
You are responsible for collecting signatures from all tenants of a certain building.
For each tenant, you know a period of time when he or she is at home.
You would like to collect all signatures by visiting the building as few times as possible.
The mathematical model for this problem is the following:
You are given a set of segments on a line and your goal is to mark as few points on a line as possible so that each segment contains at least one marked point.

Problem Description
Task.
Given a set of n segments {[A1 , B1],. . . , [An, Bn]} with integer coordinates on a line,
find the minimum number m of points such that each segment contains at least one point.
Find a set of integers X of the min size such that for any segment [Ai, Bi] there is a point x ∈ X such that Ai ≤ x ≤ Bi .

Input Format.
The 1st line of the input contains the number n of segments.
Each of the following n lines contains two integers Ai and Bi defining the coordinates of endpoints of the i-th segment.

Constraints.
1 ≤ n ≤ 100
0 ≤ Ai ≤ Bi ≤ 10^9 for all 0 ≤ i < n

Output Format.
Output the minimum number m of points on the first line and the integer coordinates of m points on the second line.
You can output the points in any order.
If there are many such sets of points, you can output any set. (It is not difficult to see that there always exist a set of points of the minimum size such that all the coordinates of the points are integers.)

E.g. 1,
Input:
3
1 3
2 5
3 6
Output:
1
3
We have three segments: [1, 3], [2, 5], [3, 6] (of length 2, 3, 3 respectively).
All of them contain the point with coordinate 3: 1 ≤ 3 ≤ 3, 2 ≤ 3 ≤ 5, 3 ≤ 3 ≤ 6.

E.g. 2,
Input:
4
4 7
1 3
2 5
5 6
Output:
2
3 6
The 2nd and the 3rd segments contain the point with coordinate 3 while the 1st and the 4th segments contain the point with coordinate 6.
All the 4 segments cannot be covered by a single
point, since the segments [1, 3] and [5, 6] are disjoint.

You are given a binary tree in which each node contains an integer value (which might be positive or negative).

Design an algorithm to count the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

Cracking The Code Interview, pp. 111.

Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth (e.g., if you have a tree with depth 0, you'll have 0 linked lists).

Cracking The Code Interview, pp. 109.

Problem Introduction.
The goal in this problem is to redesign a given implementation of the randomized quick sort algorithm so that it works fast even on sequences containing many equal elements.
Problem Description.
Task.
To force the given implementation of the quick sort algorithm to efficiently process sequences with few unique elements, your goal is replace a 2-way partition with a 3-way partition.
That is, your new partition procedure should partition the array into three parts: < x part, = x part, and > x part.

Input Format.
The 1st line of the input contains an integer n.
The 2nd line contains a n integers sequence: A0,...,An−1

*Constraints.
1 ≤ n ≤ 10^5;
1 ≤ Ai ≤ 10^9 for all 0 ≤ i < n

Output Format.
Output this sequence sorted in non-decreasing order

E.g. 1,
Input:
5
2 3 9 2 2
Output:
2 2 2 3 9

Problem Introduction.
As the last question of a successful interview, your boss gives you a few pieces of paper with numbers on it and asks you to compose a largest number from these numbers.
The resulting number is going to be your salary, so you are very much interested in maximizing
this number.
How can you do this?
In the lectures, we considered the following algorithm for composing the largest number out of the given single-digit numbers.

Problem Description
Task.
Compose the largest number out of a set of integers.

Input Format.
The 1st line of the input contains an integer n The 2nd line contains integers A1, . . . , An

Constraints.
1 ≤ n ≤ 100;
1 ≤ a i ≤ 10 3 for all 1 ≤ i ≤ n

**Output Format. **
Output the largest number that can be composed out of A1, . . . , An

E.g.1,
Input:
2
21 2
Output:
221

E.g.2,
Input:
5
9 4 6 1 9
Output:
99641

E.g. 3,
Input:
3
23 39 92
Output:
923923

Problem Introduction
You are organizing an online lottery.
To participate, a person bets on a single integer. You then draw several ranges of consecutive integers at random.
A participant’s payoff then is proportional to the number of ranges that contain the participant’s number minus the number of ranges that does not contain it.
You need an efficient algorithm for computing the payoffs for all participants.
A naive way to do this is to simply scan, for all participants, the list of all ranges.
However, your lottery is very popular: you have thousands
of participants and thousands of ranges.
For this reason, you cannot afford a slow naive algorithm.

Problem Description
Task.
You are given a set of points on a line and a set of segments on a line.
The goal is to compute, for each point, the number of segments that contain this point.

Input Format.
The 1st line contains two non-negative integers s and p defining the number of segments and the number of points on a line, respectively.
The next s lines contain two integers Ai, Bi defining the i-th segment [Ai, Bi ].
The next line contains p integers defining points X1,...,Xp

Constraints.
1 ≤ s, p ≤ 50000;
−10^8 ≤ Ai ≤ Bi ≤ 10^8 for all 0 ≤ i < s
−10^8 ≤ Xj ≤ 10^8 for all 0 ≤ j < p

Output Format.
Output p non-negative integers K0,..., Kp−1 where Ki is the number of segments which contain Xi
More formally, Ki = | { j: Aj ≤ Xi ≤ Bj } |

E.g.,
Input:
2 3
0 5
7 10
1 6 11
Output:
1 0 0
Here, we have two segments and three points. The first point lies only in the first segment while the remaining two points are outside of all the given segments.

E.g. 2,
Input:
1 3
-10 10
-100 100 0
Output:
0 0 1

E.g. 3.
Input:
3 2
0 5
-3 2
7 10
1 6
Output:
20

Given a chemical formula (given as a string), return the count of each atom.

An atomic element always starts with an uppercase character, then zero or more lowercase letters, representing the name.

1 or more digits representing the count of that element may follow if the count is greater than 1. If the count is 1, no digits will follow. For example, H2O and H2O2 are possible, but H1O2 is impossible.

Two formulas concatenated together produce another formula. For example, H2O2He3Mg4 is also a formula.

A formula placed in parentheses, and a count (optionally added) is also a formula. For example, (H2O2) and (H2O2)3 are formulas.

Given a formula, output the count of all elements as a string in the following form: the first name (in sorted order), followed by its count (if that count is more than 1), followed by the second name (in sorted order), followed by its count (if that count is more than 1), and so on.

Example 1:
Input: formula = "H2O"
Output: "H2O"

Example 2:
Input formula = "Mg(OH)2"
Output: "H2MgO2"

Example 3:
Input formula = "K4(ON(SO3)2)2"
Output: "K4N2O14S4"

The problem statement is available here

Problem Introduction
In this problem, your goal is to add parentheses to a given arithmetic expression to maximize its value.
max(5 − 8 + 7 × 4 − 8 + 9) =?

Problem Description
Task.
Find the maximum value of an arithmetic expression by specifying the order of applying its arithmetic operations using additional parentheses.

Input Format.
The only line of the input contains a string s of length 2n + 1 for some n, with symbols S0, ..., S2n.
Each symbol at an even position of S is a digit (that is, an integer from 0 to 9) while each symbol at an odd position is one of three operations from {+,-,*}.

Constraints.
1 ≤ n ≤ 14 (hence the string contains at most 29 symbols).

Output Format.
Output the maximum possible value of the given arithmetic expression among different orders of applying arithmetic operations.

E.g. 1.
Input:
1+5
Output: 6

E.g. 2.
Input: 5-8+7*4-8+9
Output: 200
200 = (5 − ((8 + 7) × (4 − (8 + 9))))