Other articles

1. Two-way BFS on 2 by 2 by 2 rubik's cube

   If you are doing breadth first search and are finding the shortest path to the state you know how to represent it and that there is only one such state, then two-way BFS could be applied.
   It searches the graph from start state and end state and if the frontier …

   read more

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 …

   read more

3. ABC095D

   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

4. Graph Representations

   Graph

   A graph G consists of a set of the nonnegative number of vertices and a set of the nonnegative number of edges that connect two distinct vertices. It provides the ultimate flexibility to represent structure of data.

   In this article, I will show two ways to how to represent a graph on a computer.

   read more

5. Searching Arrays and Peak Finding

   Searching (un)sorted array

   Sequential search

   When searching unsorted array for some element, only what we can do is sequential search, which we take elements in the array one by one and check if it's the one we are searching for.

   read more

6. ABC086D

   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

7. Binary Heap

   Heap

   Heap is complete, partially ordered binary tree. Complete means every node at a depth of the tree has subtree that each height differs at most by 1. Partially ordered means that the a element stored in the tree is less than or equal only to its ancestors and greater than or equal only to its descendants, or the other way around.

   read more

8. Binary Search Tree

   Dictionary

   Search is surely the most frequenly performed action by computers. Let's consider a simple dictionary ADT that represent data structure that can do search and store information.

   Dictionary ADT

   read more

9. Partition-Based Sorting

   Sorting based on partition of an array

   Sorting algorithms more efficient than the one by transpositions exploit the divide and conquer principle.

   Shellsort

   Shellsort utilizes the near best cases behaviour of insertion sort. It partition the array and then sort the subarray using insertion sort. Then it make subarrays with smaller gap, meaning fewer and longer subarray.

   read more

Page 1 / 2 »