ICPC PNW 2016 - Revision history

Admin: /* Enclosure */

2017-05-25T03:03:23Z

Enclosure

← Older revision		Revision as of 03:03, 25 May 2017
Line 147:		Line 147:
	Input file consists of first line with n and k, <math>3 \leq k < n \leq 100,000</math>		Input file consists of first line with n and k, <math>3 \leq k < n \leq 100,000</math>

	Remaining n lines are the tree locations <math>(x_i, y_i)</math>, where <math>x_i, y_i \in \~~mathfrak~~{Z}</math> and <math>\|x_i\|, \|y_i\| \leq 10^9</math>		Remaining n lines are the tree locations <math>(x_i, y_i)</math>, where <math>x_i, y_i \in \mathbb{Z}</math> and <math>\|x_i\|, \|y_i\| \leq 10^9</math>

	Trees are guaranteed not to have 3 colinear tree locations.		Trees are guaranteed not to have 3 colinear tree locations.

Admin: /* Solution Strategy A */

2017-05-25T02:58:47Z

Solution Strategy A

← Older revision		Revision as of 02:58, 25 May 2017
Line 190:		Line 190:

	<pre>		<pre>
			////////////////////////////////////
			// Load the data

	initialize array of x and y values		initialize array of x and y values

	for each token in file:		for each token in file:
	load x and y values		load x and y values

			////////////////////////////////////
			// Compute mean/centerpoint/centroid of original data

	initialize original average		initialize original average
	for each i in k:		for each i in k:
	update average		update original average

			/////////////////////////////////////
			// Compute variance (spread) of original data

	initialize original variance		initialize original variance
	for each i in k:		for each i in k:
	update variance		update original variance

	for each j in uncontrolled points:		for each j in uncontrolled points:
	compute new average_j		compute new average_j
	compute new variance_j		compute new variance_j
			if(variance > max_variance)
			save point j as new "picked" point

			/////////////////////////////////
			// Once we have picked a point,
			// calculate polygon area.
			// This is a convex hull algorithm: https://en.wikipedia.org/wiki/Convex_hull
			// Use the graham scan: https://en.wikipedia.org/wiki/Graham_scan

	</pre>		</pre>

Admin: /* Solution Strategy */

2017-05-25T02:48:56Z

Solution Strategy

← Older revision		Revision as of 02:48, 25 May 2017
Line 153:		Line 153:
	Print the maximum power you can achieve by gaining control over a single tree, rounded to 1 decimal place.		Print the maximum power you can achieve by gaining control over a single tree, rounded to 1 decimal place.

	==Solution Strategy==		===General Solution Strategy===

	Two tasks:		Two tasks:
Line 207:		Line 207:
	compute new variance_j		compute new variance_j
	</pre>		</pre>



	==Flags==		==Flags==

	{{CPFlag}}		{{CPFlag}}

Admin: /* Buggy Robot: Approach */

2017-05-25T02:44:29Z

Buggy Robot: Approach

← Older revision		Revision as of 02:44, 25 May 2017
Line 85:		Line 85:
	* But, this would not find the solution if ONLY the first character is wrong.		* But, this would not find the solution if ONLY the first character is wrong.
	* Basing the search on edit distance means we can find the solution faster (less time wasted); combining it in a nested for loop (for each edit distance, for each char in command sequence) allows us to find solutions where, say, we only need to edit the first character.		* Basing the search on edit distance means we can find the solution faster (less time wasted); combining it in a nested for loop (for each edit distance, for each char in command sequence) allows us to find solutions where, say, we only need to edit the first character.
	~~https://charlesreid1.com/w/index.php?title=ICPC_PNW_2016&action=edit~~

	===Buggy Robot: Solution===		===Buggy Robot: Solution===

Admin: /* Flags */

2017-05-24T21:26:17Z

Flags

← Older revision		Revision as of 21:26, 24 May 2017
Line 213:		Line 213:
	==Flags==		==Flags==

	~~[[Category:Competitive Programming]]~~		{{CPFlag}}

Admin: /* Enclosure */

2017-05-24T18:42:50Z

Enclosure

← Older revision		Revision as of 18:42, 24 May 2017
Line 142:		Line 142:
	[[ICPC PNW 2016/Camera.java]]		[[ICPC PNW 2016/Camera.java]]

	=Enclosure=		==Enclosure==

			In a forest with trees located at particular coordinate locations, you control k of the n trees. The territory you control is defined by smallest convex polygon containing all the trees you control.

			Input file consists of first line with n and k, <math>3 \leq k < n \leq 100,000</math>

			Remaining n lines are the tree locations <math>(x_i, y_i)</math>, where <math>x_i, y_i \in \mathfrak{Z}</math> and <math>\|x_i\|, \|y_i\| \leq 10^9</math>

			Trees are guaranteed not to have 3 colinear tree locations.

			Print the maximum power you can achieve by gaining control over a single tree, rounded to 1 decimal place.

			==Solution Strategy==

			Two tasks:

			1. Determine the convex polygon determined by the k points

			2. Determine the change (incremental) in area by adding 1 point

			===Solution Strategy A===

			Alternative to above: we can re-cast the problem in terms of variance. The point that maximizes the convex polygon area is the point that maximizes the variance in the data points.

			This is because the convex polygon area uses the distance from the center of the polygon (mean of the 2D points) to the points. Essentially, we're using discrete points in discrete 2D space, but the continuous form would be an integral over the function f(x,y) in two dimensions to get the area of the arbitrary shape. So, we're doing numerical integration, and finding the value that maximizes our integral value.

			To maximize area therefore requires maximizing the distance function - distance from origin to boundary. (In this case, the boundary is defined by the furthest-away points.)

			If we are maximizing the distance function,

			<math>
			d = \sqrt{ \Delta x^2 + \Delta y^2 }
			</math>

			that is equivalent to maximizing the squared distance function,

			<math>
			d^2 = \Delta x^2 + \Delta y^2
			</math>

			So we can focus on that. In this case, <math>\Delta x = x - \overline{x}</math> and <math>\Delta y = y - \overline{y}</math>

			The point that will lead to the largest territory gain is the one that will lead to the highest variance in 2D space.

			Side note: [[MeanAndVariance]]

			Pseudocode:

			<pre>
			initialize array of x and y values

			for each token in file:
			load x and y values

			initialize original average
			for each i in k:
			update average

			initialize original variance
			for each i in k:
			update variance

			for each j in uncontrolled points:
			compute new average_j
			compute new variance_j
			</pre>

Admin: /* Flags */

2017-05-24T18:06:12Z

Flags

← Older revision		Revision as of 18:06, 24 May 2017
Line 141:		Line 141:

	[[ICPC PNW 2016/Camera.java]]		[[ICPC PNW 2016/Camera.java]]

			=Enclosure=



	==Flags==		==Flags==

	[[Category:Competitive Programming]]		[[Category:Competitive Programming]]

Admin: /* cameras */

2017-05-24T18:05:58Z

cameras

← Older revision		Revision as of 18:05, 24 May 2017
Line 91:		Line 91:
	See [[ICPC PNW 2016/BuggyRobot.java]]		See [[ICPC PNW 2016/BuggyRobot.java]]

	==~~cameras~~==		==Cameras==

	Consider a street with n houses		Consider a street with n houses

Admin: /* Cameras Approach */

2017-05-22T22:44:37Z

Cameras Approach

← Older revision		Revision as of 22:44, 22 May 2017
Line 137:		Line 137:

	Possible starting positions: init = 0, init = 1, init = 2, ..., init = r		Possible starting positions: init = 0, init = 1, init = 2, ..., init = r

			===Camera Solution===

			[[ICPC PNW 2016/Camera.java]]

	==Flags==		==Flags==

	[[Category:Competitive Programming]]		[[Category:Competitive Programming]]

Admin: /* Flags */

2017-05-22T22:43:54Z

Flags

@@ Line 90: / Line 90: @@
 See [[ICPC PNW 2016/BuggyRobot.java]]
 ==Flags==
 [[Category:Competitive Programming]]