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 —
1 3 4
Explanation — after 1 sec B = 0 + X = 1,monster of 0th index got killed,
Value of X = 2 now
Value of B = 0 now
after 2 sec B = 0 + 2 = 2
after 3 sec B = 2 + 2 = 4,monster of 2nd index got killed,
Value of X = 3 now,
value of B = 0 now
after 4 sec B = 0 + 3 = 3,monster of index 1th got killed
1 1 4 9 10
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.