[Link to problem] One measure of “unsortedness” in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the letter sequence DAABEC, this measure is 5, since D is greater than four letters to its right and E is greater than one letter to its right. This measure is called the number of inversions in the sequence. The sequence AACEDGG has only one inversion (E and D) — it is nearly sorted — while the sequence ZWQM has 6 inversions (it is as unsorted as can be — exactly the reverse of sorted). You are responsible for cataloging a sequence of DNA strings (sequences containing only the four letters A, C, G, and T). However, you want to catalog them, not in alphabetical order, but rather in order of “sortedness,” from “most sorted” to “least sorted.” All the strings… Read more →
EppsNet Archive: Dynamic Programming
Competitive Programming: SPOJ – String Problem
Link to problem Substring of some string A is defined as one or more (not necessary succeeding) elements of the string with maintaining the sequence. There are given two strings, string VOKI and string TOKI. Write the program that will calculate the length of any shortest substring of string VOKI such as it is not substring of string TOKI. Input In first line of input file there is string VOKI and in second one is string TOKI. The only characters that will occur are lowercase characters of English alphabet (‘a’- ‘z’). String lengths will be less or equal to 1000. Note: input data will be such so there will always be a solution. Output In the first line of file you should print the length of wanted substring. Sample input banana anbnaanbaan Sample output 5 (eg. banna) Sample input babab babba Sample output 3 (eg. aab) Solution below . .… Read more →
Competitive Programming: POJ 1159 – Palindrome
Description A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a program which, given a string, determines the minimal number of characters to be inserted into the string in order to obtain a palindrome. As an example, by inserting 2 characters, the string “Ab3bd” can be transformed into a palindrome (“dAb3bAd” or “Adb3bdA”). However, inserting fewer than 2 characters does not produce a palindrome. Input Your program is to read from standard input. The first line contains one integer: the length of the input string N, 3 <= N <= 5000. The second line contains one string with length N. The string is formed from uppercase letters from ‘A’ to ‘Z’, lowercase letters from ‘a’ to ‘z’ and digits from ‘0’ to ‘9’. Uppercase and lowercase letters are to be considered distinct.… Read more →
Competitive Programming: POJ 2663 – Tri Tiling
Description In how many ways can you tile a 3xn rectangle with 2×1 dominoes? Here is a sample tiling of a 3×12 rectangle. Input Input consists of several test cases followed by a line containing -1. Each test case is a line containing an integer 0 <= n <= 30. Output For each test case, output one integer number giving the number of possible tilings. Sample Input 2 8 12 -1 Sample Output 3 153 2131 Link to problem Solution below . . . Read more →
Competitive Programming: USACO Big Barn
Farmer John wants to place a big square barn on his square farm. He hates to cut down trees on his farm and wants to find a location for his barn that enables him to build it only on land that is already clear of trees. For our purposes, his land is divided into N x N parcels. The input contains a list of parcels that contain trees. Your job is to determine and report the largest possible square barn that can be placed on his land without having to clear away trees. The barn sides must be parallel to the horizontal or vertical axis. EXAMPLE Consider the following grid of Farmer John’s land where ‘.’ represents a parcel with no trees and ‘#’ represents a parcel with trees: 1 2 3 4 5 6 7 8 1 . . . . . . . . 2 . # .… Read more →