Problem Summary

Two players play a game with a sequence of N positive integers laid onto a 1*N game board. Player 1 starts the game and they move alternately by selecting a number from either the left or the right end of the board. The selected number is then deleted, and its value is added to the score of the player who selected it. Whoever has the greater sum in the end wins.
Write a program that implements the optimal strategy for player 2. The optimal strategy yields maximum points when playing against the “best possible” opponent.

Read More

Problem Summary

Given a board with R rows and C columns, a king and some(from zero to R*C) knights, and their moving patterns, compute the minimum number of moves the player must perform to gather them all in the same square.

Specially, whenever the king and any knight are placed in the same square, the player may choose to move the king and the knight together from that point on, as a single knight.

Read More

Problem Summary

Given an undirected graph, find the weight of its minimum spanning tree.

Solution

Since the graph is dense, we choose Prim Algorithm over Kruskal Algorithm.
The graph is stored in adjacency matrix, so the time complexity is O(n^2).

Read More

Problem Summary

Given N, find the last digit of N! that is not zero.

Solution

The solution is obvious once we notice that,

1. Only 2 and 5 as a pair can cause 0 at the end of the product,
2. There are always more 2s than 5s in a factorial.

Read More

Problem Summary

Given P pastures, C cows and their locations, and the paths connecting the pastures, choose a pasture for farmer John to put a piece of butter, making the total time that cows need to walk there minimal.

Read More

Problem Summary

Given the initial and target configurations of the magic board, and three basic transformations, compute a minimal sequence of basic transformations.

Read More