Friendlist

Let's solve Friendlist.

Let's start by summarizing problem: You're given a list of friendship pairs and would like to print out the IDs of the players with the most friends, in ascending order.

What data should we store?

Firstly, we need to work out how we want to store the data. There are many options on what to do here. One important (but simple) realization is that we aren't interested in who is friends with who exactly, rather we are only interested in how many friendship pairs each person is part of. Thus, it makes sense for us to create a list nCount, where nCount[i] will store the number of friends that player i has. We can calculate this list as follows:

• Python 3
• C++

# TODO: Read in the integer f
for i in range(f):
    # TODO: Read in the i-th friendship pair a b
    nFriends[a] += 1
    nFriends[b] += 1

// TODO: Read in the integer f
for(int i = 0; i < f; i++) {
    // TODO: Read in the i-th friendship pair a b
    nFriends[a]++;
    nFriends[b]++;
}

It's always important to think through some of the edge cases:

• What happens if a friendship pair is listed twice?

  Fortunately, the problem statement guarantees that each friendship pair is listed once only.

• Is 0 a valid player ID?

  The statement says "All player IDs are integers between 0 and 1000 inclusive." which tells us that 0 can indeed be a valid ID. Even if you missed it, you can check the sample input, which also shows that 0 is a valid ID.

• Can someone be friends with themselves?

  The statement doesn't clarify if a pair like 5 5 could appear in the input. One could argue both that it does and does not make sense to be friends with yourself. Ideally, the statement should make it clear if we could receive input like this (spoilers: we can't), but at least the ambiguity gives us an opportunity to learn about asserts. Asserts take the form assert(condition). If condition is true, then your code proceeds as normal. If condition is false, it will cause your code to crash immediately.

  • Python 3
  • C++

  # TODO: Read in the integer f
  for i in range(f):
      # TODO: Read in the i-th friendship pair a b
      assert(a != b)
      nFriends[a] += 1
      nFriends[b] += 1

  #include <cassert> // we need this #include to use assert
  // TODO: Read in the integer f
  for(int i = 0; i < f; i++) {
      // TODO: Read in the i-th friendship pair a b
      assert(a != b);
      nFriends[a]++;
      nFriends[b]++;
  }

  In this way, we can check when we submit our code if our assumptions held true (assuming our code doesn't crash for other reasons).