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.

https://charlesreid1.com/w/index.php?title=ICPC_PNW_2016&action=edit

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