Computer Science & EngineeringProblem Solving Lab →List Of 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 < 106.



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<=105) 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