p097.pdf

p097.tex

\documentclass{article}
\usepackage{fancyhdr}
\usepackage{amsmath ,amsthm ,amssymb}
\usepackage{graphicx}
\usepackage{listings}

\begin{document}

This is slightly cheating because I picked this problem, and I really liked my
approach. I know that this can be solved by brute force, but it's incredibly ugly.

First let's define a function $d_k(x)$, that returns the $k$ least significant digits of $x$.

\begin{align}
	\nonumber
	d_1(0)& =0\\
	\nonumber
	d_1(14)& =4\\
	\nonumber
	d_2(14)& =14
\end{align}

This is really just the $mod$ function is a different form. Just a bit more terse.

\[ d_k(x) = x \bmod 10^k \]

This function has some identities that are useful for this problem. I won't
prove them.

\begin{align}
	\label{eq:multid}
	d_k(Cx) &= d_k(d_k(C) \cdot d_k(x))\\
	\label{eq:addid}
	d_k(C + x) &= d_k(d_k(C) + d_k(x))
\end{align}

Problem 97 asks us to produce the following:

\[
	d_{10}(28433 \cdot 2^{7830457} + 1)
\]

The identities \eqref{eq:multid} and \eqref{eq:addid} can help us break this
down into something slightly more manageable.

\begin{align}
	\nonumber
	A &= d_{10}(28433 \cdot 2^{7830457} + 1)\\
	\nonumber
	  &= d_{10}(d_{10}(28433) \cdot d_{10}(2^{7830457}) + d_{10}(1))\\
	  \label{eq:euler97}
      &= d_{10}(28433 \cdot d_{10}(2^{7830457}) + 1)
\end{align}

$d_{10}(2^{7830457})$ is a waste to compute. Though the identity \eqref{eq:multid} can be used to do some interesting modulus optimizations,
I'd rather find a more elegant solution.

Let's look at powers of two in more depth. Consider the powers of 2:

\[ 2^x = 1, 2, 4, 8, 16, 32, 64, 128, 256, \ldots \]

There is a pattern here when considering just the least signficant digit.

\[ d_1(2^x) = 1, 2, 4, 8, 6, 2, 4, 8, 6, \ldots \]

This sequence is eventually periodic, with period $4$.

\[ P(d_1(2^x)) = 4 \]

Using a short Haskell function, I found the periods for the first four digits of $2^x$:

\begin{align}
	\nonumber
	P(d_{1}(2^x)) &= 4\\
	\nonumber
	P(d_{2}(2^x)) &= 20\\
	\nonumber
	P(d_{3}(2^x)) &= 100\\
	\nonumber
	P(d_{4}(2^x)) &= 500
\end{align}

The periodicity looked like it could be generalized.

\begin{align}
	\label{eq:periodicity}
	P(d_k(2^x)) &= 4 \cdot 5^{k - 1}\\
	\label{eq:specificperiod}
	P(d_{10}(2^x)) &= 7812500
\end{align}

This number looks promising. Because $d_k(2^x)$ is not strictly periodic, but only eventually periodic, we aren't guaranteed that $d_k(2^x) = d_k(2^{x - P(d_k(2^x))})$. All we can do it just guess and check.



\begin{align}
	\nonumber
	A &= d_{10}(28433 \cdot d_{10}(2^{7830457}) + 1)\\
	\nonumber
	  &= d_{10}(28433 \cdot d_{10}(2^{7830457 - 7812500}) + 1)\\
	\nonumber
	  &= d_{10}(28433 \cdot d_{10}(2^{17957}) + 1)\\
	\label{eq:solution}
	  &= (28433 \cdot (2^{17957} \bmod 10^{10}) + 1) \bmod 10^{10}
\end{align}

This final formula \eqref{eq:solution} is much easier to compute.

\end{document}

updown.py

# poorly organized. sorry.

import sys

def take_steps(state, *chances):
    for chance in chances:
        state = step_forward(state, chance)

    return state


def woken_chance(chances):
    return take_steps((1, 0, 0), *chances)[2]


def step_forward(states, chance):
    return (
        states[0] * (1 - chance),
        states[0] * chance + states[1] * chance,
        states[1] * (1 - chance) + states[2]
    )


def run_test():
    examples = [n/10.0 for n in range(1, 10)]

    tries = []

    for a in examples:
        for b in examples:
            for c in examples:
                for d in examples:
                    tries.append((
                        a*(1-b) + a*b*(1-c) + (1-a)*b*(1-c) + a*b*c*(1-d) +
                        (1-a)*b*c*(1-d) + (1-a)*(1-b)*c*(1-d),
                        (a, b, c, d)
                    ))

    for entry in sorted(tries, key = lambda x:x[0]):
        print entry


class ActivityHill(object):
    def __init__(self, activities, dimensions):
        activities = sorted(activities, key=lambda x:x[0])
        activities = self.collapse_activities(activities)

        self.counter = 0
        self.activities = activities
        self.dimensions = dimensions
        self.next_step = None
        offset = 1 + len(activities) - dimensions

        if offset > 1:
            # there are more options that posibilities
            self.point = [(activities[0][0], 0)] + [
                (activity[0], i + offset)
                for i, activity in enumerate(activities[offset:])
            ]
        else:
            point_source = []

            size = 1
            tally = 0
            focus = -1
            ln = len(activities)
            while size < dimensions:
                if tally < activities[focus][1]:
                    tally += 1
                    size += 1
                    point_source.append((activities[focus][0], ln + focus))
                else:
                    tally = 0
                    focus -= 1

            point_source.append((activities[0][0], 0))
            point_source.reverse()
            self.point = point_source



    def collapse_activities(self, activities):
        new_activities = []
        for activity in activities:
            if new_activities:
                if activity[0] == new_activities[-1][0]:
                    new_activities[-1] = (
                        activity[0],
                        new_activities[-1][1] + activity[1]
                    )
                else:
                    new_activities.append(activity)
            else:
                new_activities.append(activity)
        return new_activities


    def value(self):
        return take_steps(
            (1, 0, 0),
            *[activity[0] for activity in self.point]
        )[2]


    def meets_constraints(self, indexes):
        counts = {}
        for i in indexes:
            counts.setdefault(i, 0)
            counts[i] += 1

        for i, v in counts.iteritems():
            if v > self.activities[i][1]:
                return False

        return True


    def climb_steepest_neighbor(self):
        chances, indices = zip(*self.point)
        chances = list(chances)
        indices = list(indices)

        best_result = woken_chance(chances)
        best_indexes = indices
        found_better = False
        better_matches = 0

        for i in range(len(chances) - 2):
            for r in [1, -1]:
                if 0 <= indices[i+1] + r < len(self.activities):
                    new_chances = chances[:]
                    new_chances[i+1] = self.activities[indices[i+1] + r][0]
                    new_result = woken_chance(new_chances)
                    if new_result < best_result:
                        new_indexes = indices[:]
                        new_indexes[i+1] += r
                        if self.meets_constraints(new_indexes):
                            best_result = new_result
                            best_indexes = new_indexes
                            found_better = True
                            better_matches += 1
                            if better_matches > 4:
                                break
            if better_matches > 4:
                break

        if found_better:
            self.counter += 1
            self.point = [
                (self.activities[i][0], i)
                for i in best_indexes
            ]

        return found_better


def hill_climb(activities, action_count):
    if action_count == 1:
        return 0.0

    config = ActivityHill(activities, action_count)
    while True:
        if not config.climb_steepest_neighbor():
            break

    return config.value()

def optimal_wake_rate(activities, action_count):
    if action_count == 1:
        return 0.0

    best_outcome = 1.0

    initial_state = (1, 0, 0)
    activities = sorted(activities, key = lambda x:x[0])

    permutations = [(initial_state, activities, 0)]

    while permutations:
        state, actions, round = permutations.pop()
        for i, action in enumerate(actions):
            loop_actions = actions[:]
            if action[1]:
                loop_state = step_forward(state, action[0])
                if round == action_count - 1:
                    best_outcome = min(best_outcome, loop_state[2])
                else:
                    loop_actions[i] = (action[0], action[1] - 1)
                    permutations.append((
                        loop_state,
                        loop_actions,
                        round + 1
                    ))

    return best_outcome

def read_input():
    activity_count, action_count = sys.stdin.readline().strip().split()
    action_count = int(action_count)

    activities = {}
    for _ in xrange(int(activity_count)):
        sleep_chance, limit = sys.stdin.readline().strip().split()
        activities.setdefault(sleep_chance, 0)
        activities[sleep_chance] += int(limit)

    actions = []
    for chance_str, limit in activities.iteritems():
        sleep_parts = chance_str.split('/')
        actions.append((
            int(sleep_parts[0]) / float(sleep_parts[1]),
            limit
        ))

    return actions, action_count

if __name__ == "__main__":

    case_num = int(sys.stdin.readline())
    for case_i in xrange(case_num):
        activities, action_count = read_input()
        wake_rate = hill_climb(activities, action_count)
        print 'Case #{0}: {1}'.format(case_i + 1, wake_rate)