Initial sample solution for Kattis problem

[avborup]

This issue outlines our initial, basic version of the problem.

Description

A band is performing at this year's Copenhell, and to finish off their concert in style, they would like to crowdsurf from the stage all the way from the stage to the back of the crowd.

However, the band is not sure that the crowd will be able to carry all of them through. They're unsure how strong the people in the crowd are, so to be sure, each person in the crowd would have to carry at most one band member over the course of the crowdsurfing.

The people in the crowd will only pass band members to other crowd members behind them - that is, people further away from the scene than themselves.

Input

4 9 3
.###..#.#
..#..##.#
#....##.#
..#...##.

• First line contains three numbers: $r$, $c$, $b$
  • $r$: the number of rows
  • $c$: the number of columns
  • $b$: the number of band members
• Then follow $r$ lines with $c$ characters
  • Each character indicates whether a person is standing there # or if nobody is there to carry ..
  • The first row shows the people closest to the scene, and the last row shows the people furthest from the scene.

Output

The number of band members not able to crowdsurf. I.e. how many band members remain standing on the stage.

Expected output for above input is 1. Two band members can surf the two rightmost paths. The remaining band member has nowhere to surf.

Intended solution

Number of node-disjoint paths, calculated using a maximum flow algorithm.

[avborup]

Ideas for extensions:

• Allow band members to be passed off in any direction. That is either of the 8 surrounding tiles.
• Each crowd member has a carrying capacity, and the band members weigh something. Have to filter out which crowd members are able to carry.
  • Can make more complex: all band members have their own weight. They are not allowed to be cut in pieces.
• Each crowd-member is represented by a number between 0 and 2 showing how many cups of beers they are currently carrying. If you have 2 cups of beers, you have no hands free to carry a band member. If you have 0 cups of beers, you have two free hands and can carry a band member by yourself. If you have 1 cup of beer you have one free hand, and need a neighbour with one hand free to carry a band member with you.

[AMB-F]

Some very simple input/output

Basic one row

Input:

1 9 10
...###...

Answer: 7

Basic two row

Input:

2 9 20
...###...
....#....

Answer: 19

Full crowd

Input:

3 6 3
######
######
######

Answer: 0

Empty crowd

input:

3 6 3
......
......
......

Answer: 3

Two paths join

Input:

3 3 3
#.#
#.#
.#.

Answer: 2

Simple straight line

Input:

3 3 3
.#.
.#.
.#.

Answer: 2

Simple diaginal (examples of both directions)

Diagonal rightwards

Input:

3 3 3
#..
.#.
..#

Answer: 2

Diagonal leftwards

Input:

3 3 3
..#
.#.
#..

Answer: 2

[JoachimBorup]

To catch solutions that scale with the number of possible entry points or exit points. Hidden cases with huge inputs, that look something like the cases below:

Many-to-few:

Input:

5 9 5
#.#.#.#.#
.###.###.
..#.#.#..
...###...
....#....

Answer: 4

Few-to-many:

Input:

5 9 5
....#....
...###...
..#.#.#..
.###.###.
#.#.#.#.#

Answer: 4

Many-to-many:

Input:

5 9 5
#.#.#.#.#
.###.###.
..#.#.#..
.###.###.
#.#.#.#.#

Answer: 2

[AMB-F]

Feedback from TA

Input Use the 0,1,2 beers idea for crowdmembers and have every bandmember weigh 1 Might need something else than the grid, so IO does not take too long. We need input large enough that the optimal flow algorithm is the only solution that can give full points, the problem should not be solvable just using greedy

Some options for grading groups Input size Carrying capacity of crowd (all 0, all mixed) Complexity of hand-over (always moving away form stage or mix) Number of band members (1 or many)

Look at running times for the different flow algorithms and chose the one optimal for our input