ruh_orz's blog

By ruh_orz, history, 6 weeks ago, In English

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

 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

»
6 weeks ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Problem 1: bitmask dp.

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