Almost Equal - Advanced
A Sumo wrestling championship is scheduled to be held this winter in the HackerCity where N wrestlers from different parts of the world are going to participate. The rules state that two wrestlers can fight against each other if and only if the difference in their height is less than or equal to K, (i.e) wrestler A and wrestler B can fight if and only if |height(A)-height(B)|<=K. Given an array H[], where H[i] represents the height of the ith fighter, for a given l, r where 0 <= l <= r < N,
View Solution →Almost sorted interval
Shik loves sorted intervals. But currently he does not have enough time to sort all the numbers. So he decided to use Almost sorted intervals. An Almost sorted interval is a consecutive subsequence in a sequence which satisfies the following property: The first number is the smallest. The last number is the largest. Please help him count the number of almost sorted intervals in this permutation. Note: Two intervals are different if at least one of the starting or ending indices are diffe
View Solution →Roy and alpha-beta trees
Roy has taken a liking to the Binary Search Trees(BST). He is interested in knowing the number of ways an array A of N integers can be arranged to form a BST. Thus, he tries a few combinations, and notes down the numbers at the odd levels and the numbers at the even levels. You're given two values, alpha and beta. Can you calculate the sum of Liking of all possible BST's that can be formed from an array of N integers? Liking of each BST is defined as follows (sum of numbers on even levels
View Solution →Coloring Tree
You are given a tree with N nodes with every node being colored. A color is represented by an integer ranging from 1 to 109. Can you find the number of distinct colors available in a subtree rooted at the node s? Input Format The first line contains three space separated integers representing the number of nodes in the tree (N), number of queries to answer (M) and the root of the tree. In each of the next N-1 lines, there are two space separated integers(a b) representing an edge from
View Solution →Recalling Early Days GP with Trees
You are given a tree with N nodes and each has a value associated with it. You are given Q queries, each of which is either an update or a retrieval operation. The update query is of the format i j X This means you'd have to add a GP series to the nodes which lie in the path from node i to node j (both inclusive) with first term of the GP as X on node i and the common ratio as R (given in the input) The retrieval query is of the format i j You need to return the sum of the node v
View Solution →