These problems were asked in Coding test of Trilogy Innovations(formally Codenation) held yesterday,Hoping our CF community will provide explanation of approach to these problems.

I will write down as much I remember the problem statements. Sorry for my poor English.

**Problem 1** — Given an array A of length N, representing defense capacity of N monsters.Being a hero you have to kill all monster using your weapon of attacking capacity B (initially equal to 0).

Given condition that each second your attacking capacity increases by X (initially X equal to 1), and when an monster gets killed X value increases by 1 ( X = X + 1) and your attacking power becomes 0(ie. starts from beginning).

**ith** Monster gets killed when **A[i] <= current attacking power (ie B)**

You can kill monsters in any order.

Value of B gets reset to 0(the instant monster is killed)

**example** Input —

3

1 3 4

output —

4

**Explanation**

Input —

5

1 1 4 9 10

Output —

8

Constraints —

N<=20

A[i]<=100000

**Problem 2**

You are given a string **S** of length N consisting of lowercase letter(a-z).

You are also given an Tree of N nodes numbered from 0 to N-1 , where ith node represent **S[i]** character.

You have to process Q queries consisting of 2 values **A and B** representing string we will obtain on concatenate of characters represented by nodes we visit while moving from **A** th node to **B** th node via shortest path between them.

After processing all queries,you have to return no. of unique strings found during processing Q queries mod 10^9+7;

Input Format —

First Line contains N (length of string)

Second line contains string S of length N

Next N-1 lines contains E1 and E2 (each 0<=value<=N-1) representing there is a edge between those 2 nodes

Next line contains Q (number of Queries)

Next line Q lines contains A and B (each 0<=value<=N-1)

Output Format —

Return Number of Unique string found during process of all Q queries.

Constrains —

N<=10000

Q<=10000

Problem 1: bitmask dp.

Problem 2: Not confirmed but binary lifting and hashing feel probable.