Computer Science 320SC – (2023)
Programming Assignment 3
Due: Friday Sept 1st or Friday Sept 8th (11:59pm)
Requirements
This assignment tests you understanding of how to apply network flow to a real-world application. We
have taken a recent New Zealand Programming Contest question and repackaged it for your requirements. See the following two pages for specifications.
Submission
There will problem two sets of inputs Easy and Hard worth 3 and 2 marks, respectively, on the computer
science automarker https://www.automarker.cs.auckland.ac.nz/. It is expected that you will need
a network flow solution for the harder test case.
For this assignment you can use any language supported on the automarker and can submit up to
10 times for each problem before occuring a 20% penalty. Then a maximum of 20 times to prevent
overloading of the server.
Also, as a bonus, if you finish both parts of the assignment before the first deadline of Sept 1st, you will
get 10% added to your Assignment 3 score (e.g. 5.5 marks), which will be manually added to Canvas.
You need to have solved both test sets to qualify.
1
NZPC2023 MOLECULES
Organic molecules can be amazingly complex and need a great
variety of shapes and conventions to represent them,
particularly if we wish to depict details of their 3-dimensional
structures. For this problem, we will restrict ourselves to
reasonably simple compounds with only single bonds between
atoms, that can be represented on a simple rectangular grid
with bonds aligned horizontally or vertically. In such molecules,
carbon is bonded to 4 adjacent atoms, nitrogen to 3, oxygen to
2 and hydrogen to 1. These numbers are called the valences of
the atoms.
Of course, not all such grids represent valid molecules. Your task is to write a
program that will determine whether a given grid could represent one or more valid
molecules, satisfying the valences of all the atoms. Note that the molecule(s) in a
valid grid do not need to exist in the real world.
Input
The first line of the input consists of a pair of integers (r and c, 1 ≤ r, c ≤ 20) representing
the number of rows and columns in the rectangle to follow. The next r lines contain c
characters each, where the characters are chosen from the set {‘H’, ‘O’, ‘N’, ‘C’, ‘.’}
representing hydrogen, oxygen, nitrogen, carbon and ‘empty’, respectively.
Output
Output consists of a single line containing a single word:
Valid if it possible to draw horizontal and/or vertical bonds between
neighbouring atoms so as to satisfy the valences of all the atoms in the grid, or
Invalid if no such set of bonds exists.
New Zealand Programming Contest 2023
Sample Input #1
3 4
HOH.
NCOH
OO..
Output for Sample Input #1
Valid
Explanation
A valid bonding is:
H O—H
| |
N—C—O—H
| |
O—O
Sample Input #2
3 4
HOH.
NCOH
OCNH
Output for Sample Input #2
Invalid
Sample Input #3
2 3
HOH
HOH
Output for Sample Input #3
Valid
Explanation
This could represent two water
molecules:
H—O—H
H—O—H
Sample Input #4
4 10
OOOONOOOOO
OOOOHOOOOO
OOOHNHHOOO
OOOOOOOOOO
Output for Sample Input #4
Invalid