LogoLogo
  • CP Gymnasium
  • Week 3 Math / Number Theory
    • Week 3 Math / Number Theory
      • Problem 1: Tetration
      • Problem 2: Peragrams
      • Problem 3: Veci
      • Problem 4: Architecture
      • Problem 5: Joint Attack
      • Problem 6: How Many Digits?
      • Problem 7: Abstract Painting
  • Week 4 Array / Greedy
    • Week 4 Array / Greedy
      • Problem 1: Vaccine Efficacy
      • Problem 2: Frosh Week
      • Problem 3: Inquiry
      • Problem 4: Bank Queue
      • Problem 5: Log Land
  • Week 6 Sorting / Binary Search
    • Week 6 Sorting / Binary Search
      • Problem 1: Falling Apart
      • Problem 2: Synchronizing Lists
      • Problem 3: Distributing Ballot Boxes
      • Problem 4: Financial Planning
      • Problem 5: Big Boxes
  • Week 7 Dynamic Programming
    • Week 7 Dynamic Programming
      • Problem 1: Ocean's Anti-11
      • Problem 2: Batmanacci
      • Problem 3: Radio Commercials
      • Problem 4: Welcome to Code Jam (Hard)
      • Problem 5: Honeycomb Walk
  • Week 8 Graph Traversals
    • Week 8 Graph Traversals
      • Problem 1: Reachable Roads
      • Problem 2: Money Matters
      • Problem 3: Squawk Virus
      • Problem 4: Beehives
      • Problem 5: Running MoM
      • Problem 6: Amanda Lounges
Powered by GitBook
On this page
  1. Week 8 Graph Traversals
  2. Week 8 Graph Traversals

Problem 2: Money Matters

https://open.kattis.com/problems/moneymatters

We are given that we are dealing with a splintered group of friends, so we can anticipate that this graph is not going to be connected. This is another connected components problem, but with a twist! Each node has a weight - the amount of money a person owes or is owed - and we want each person to be able to exchange this weight with people they are connected to so that everyone ends up with zero money owed.

In other words, the sum of weights over a connected component should equal zero!

So, to solve, you must traverse through all of the connected components, summing up the values at the nodes. If you complete your traversal through the connected component and the sum is anything but zero, their task is impossible.

How do I traverse through Connected Components?

Just use your favorite graph traversal method!

Start from some node, and if there are still unvisited nodes when your B/DFS terminates, there are still connected components for you to explore, so call B/DFS again (on an unvisited node).

PreviousProblem 1: Reachable RoadsNextProblem 3: Squawk Virus

Last updated 4 years ago