## Travel around the world

There are N cities and N directed roads in Steven's world. The cities are numbered from 0 to N - 1. Steven can travel from city i to city (i + 1) % N, ( 0-> 1 -> 2 -> .... -> N - 1 -> 0). Steven wants to travel around the world by car. The capacity of his car's fuel tank is C gallons. There are a[i] gallons he can use at the beginning of city i and the car takes b[i] gallons to travel from city i to (i + 1) % N. How many cities can Steven start his car from so that he can travel around the

View Solution →## Longest Palindromic Subsequence

Steve loves playing with palindromes. He has a string, s, consisting of n lowercase English alphabetic characters (i.e., a through z). He wants to calculate the number of ways to insert exactly 1 lowercase character into string s such that the length of the longest palindromic subsequence of s increases by at least k. Two ways are considered to be different if either of the following conditions are satisfied: The positions of insertion are different. The inserted characters are different. T

View Solution →## Candles Counting

Tim is visiting his grandma for two days and is bored due to the lack of the electricity over there. That's why he starts to play with grandma's colorful candle collection. He aligned the N candles from left to right. The ith candle from the left has the height Hi and the color Ci, an integer ranged from 1 to a given K, the number of colors. Now he stares at the sequence of candles and wonders, how many strictly increasing ( in height ) colorful subsequences are there? A subsequence is con

View Solution →## Hyper Strings

String A is called a Super String if and only if: A contains only letters a,b,c,d,e,f,g,h,i,j; For any i and j, A[i] has lower ascii code than A[j], where 0 < i < j < length(A) Given a set of Super Strings H, a Hyper String is a string that can be constructed by concatenation of some Super Strings of the set H. We can use each Super String as many times as we want. Given set H, you have to compute the number of Hyper Strings with length no greater than M. Input Format The first lin

View Solution →## Swap Permutation

You are given an array A = [1, 2, 3, ..., n]: 1.How many sequences (S1) can you get after exact k adjacent swaps on A? 2.How many sequences (S2) can you get after at most k swaps on A? An adjacent swap can be made between two elements of the Array A, A[i] and A[i+1] or A[i] and A[i-1]. A swap otherwise can be between any two elements of the array A[i] and A[j] ∀ 1 ≤ i, j ≤ N, i ≠ j. Input Format First and only line contains n and k separated by space. Constraints 1 ≤ n ≤ 25

View Solution →