## Computer Science & Engineering Problem Solving Lab Experiments

# Searching and Sorting

Searching and Sorting are very important areas in computer science. Efficient sorting algorithms are required for optimizing the use of other algorithms that require sorted lists to work correctly, for example to do binary search sorting is required.We present two problems here based on variant of binary search and sorting. Hope you will appreciate them.

## Problem 1:

You are given some set of numbers. By choosing three numbers we may be able to construct a triangle. In this problem we ask you to find out the number of invalid triangles formed from these set of numbers. The degenerate traiangles are considered to be valid traiangles.

**Input Specification**

Input contains N(<= 1000), followed by N numbers in the next line.The numbers
are separated by spaces and each number is > 0 and < 10^{6}.

**Output Specification**

Print the number of invalid traingles that can be formed.

**Sample Input and Output**

Input: 5

1 2 3 4 10

Output: 7

## Problem 2:

Given a String and a character set we need to find out the length of the smallest substring which contains all the characters of the set.

**Input Specification**

The input contains a string(length<=10^{5}) made up of small letters from english language followed by number of characters N(< 26) and then N chracters in the next line follow separated by spaces.

**Output Specification**

The output must contain the length of the smallest substring which contains all the characters from the character set. If no such substring exists report -1.

**Sample Input and Output**

Input: applelooksred 3 e a p

Output: 5