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.

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

SPOJ IKEYB - I-Keyboard

Problem Link: https://www.spoj.pl/NSUDP/problems/IKEYB/

Description for this problem is really long. In short -

Given the set of keys on a keypad, a set of letters to assign on those keys sequentially and each letters' frequency on a dictionary, you have to design an optimal keypad layout (assign letters to keys) such that overall typing price is lowest. The price is determined as the sum of the prices of each letter. The price of a letter is a product of the letter frequency (Fi) and its position on the key.

SPOJ PT07X - Vertex Cover

Problem Link : https://www.spoj.pl/problems/PT07X/

This is a classic dynamic programming problem. We'll need to find minimal vertex cover of an unweighted, undirected tree.

UVa 10820 - Send A Table

Problem Link : http://uva.onlinejudge.org/external/108/10820.html

This is an straight forward Euler Totient Function problem. Given N, you have to find the sum of Totient Function of every number from 1 to N.

Now calculating Totient Function or Phi Function on each test case would be too slow. We need to pre-calculate Totient Function of every integer upto 50000. To do this, we can modify the Sieve method and utilize the following properties -