UVA - 10161 - Ant on a Chessboard

This article will explain my thought process to solve called Ant on a Chessboard (PDF) from UVA Online Judge. Read the original problem statement before reading this article.

Keywords: Pattern

Objective

Given:

A time.

We want to:

Find the location at the time.

Glossary

Pattern — A series of numbers, shapes, or objects that follow a predictable sequence or arrangement.

Observation

Alice moves with L-shaped movement that repeat the cycle of moving up-and-left, turn around to the upper-side, moving right-and-down, and turn around to the right-side. By analyzing the example grid, we could see that the L-shaped movement always started at n*n+1 time and finished at (n+1)^2 time.

After we have identified the range of the L-shaped movement, we need to differentiate 2 types of the L-shaped. The first one is the up-and-left movement, and the second one is the right-and-down movement. Since it is alternating, we could say that when the n is even, the direction of the movement is up-and-left, otherwise it is the right-and-down.

Next, to find the location of alice, we need to find movement range that satisfy n*n+1 <= time <= (n+1)^2. Since the n is squared, we could find n by calculating the square root of time.

After we have identified the n, we could calculate the starting position of the movement range and the time on the starting position. After that, the actual position can be calculated using the starting position, direction of the movement, and the time difference between the starting and actual time.

Algorithm

There is no advance algorithm needed for this problem. The pattern formula can be implemented easily on the code, and java has a built-in Math.sqrt() function to calculate the square root efficiently.

The time complexity of this solution is O(log2({maximum time})) or O(10^1).

Implementation

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * 10161 - Ant on a Chessboard
 * Time limit: 3.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1102
 */
public class Main {
    public static void main(final String... args) {
        final Scanner in = new Scanner(new BufferedInputStream(System.in));
        final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        final Process process = new Process();

        while (in.hasNextInt()) {
            final Input input = new Input();
            input.time = in.nextInt();
            if (input.time == 0) break;

            final Output output = process.process(input);
            out.format("%d %d\n", output.column, output.row);
        }

        in.close();
        out.flush();
        out.close();
    }
}

class Input {
    public long time;
}

class Output {
    public long column;
    public long row;
}

class Process {
    public Output process(final Input input) {
        final Pattern pattern = getPattern(input.time);
        final long[] cell = getCell(pattern, input.time);

        final Output output = new Output();
        output.column = cell[0];
        output.row = cell[1];
        return output;
    }

    private Pattern getPattern(final long time) {
        final long base = Math.round(Math.ceil(Math.sqrt(time))) - 1;
        return new Pattern(base);
    }

    private long[] getCell(final Pattern pattern, final long time) {
        long column = pattern.base + 1, row = pattern.base + 1;
        if (between(time, pattern.upright(), pattern.upleft())) {
            final long miss = Math.abs(time - pattern.upright());
            column -= miss;
        } else if (between(time, pattern.upright(), pattern.downright())) {
            final long miss = Math.abs(time - pattern.upright());
            row -= miss;
        }
        return new long[]{column, row};
    }

    private boolean between(final long value, final long range1, final long range2) {
        final long min = Math.min(range1, range2), max = Math.max(range1, range2);
        return min <= value && value <= max;
    }
}

class Pattern {
    public final long base;

    public Pattern(final long base) {
        this.base = base;
    }

    public long min() {
        return (base * base) + 1;
    }

    public long max() {
        final long base1 = base + 1;
        return (base1 * base1);
    }

    public long upright() {
        return min() + base;
    }

    public long upleft() {
        return even()? max() : min();
    }

    public long downright() {
        return even()? min() : max();
    }

    public boolean even() {
        return base % 2 == 0;
    }
}