MEC Algorithms Programming Contest, 2014

You will need to access project related files for this contest at
http://mlxstorage.blob.core.windows.net/mec-v2/AlgoRhythm2014.zip

Problem Description
Consider a stock market with n types of stocks numbered 0, 1, , n 1. Initially, no stocks
can be exchanged. However after each unit of time, the stock market receives information of
the form (i, j, k). Once such information is received, one unit of stock i can be exchanged for
k units of stock j, where k is a positive real number. Such an exchange remains valid until
new information of the type (i, j, k) is received, indicating that one unit of stock i can now be
exchanged for k units of stock j. For example, suppose the stock market receives the
following sequence of information:

Time unit Information
1 (0, 2, 0.5)
2 (0, 1, 1.3)
3 (1, 0, 0.8)
4 (0, 1, 1.2)
5 (2, 1, 2.6)

We say that time unit 3 is trivially profitable because during this time unit it is possible to
exchange two stocks (stock 0 and stock 1) and make a profit:
1 unit of stock 0 1.3 units of stock 1
1.3 units of stock 1 1.3 0.8 = 1.04 units of stock 0

Note that the above exchanges transform one unit of some stock into more than one unit of
the same stock. By repeating this sequence rapidly (high-frequency trading) during time
unit 3, it is possible to make a large profit. The stock market quickly corrects this in time
unit 4 by revising the exchange rate between stock 0 and 1 to 1.2 (instead of 1.3). You can
easily check that the above sequence is no longer profitable (since 1.2 0.8 = 0.96 1).

Now consider time unit 5. We say that time unit 5 is profitable because during this time unit
it is possible to perform a sequence of exchanges that transforms one unit of some stock into
more than one unit of the same stock:
1 unit of stock 0 0.5 units of stock 2
0.5 units of stock 2 0.5 2.6 = 1.3 units of stock 1
1.3 units of stock 1 1.3 0.8 = 1.04 units of stock 0

Thus, time unit 3 is (trivially) profitable, time unit 5 is profitable, and all other time units (1,
2 and 4) are not profitable.

Project goal #1 (easy): Given a sequence of information as in the example above, find the
number of trivially profitable time units. For the above example, the answer would be 1.

Project goal #2 (challenge): Given a sequence of information as in the example above,
find the number of profitable time units (including trivially profitable time units). For
the above example, the answer would be 2.

Input Format
The input to the problem will be given in a plain text file, formatted exactly as follows:
Line 1: This line only contains the positive integer n (the number of stocks).
Remaining lines: Each remaining line contains three numbers i j k separated by a
single space, corresponding to information (i, j, k) as described above. Note that i
and j are integers in the range 0 to n1, and k is a positive real number.
We are giving you a C program (AlgoRhythm.c) that reads inputs in the above format.

Output Format
Your program will print a single number:
the number of trivially profitable time units as defined above, if you are only aiming
for goal #1.
the total number of profitable time units (trivial + non-trivial) as defined above, if you
are aiming for goal #2.

Example input 1:
2
0 1 0.5
1 0 2

Output for the example input 1 (for both goal #1 and goal #2):
0

Explanation: Before time unit 2, there is no sequence of exchanges from one unit of a stock
back to itself. At time unit 2, it is possible to exchange stocks 0 and 1, but exchanging one unit
of either stock for the other and then exchanging back results in only one unit of the original
stock (neither a profit nor a loss). Hence, there are no profitable time units.

Example input 2:
3
2 1 0.65
1 2 1.54
0 1 6.92
2 0 0.11
1 2 1.44

Output for the example input 2 (for goal #1):
3

Output for the example input 2 (for goal #2):
4

Explanation: At time unit 2, a trivially profitable exchange (stock 1 stock 2 stock 1
yields a small profit). This exchange remains possible at time units 3 and 4 as well. At time
unit 5, however, this exchange is no longer profitable. However, another profitable
sequence now exists (stock 0 stock 1 stock 2 stock 0), so time unit 5 is also
profitable (but not trivially profitable).
Getting started
To help you get started, we are giving you the following resources (available at
http://mlxstorage.blob.core.windows.net/mec-v2/AlgoRhythm2014.zip):
1) C code AlgoRhythm.c: This file contains code to read one input file (in the format
described above). After reading the first line, a function init(n) is called, which you
can modify. As each subsequent line is read, the function info(i, j, k) is called.
You must modify this function so that it returns 1 if the current time unit after getting
information (i, j, k) is profitable, and returns 0 otherwise. You can define your own
helper functions, etc. The given code counts the number of profitable time units and
prints the answer.
2) Three simple test cases: Three text files representing small inputs are given. The
correct answers for these inputs is part of each file name.

Required Steps & Deadlines

15 April 2014: Send us a feedback form. Ask your teacher to do a discussion in class, form
teams (each team can have 1 to, at most 4 people), and register the teams by deadline: 15
April 2014 by sending email to mecfeedback@microsoft.com with the following template

College name:
Teacher name:
Number of teams:
For each team, names of team members with email addresses:

15 May 2014: Have the teacher send us the following entries per team.
Each entry should consist of a zip file with source code, as well as an executable, and a
README file which shows how to run the executable.
The executable should run on any Windows machine.

31 May 2014: Who wins the contest?
Your code will first be tested for correctness using small example inputs similar to the ones
given above. Next, all teams that pass the correctness tests will compete against each other
with large test inputs. The winning team will be the one that performs fastest (on average)
across all large tests. To ensure fairness, we will not reveal all our test inputs, nor what we
mean by small and large. Your code should work correctly for all values of n in the range
1 to 10,000, and up to 1 million time units.

The winners will be declared by 31 May, 2014. The winning team(s) will be chosen
by the MEC Team and Faculty and rewarded suitably, and their decision will be final
and binding.