Yuta Nishino

Simple memoization and dynamic programming

ABC040C is a nice example of the simplest form of memoization or dynamic programming.
Using recursion without memoization cause TLE for this problem.

    import java.util.Scanner;

    public class ABC040C {
        static int n;
        static int[] as;
        static int[] costs;
        public static void main(String args[]) {
            Scanner sc = new Scanner(System.in);
            n = sc.nextInt();
            as = new int[n];
            as[0] = sc.nextInt();
            for (int i = 1; i < n; i++) {
                as[i] = sc.nextInt() - as[0];
            }
            as[0] = 0;
            costs = new int[n];
            for (int i = 0; i < n; i++) costs[i] = Integer.MAX_VALUE;
            //rec(n - 1);
            dp();
            System.out.println(costs[n - 1]);
        }

        // Memoization
        static int rec(int i) {
            if (i == 0) {
                costs[0] = 0;
                return costs[0];
            }
            if (i == 1) {
                costs[1] = Math.abs(as[1] - as[0]);
                return costs[1];
            }
            if (costs[i] < Integer.MAX_VALUE) return costs[i];
            costs[i] = Math.min(Math.abs(as[i] - as[i - 1]) + rec(i - 1),
                    Math.abs(as[i] - as[i - 2]) + rec(i - 2));
            return costs[i];
        }

        // Dynamic Programming
        static void dp() {
            costs[0] = 0;
            costs[1] = Math.abs(as[1] - as[0]);
            for (int i = 2; i < n; i++) {
                costs[i] = Math.min(Math.abs(as[i] - as[i - 1]) + costs[i - 1],
                        Math.abs(as[i] - as[i - 2]) + costs[i - 2]);
            }
        }
    }

ABC015C

I solved the problem with DFS using recursion, stack and stack with pruning.

Main part

    import java.util.Scanner;
    import java.util.Stack;

    public class ABC015C {
        static int n, k;
        static int[][] field;
        static boolean[][] visited;
        public static void main(String args[]) {
            Scanner sc = new Scanner(System.in);
            n = sc …

ABC095D
Published: Tue 30 January 2018
By Yuta Nishino

In Competitive programming.

tags: Java

To solve this problem and get full score, O(N) algorithm is needed. Naive solution takes O(N^3) time, however, by calculating information that is independent from the variable we loop through, we get O(N^2) and O(N) algorithms.

O(N^3)
```
    public class ABC095D {
        int n …
```
read more
ABC086D

Published: Sat 27 January 2018
By Yuta Nishino

In Competitive programming.

tags: imos Java

First, we can treat x and y as x modulo 2K and y modulo 2K.

I used imos method https://imoz.jp/algorithms/imos_method.html to count up the number in the array. After that, the array is folded back so that the cases where x >= 2K and y …
read more

Other articles