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

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.