Your friend for GRE words and Vocabulary. Find here

April 2011

//April 2011


By |October 14th, 2012|

Bob has n heap(s) of gravel (initially there are exactly c piece(s) in each). He wants to do m operation(s) with that heaps, each maybe:

adding pieces of gravel onto the heaps from u to v, exactly k pieces for each,
or querying “how many pieces of gravel are there in the heap p now?”.

Help Bob do […]

Rectangles Counting

By |October 14th, 2012|

Given N separate integer points on the Cartesian plane satisfying: there is no any three of them sharing a same X-coordinate. Your task is to count the number of rectangles (whose edges parrallel to the axes) created from any four of given points.
There are several test cases (ten at most), each formed as follows:

The first […]

Number Game Revisited

By |October 14th, 2012|

Alice and Bob play the following game.They choose a number N to play with.The runs are as follows :

1.Bob plays first and the two players alternate.

2.In his/her turn ,a player can subtract from N any prime number(including 1) less than N.The number thus obtained is the new N.

3.The person who cannot make a move in […]

Graphs in Euclidean Space

By |October 14th, 2012|

The Chef is a bit tired of graphs. He has spent far too many days calculating shortest paths, finding bipartite matchings, minimum cuts, and optimizing over NP-hard problems. He needs a break. Unfortunately for him, the food services industry doesn’t take breaks. Once again, the Chef has to navigate through an undirected graph to keep […]

Generalized Independent Sets

By |October 14th, 2012|

Given a graph G on nodes V with undirected edges E, an independent set X is a subset of V such that no edge in E has both endpoints in X. Finding the size of the largest independent set in a graph is currently a very difficult problem.

Consider the following generalization of an independent set. […]

Central Point (April 2011)

By |October 14th, 2012|

Given a set of N integer points on the Cartesian plane. Your task is to find an integer point satisfying its sum of distances to N given points (S) is minimum.
There are several test cases (fifteen at most), each formed as follows:

The first line contains a positive integer N (N ≤ 2,000).
N lines follow, each […]