Thursday, February 16, 2012

LightOJ 1071 - Baker Vai

Problem Link: http://lightoj.com/volume_showproblem.php?problem=1071

Problem in short -
Given an x n grid of numbers, you have move from top-left cell to the bottom-right cell and then get back to top-left cell without stepping on any cell twice and maximizing the sum of the numbers on the path.

Sunday, August 21, 2011

UVa 11300 - Spreading the Wealth

Problem link: http://uva.onlinejudge.org/external/113/11300.html

Problem in short -
Given n people sitting on a circular table, each with some number of coins, you have to redistribute the coins in a manner so that everyone has equal number of coins. Any person can only pass coins to his left or right. Calculate the minimum number of coins that need to be transferred.

Sunday, July 31, 2011

UVa 11813 - Shopping

Problem Link: http://uva.onlinejudge.org/external/118/11813.html

Problem in short -
Given a weighted undirected graph with around 10^5 nodes and edges and at most 10 store nodes which you must visit, create the minimum distance route starting from a particular node that visits all other nodes and returns to that node.

Monday, July 11, 2011

UVa 315 - Network

Problem Link: http://uva.onlinejudge.org/external/3/315.html

Problem in short -
Given an undirected graph with N nodes, we'll need to find no. of articulation points in that graph.
 I've used the Tarjan's algorithm described in Wikipedia (http://en.wikipedia.org/wiki/Biconnected_component). There's also an algorithm described here - http://www.ibluemojo.com/school/articul_algorithm.html , but this one is probably overly complicated with many variables.

UVa 10158 - War

Problem Link: http://uva.onlinejudge.org/external/101/10158.html

This is a disjoint set data structure problem, but with a twist. In this problem, there are around 10000 people and 4 types of operations on them -
setFriends(x, y) shows that x and y are from the same country
setEnemies(x, y) shows that x and y are from different countries
areFriends(x, y) returns true if you are sure that x and y are friends
areEnemies(x, y) returns true if you are sure that x and y are enemies