ICPC PNW 2016

Alphabet

A string is alphabetical if deleting 1 or more of its letters results in an alphabet string, a to z (abcdefg....wxyz).

Given a string, determine the minimum number of letters required to make it alphabetical.

Example input: xyzabcdefghijklmnopqrstuvw

Output: 3

Example input: aiemckgobjfndlhp

Output: 20

1 second computational limit.

Alphabet Approach

Start with an empty stack
Push first letter on to stack
For each remaining letter in the string:
    comesbefore = false
    compare this letter to stack.peek(), if it comes before, set comesbefore = true
    while(comesbefore):
        pop the stack
        compare this letter to stack.peek, if it comes before, set comesbefore = true
    push this letter onto the stack
Return 26 - stack.size()

The trick here was just to think this out by hand, one step at a time:

a
ai
aie -> ae
aem
aemc -> aec -> ac

if c < m, pop m
if c < e, pop e

Alphabet Solution

See ICPC PNW 2016/Alphabet.java

Buggy Robot

Navigating a 2-dimensional maze to find the exit.

N row x M col grid; empty cells (.) and obstacle cells (#)

One cell is the start position of robot (R), and one cell is exit (E).

Robot is given command string consisting of sequence of L/U/R/D to move left/up/right/down

If command causes robot to run into obstacle, it ignores that command

If the robot reaches exit, it ignores remaining commands

Find the minimum number of changes to an incorrect command string to make it correct

Concern here is not with the minimum path, but with the minimum number of changes.

1 second computational limit

Buggy Robot: Approach

Approach:

Same trouble as before, with the representation and initialization of mazes.
Faster way to do N/S/E/W or L/R/U/D?

Initialize graph for maze problem
For each edit distance, including 0, 
    for each char in command sequence:
        apply commands to see if it reaches the end
        if so, return - we are done

Initial hang-ups:

Was initially thinking of a depth-first traversal, where you apply the given command one step at a time and do a depth-first traversal for the remaining steps.
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.

Buggy Robot: Solution

See ICPC PNW 2016/BuggyRobot.java

Cameras

Consider a street with n houses

Of the n houses, k have security cameras

Neighborhood watch wants to ensure every r houses have cameras

Want at least 2 houses with cameras for each set of r consecutive houses

What is the minimum number of cameras to achieve this?

On the first line of the input file, n, k, and r are specified.

$2\leq n\leq 100,000$

$0\leq k\leq n$

$2\leq r\leq n$

The k lines that follow specify the locations of the k cameras (presumably, in order; the examples show them in order, but problem does not specify).

1 second limit

Cameras Approach

Thinking of all the houses as a long array of 0/1 values - 0 no camera, 1 camera

We are looking for minimum number of cameras - which depends on how we partition the houses.

For a given r, we need to try r different partitionings.

Moving window that slides along the houses

Every move increments a different counter
Every r moves, we cycle through and come back to the same counter
How to manage juggling k's? (Want to skip ahead to next k's for some counters, then go back again for others)
Multiple stacks?
One dequeue, throw away values if passed already.

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

Camera Solution

ICPC PNW 2016/Camera.java

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, $3\leq k<n\leq 100,000$

Remaining n lines are the tree locations $(x_{i},y_{i})$ , where $x_{i},y_{i}\in \mathbb {Z}$ and $|x_{i}|,|y_{i}|\leq 10^{9}$

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.

General 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,

$d={\sqrt {\Delta x^{2}+\Delta y^{2}}}$

that is equivalent to maximizing the squared distance function,

$d^{2}=\Delta x^{2}+\Delta y^{2}$

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

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:

////////////////////////////////////
// Load the data

initialize array of x and y values

for each token in file:
    load x and y values

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

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

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

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

for each j in uncontrolled points:
    compute new average_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