TIUP - Torneio Interuniversitário de Programação (2007)

Problem A

This problem is a brute force number problem. Given an n-digit number where the digits are d₁, d₂, ..., d_n, the value of that number is d₁ⁿ + d₂ⁿ + ... + d_nⁿ. We need to find numbers within given bounds such that the value of each number is equal to the respective number.

The values of each possible digits are already predetermined (that is, dⁿ). Therefore, it's plausible guess that there wouldn't be that many numbers. To get a good idea, one can make a program that generate all numbers that satisfy the constraint up until a certain bound, say 1 million. By doing this we find that our guess is quite good. Next step we can do is to generate all the numbers up to 2³¹-1. After that, we store the numbers in a small array, and make the following precalculated program:

#include <stdio.h>

int a[31] = {1,  2,  3,  4,  5,  6,  7,  8,  9,  
             153, 370, 371, 407, 1634, 8208, 9474, 
             54748, 92727, 93084, 548834, 1741725, 4210818, 
             9800817, 9926315, 24678050, 24678051, 88593477, 
             146511208, 472335975, 534494836, 912985153};

int main()
{
  int i,j,k, l = 0;
  scanf("%d %d", &j, &k);
  for (i = 0; i < 31; i++) if (a[i] >= j && a[i] <= k) 
    {l = 1; printf("%d\n", a[i]);}
  if (!l) printf("None\n");
  return 0;
}

Another approach is of course to optimize the brute force program we use to generate the numbers. One of a handful of constraints that we can place on this is that if we have the prefix of a number, say d₁, d₂, and d₃, we can only choose remaining digits such that the value will be less than (d₁*100 + d₂ * 10 + d₃) * 10^{n - 2}.

Problem B

This is a well known simulation problem. The only thing one can do is to (very) carefully follow the specification. Given the small limits (Apparently we don't know the limits, but let's assume that it's not too big, which apparently the case here), we don't need to pay much attention to inefficiencies as long as our program is exactly follows the spec. One good strategy to solve this problem is to have one team member to do an outline (in pseudocode or actual program) of the program, and give it to another member to double check it.

Problem C

A small N should always raise the alarm that a brute force program should work. It is also the case here. I will give a simple procedure to solve this problem. First of all, we remove all words that are a substring of another word. One important observation is that if we already have a part of the string, to add a word to the end of this string, we should use as many characters from the end of the string as possible to overlap it with the prefix of that word. If we do not do this, we will not get the shortest possible string.

After we find this observation, we can solve this problem in the following manner:

Answer <- None
foreach permutation P of {1, 2, ..., N}, 
  Result <- ""
  for i := 0 to N do
    begin
    Result <- append(Result, word[P[i]]). 
    end
  If (Answer = None) OR
     (Result is better than Answer) then
    Answer <- Result

There are two things to note:

1. For generating permutation in C++, we can use STL function next_permutation defined in the algorithm library.
2. Recall that a resulting string is better than another if its length is shorter, or if the length is equal, it is lexicographically preceed the other string (we can use strcmp in string.h library, or < in STL String, or compareTo method in Java).

The time complexity of this solution is O(N * N!).

We can still optimize this by sacrificing some space. For those who like an extra challenge, construct a dynamic programming algorithm that solve this in O(N² * 2^N) time using O(N * 2^N) space.

This problem has appeared before in TopCoder Single Round Match 302, with a more challenging limit.

Problem D

There are two parts to solve this problem. First part is to construct a new graph where the vertices are the filled nodes (offices), and each edge connects a pair of filled nodes with the weight of each node is the shortest distance (in this case, the number of link crossings) between any pair of filled nodes. The second part is to construct a minimum spanning tree from this new graph.

For the first part, we can use BFS (or Dijkstra, both will return the same answer since the weight of any link crossing is only one) P times (P is the number of filled nodes), with each BFS starts from a filled node. The complexity of O(P * N²) using a simple BFS implementation. For the second part, we can use any well known MST algorithm, such as Prim's or Kruskal's, where a naive implementation will cost O(P²).

If you have any difficulty regarding how to implement BFS or Dijkstra's algorithm, it may be a good idea to check the following tutorials: here and here. While for Prim's or Kruskal's algorithm, wikipedia is your friend.

Problem E

This is a well known problem of finding articulation points. You can find an exact implementation that solve this problem in PUC-Rio's ICPC team library. The complexity of that solution is O(N + M). However, given that N can be a huge number, it may be the case that you have to emulate the recursion manually, by building your own stack (instead of using a recursive function, that is).