Tree Pruning
A tree, t, has n vertices numbered from 1 to n and is rooted at vertex 1. Each vertex i has an integer weight, wi, associated with it, and t's total weight is the sum of the weights of its nodes. A single remove operation removes the subtree rooted at some arbitrary vertex u from tree t. Given t, perform up to k remove operations so that the total weight of the remaining vertices in t is maximal. Then print t's maximal total weight on a new line. Note: If t's total weight is already maxima
View Solution →Ones and Twos
You are using at most A number of 1s and at most B number of 2s. How many different evaluation results are possible when they are formed in an expression containing only addition + sign and multiplication * sign are allowed? Note that, multiplication takes precedence over addition. For example, if A=2 and B=2, then we have the following expressions: 1, 1*1 = 1 2, 1*2, 1*1*2, 1+1 = 2 1+2, 1+1*2 = 3 2+2, 2*2, 1+1+2, 1*2*2, 1*1*2*2, 1*2+1*2, 1*1*2+2, 1*2+2 = 4 1+2+2, 1+1*2+2 = 5 1+1+2
View Solution →Count Scorecards
In a tournament, n players play against each other exactly once. Each game results in exactly one player winning. There are no ties. You have been given a scorecard containing the scores of each player at the end of the tournament. The score of a player is the total number of games the player won in the tournament. However, the scores of some players might have been erased from the scorecard. How many possible scorecards are consistent with the input scorecard? Input Format The first line
View Solution →Vim War
A war has broken down between Vim and Emacs. Gedit, being Vim's ally, is captured by Emacs as a prisoner of war and it is up to Vim to rescue him by defeating Emacs. For this task, Vim has to assemble an army of appropriate skills. He can choose a non-empty subset of soldiers from a set of soldiers (numbered from 1 to N). Each soldier has some subset of skills out of M different skills (numbered from 1 to M). The skill-set of an army is the union of skill-sets of its constituent soldiers. To
View Solution →Best spot
In Chile, land are partitioned into a one large grid, where each element represents a land of size 1x1. Shaka is a newcomer in Chile and is trying to start his own business. He is planning to build a store. He has his own ideas for the "perfect store" which can be represented by a HxW grid. Element at position (i, j) represents height of land at index (i, j) in the grid. Shaka has purchased a land area which can be represented RxC grid (H <= R, W <= C). Shaka is interested in finding best
View Solution →