UVa 196

From Algorithmist
Jump to navigation Jump to search

196 - Spreadsheet[edit]

Summary[edit]

At the first glance this is a straightforward task, you just need to replace formulas from the input with numbers. In fact, there is an underlying problem from Graph Theory: topological sort.

Explanation[edit]

We present a simple iterative solution. All you need to do is: load integers and formulas, replace formulas with numbers according to the numbers they point to and print output. Processing of one sheet will look as follows:

  1. Load up m and n.
  2. Create 2-dimensional m*n field of Integers. (class Integer, not type int)
  3. Create 1D m*n field of Strings. (Since UVa didn't allow Vector or List, i had to use the static way.)
  4. For each line of input:
  5. Load line of input as String.
  6. Parse that String using StringTokenizer.
  7. For each token:
  8. If the parsed token is a number, place it in the corresponding space in 2D field.
  9. If the parsed token is a formula (starts with '='), transform formula into some more readable form.
  10. (Example: formula A3 = A2+A1 looks in my program as 3 1 2 1 1 1. Rows first, columns second.)
  11. Place modified formula into 1D field of Strings and null into corresponding space in 2D field .

Now that we have all input loaded:

  1. Browse through that 1D field of formulas and check them. For each formula, check whether you know all values it points to (all formula members pointing to 2D field have non-null value). If you do, fill target 2D space with corresponding value and remove that formula from 1D field. If not, skip it and continue with another one.
  2. Repeat until there's no formula left.
  3. Print output.


A more effective solution than the one above would build a graph giving the dependencies between cells. The graph says that for each cell the cells it depends on have to be filled before the cell in question can be computed. Thus if we process the cells in the topological order determined by the dependency graph, we will be able to fill all of them in the first pass.

Gotchas[edit]

Watch out for X and Y. Letter is column, number is line.

If you implement topological sort using depth-first search, beware of stack overflow.

Input[edit]

1
4 3
10 34 37 =A1+B1+C1
40 17 34 =A2+B2+C2
=A1+A2 =B1+B2 =C1+C2 =D1+D2

Output[edit]

10 34 37 81
40 17 34 91
50 51 71 172