2004 ACM Programming Competition

From ProgSoc Wiki

Jump to: navigation, search

About

The UTS Programmers' Society is pleased to announce that we will be participating in the 2004 ACM programming competition. ACM has a worldwide programming competition every year, in which teams of programmers compete to solve a set of problems. A team of three students uses one computer to solve eight hard problems in five hours using either C, C++, or Java.

FIT is providing a $500 prize to the top UTS team.

Chris Johnson and Robert Rist are the staff advisors and will run a series of training sessions based on past problems.

For more details see the initial announcement. If you'd like to take part, come along to our next meeting. We won't form teams until later, so feel free to come as you are.

Initial announcement

The UTS Programmers Society is pleased to announce that we will be participating in the 2004 ACM programming competition. ACM has a worldwide programming competition every year, in which teams of programmers compete to solve a set of problems. A team of three students uses one computer to solve eight hard problems in five hours using either C, C++, or Java. A university can enter any number of teams; all teams must have a registered staff advisor.

The competition goes through three levels: regional, national, and world. At the regional level, a team from UTS would compete against other teams from the local universities, such as Sydney, UNSW, and UWS. The winners then fight it out with a team from each state in Australia, and the winners of that contest go to the finals. Last year, the finals were held in Prague, and a team from St. Petersburg (Russia) won. The competition website is http://icpc.baylor.edu/past/default.htm

FIT is going to pay to enter a number of teams into the competition and progsoc is going to provide the team members, support and infrastructure (mailing lists, servers etc).The regional contest will probably be held at UNSW about September, so that leaves the rest of this semester and the first half of next semester for preparation.

Chris Johnson and Robert Rist will be the staff advisors and will run a series of training sessions based on past problems.

If you would like to sign up to be on a team or want more information please contact Myles Byrne (myles@progsoc.org). Unfortunately this competition is only available to current UTS students so progsoc alumni members are not eligible to enter.

Next meeting

Tuesday July 6, 13:00 - 15:00, in 10/2.240

We are considering Problem E in the 2000 competition.

We have now finished phase 1 of the preparation, and will break for exams. In phase 2, students will design and code one solution in the two hour slot.

Minutes of meeting Tuesday 25 May

Rist provides a solution.

Goal: assemble one chain with the minimum number of cuts

Terminology:

In this domain the agent of the graph is known as a "link", which name a lot of people use as a synonym for "edge", so let's just be hardline about it and use "node" for the bits of chain and "edge" for the (conceptual) joins between them.

Tricksy bits of this problem, as I see it, and observations:

  • If you open a single node, it can be used to join up three chains (including itself).
  • This generalises to longer chains, giving you "free" joins by entirely "using up" a chain
  • Because singletons are so wonderful, every time you cut open a node you may as well store it independently of the chain it came from
  • If you have a choice between several chains to cut free, cut the smallest because it's easier to "use up"
  • Obviously, when it comes time to join chains up at the end, first use up the open singletons then start cutting up the smallest chains
  • You can only find the smallest chains to cut by starting at the tree leaves. Allegedly you can start at the tree head and get the same result by "tail recursion" but why do something more conceptually difficult to achieve the same result?
  • A concept of "direction" within chains helps; we can be gravity-inspired and start at the "top" working "down".
  • The reason you get both a node count and a termination token in the data is because singleton nodes can be inferred without being explicitly listed.
  • The data can represent two nodes being linked to each other in both directions, but this isn't physically possible (except with some improbably-shaped nodes) so it should be checked for and ignored.

Node representation wrinkles: we can assume that the input would not contain patterns like "1 2_ 2 3_ 3 4_ 5 6_ 6 3" that make it hard to spot separate chains. There are singleton nodes not explicitly specified in the input

Chain structure types:

  • cycles:
  • trees:
  • single chain: each node connected to two nodes except ends which are connected to one

Think about: data structure
OR
algorithm: start with key or focal idea

Data structure:

  • list of nodes
  • nodes joined in chains by edges
  • list of chains

node: id
links "above"
links "below"
open/closed

cycle: node has been visited before; cut next
tree: |top+bottom| > 2; cut next until no more tree

can be a sequential algorithm: for all chains, first cut all cycles then cut all trees
Cutting a cycle adds a singleton to the list of chains, cutting a tree adds a singleton and a chain

Minutes of meeting Tuesday 18 May

Yusuf Pisan provides two non-working solutions for you to fix. The output from both looks correct but bartjensDList times out for the "online judge" and bartjensArray is reported to provide the wrong answer. Sample input and output provided.


Find Bartjens at http://acm.uva.es/problemset problem #817.

Task: place operators between numbers

Restrictions:

  1. operators are +, -, *
  2. no leading zeros before numbers
  3. operators must be separated by numbers
  4. terminate on '=' sign
  5. number of digits: 1 - 9, so a maximum of 8 operators, so a maximum of 4^{8} cases

Considerations:

  • We can treat the "null" operator as "concatenation" instead, which means we can avoid exhaustively finding all possible number tokens.
  • We'd like to avoid calculating all the possible cases in advance, since this takes lots of storage
  • We'd like to avoid copying or changing the data representing the case, since this takes time

It turns out that a "concatenation" operator removes a lot of mess from the problem, but adds some mess of its own. I wrote a solution in Python (not ready for Java yet) that uses a "copy and manipulate" approach, rather than the superior "look at the data, work on the stack" approach, to avoid having to think about the mess. It's too slow.

Minutes of meeting Tuesday 11 May

Rist's mostly complete solution is available for participants to examine and complete.

Daniel Shoon provides a C++ solution.


This problem is a graph search. We need to build a data structure and then search it. The heart of the problem is the search algorithm.

For inspiration, try searching the data structure by hand.

Graph search: start at (3,1), stop when you reach (3,3).

The concept of "next links" is defined on links, not nodes.

Link:
        start: Node
        end: Node
        next: [Link]
        prev: Link   # set and updated by traversing algorithm, see below

Node:
        row, col: int
        in: [Link]   # unused
        out: [Link]  # unused

Initial exploration of the problem:

Problem: graph may contain cycles
Solution: keep list of visited links

Problem: shortest path required
Solution: store depth?

Problem: must actually return the path
Solution: keep a history? recalculate the path once the end node is found?


Open/closed is a graph search strategy, that can be adapted to this problem. Presented here in faux Python.

open = [start]
closed = []
until open[0] == end or not len(open):
      expand(open[0])
if len(open):
   # soln
else:
   # no soln

def expand(link):
    for ln in link.next:
        if not ln in closed:
           ln.previous = link
           open += link
    open.remove(0)
    closed += link

Storing the "previous" link in each link visited makes it easy to calculate the path once the end node is reached. We also get some other stuff for free, like guaranteed shortest path, cycle avoidance and solution/no solution detection. Minutes of meeting Tuesday 4 May The basic competition format is 3 people, 5 hours, 8 problems.

Schedule and time commitment:

May 4 - June 14:
2-3 hours a week
1 problem per week for teams to think about and Rist to solve as walkthrough

July 5 - Aug
Split into potential teams
4-6 hours per week
1-2 problems a week for teams to solve

Aug - Sep 18
5-10 hours per week
Teams formed
Time trials in teams

Prizes:
UTS will probably provide a prize for the top UTS team
Progsoc also to pony up prizes of some sort
Personal tools