I am referring to this problem: Determining DNA Health. The editorial mentions using Aho- Corasick Algorithm. I was wondering can it be solved using tries?

Given an array A of length N, what is the best approach to answer queries of the form (i,j) where i and j are the indices of the array. Answer to a query (i,j) is the length of longest increasing subsequence of subarray from i to j. I am thinking of making a 2-D matrix which stores the length of LIS of all subarrays and then answering queries in O(1). How should I go about making that 2-D matrix? Or is there a better approach?

Two letter strings are the strings consisting of only two letters "X" and "Y". A string is "super two letter string" if

a) It does not have leading "X" letters. b) It does not contain P consecutive "X" letters. Your task is to find total number of Super two letter strings of length N.

How to identify the states of dynamic programming for the above problem? Problem Link: Super two letter strings

Thanks!

The problem statement is as follows: Problem description.

Little Schrodinger had a magical cat. That cat once fell down an empty well. As the walls of the well were not completely vertical, the cat could climb up the well. In one day, the cat can climb 1 unit height and the height of the well is h units. The cat starts at the bottom. Every day, a cat would divide into 2 cats. One of them would climb up 1 unit. The other would wait for help. But while waiting it would fall asleep and roll down 1 unit, unless it is already at the bottom, in which case it just remains there. When a cat would reach the top, it would run home to Schrodinger. (Schrodinger doesn't know that some of the cats are in a well and so he can't rescue them). It has been d days since the cat fell into the well. How many cats would come out of the well today? You would notice that the number of cats grows very large with each passing day, so output the answer modulo 10^9+7. NOTE : d = 0 means that the cat has fallen just now and so there's just one cat at the bottom of the well. So you wouldn't see any cat coming out today. If the height of the well is 1 unit, you will see a cat come out tomorrow.

Problem link : Cats of Schrodinger

Please suggest an approach to solve this problem. (Problem Link)

There are N servers which you have to place in N slots. Slots and servers are numbered from 1 to N. A distance between slots i and j is |i — j|. There are M pairs of servers that should be connected by wire. You are to place all the servers in the slots so the total wire length is minimized.

The problem statement is given here : Problem Statement

What is the meaning of these two macros? ~~~~~

define ifc(x) (flag[x>>6]&(1<<((x>>1)&31)))

define isc(x) (flag[x>>6]|=(1<<((x>>1)&31)))

~~~~~