Jolly Jumpers..~

Problem Statement
     
You are given an electrical circuit for a home, with a number of nodes possibly connected by wires. Any pair of nodes may be connected by at most one wire, and a node can't be connected to itself. Each node on the circuit is either an electrical outlet for the house or a connection to the main electrical grid. The vector <string> wires tells you the wires that are already in place; the xth character of the yth element is '1' (one) if nodes x and y have a wire between them, '0' (zero) otherwise. The vector <int> gridConnections lists the indices of the nodes that are connections to the main electrical grid.  You'd like to make the circuit safer and more redundant by adding as many extra wires to it as possible. The one complication is that no two main grid connections are currently wired together (directly or indirectly), and you must preserve this, or else disaster will result. Determine the maximum number of new wires you can add to the circuit.
Definition
   
Class:
AddElectricalWires
Method:
maxNewWires
Parameters:
vector <string>, vector <int>
Returns:
int
Method signature:
int maxNewWires(vector <string> wires, vector <int> gridConnections)
(be sure your method is public)
   
 
Constraints
-
wires will contain between 1 and 50 elements, inclusive.
-
Each element of wires will have the same length as wires.
-
Each element of wires will contain only the characters '0' and '1'.
-
Character i of element i of wires will be a '0'.
-
Character i of element j of wires will be the same as character j of element i.
-
gridConnections will contain between 1 and 50 elements, inclusive.
-
Each element of gridConnections will be an integer between 0 and length(wires)-1, inclusive.
-
Each element of gridConnections will be distinct.
-
Each pair of elements of gridConnections will not index nodes connected by a path of '1's in wires.
Examples
0)
 
   
{"000","000","000"}
{0}
Returns: 3
Every valid wire can be added.
1)
 
   
{"000","000","000"}
{0,1}
Returns: 1
0 and 1 can't be connected, but 0 and 2 (or 1 and 2) still can be.
2)
 
   
{"01","10"}
{0}
Returns: 0
This circuit is already complete.
3)
 
   
{"00000","00000","00000","00000","00000"}
{0,1,2,3,4}
Returns: 0
Any connections would be disastrous.
4)
 
   
{"01000","10100","01010","00100","00000"}
{2,4}
Returns: 3
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

Problem Statement
     
You are writing a program for a very simple processor. It is attached to a slow memory system that contains n bytes, numbered 0 to n - 1. The processor has a cache which holds a copy of k of these bytes at a time, for fast access. It has a base address (referred to as base below), and it holds a copy of the bytes numbered base, base+1, ..., base+k-1.
In order to keep the processor as simple as possible, the programmer must directly control the cache. To access some byte in memory, the program must first set the cache base address. Any bytes that are in the new range that were not in the old range are read from the memory store, but bytes that were in both the old and new ranges are simply kept in the cache and do not require a read from the memory store.
You wish to optimize a program to use as few memory reads as possible. The bytes that the program accesses, in the order it accesses them, are given in addresses. Determine the minimum number of bytes that must be read from the memory store. Note that when the program starts, the cache is in a special empty state, so the first cache update always requires k bytes to be read.
Definition
   
Class:
ContiguousCache
Method:
minimumReads
Parameters:
int, int, vector <int>
Returns:
long long
Method signature:
long long minimumReads(int n, int k, vector <int> addresses)
(be sure your method is public)
   
 
Constraints
-
n will be between 1 and 1,000,000,000, inclusive.
-
k will be between 1 and n, inclusive.
-
addresses will contain between 1 and 50 elements, inclusive.
-
Each element of addresses will be between 0 and n-1, inclusive.
Examples
0)
 
   
100
3
{0, 2, 16, 13}
Returns: 7
The first access must read bytes 0 to 2, inclusive. For the second access, no reads are needed, since 2 is already cached. For the third access, the base address should be set to 14. Then for the final access, the base address is set to 13, and only one additional byte must be read.
1)
 
   
100
10
{1,10,19,28,30,37}
Returns: 29
 
2)
 
   
1000000000
500000000
{0, 999999999, 1, 500000000, 500000001, 987654321}
Returns: 1987654320
 
3)
 
   
8
2
{7}
Returns: 2
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

Problem Statement
     
Dissatisfied with the inconvenient spherical shape of the Earth, a group of map-makers have gone to Magrathea to obtain a custom-built planet. They decided to design their new planet to be flat and in the shape of a polygon. All coordinates will be in the Cartesian (x, y) plane.
In order to provide everyone on the planet with internet access, a wireless router will be placed at every lattice point that is inside the polygon (a lattice point is a point with integer coordinates). The map-makers decided to keep their job simple by choosing a polygon with no lattice points on its boundary.
Because the map-makers are highly rational people, they decided that the coordinates of all the vertices of the polygon would be fractions with a common denominator. The vertices of the polygon (in order), are given by the vector <int>s x and y, and by the common denominator denom. The ith vertex is (x[i]/denom, y[i]/denom).
Calculate and return the number of routers required.
Definition
   
Class:
WifiPlanet
Method:
routersNeeded
Parameters:
vector <int>, vector <int>, int
Returns:
long long
Method signature:
long long routersNeeded(vector <int> x, vector <int> y, int denom)
(be sure your method is public)
   
 
Constraints
-
x and y will contain the same number of elements.
-
x and y will each contain between 3 and 50 elements, inclusive.
-
Each element of x and y will be between 1 and 10^9, inclusive.
-
No two vertices of the polygon will be the same.
-
No two edges of the polygon (including their end-points) will intersect, with the exception that adjacent edges will intersect at their common end-point.
-
No lattice point will lie on the boundary of the polygon.
-
denom will be between 2 and 10^9, inclusive.
Examples
0)
 
   
{1,7,3,3}
{1,1,3,5}
2
Returns: 2
This is illustrated in the image below:
 
1)
 
   
{3,3,4,4,5,6,10,10,11,11,10,10,9,9}
{1,2,2,6,3,8,8,9,9,3,3,2,2,1}
3
Returns: 4
 
2)
 
   
{50,1000050,1000049}
{2,1000002,1000003}
100
Returns: 0
 
3)
 
   
{32,32,64,8,15,1000,999}
{1,10,10,48,48,47,1}
16
Returns: 120
 
4)
 
   
{1,1000000000,1000000000,1}
{1,1,1000000000,1000000000}
3
Returns: 111111110888888889
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.