This was a 200-point challenge, and the description of the challenge was as follows:

We have a lot of friends because we’re super popular, but unfortunately we have to split our set of friends into two halves so they can go into war with each other. That’s just life, unfortunately.

We have a set of N friends, and M pairwise connections between friends. Each connection goes both ways, so if, for example, Aariss Weiron is friends with Bendelman, then Bendelman is also friends with Aariss Weiron. Each connection also has an associated weight, representing how close the two friends are, which is a positive integer value. No two pairs of friends with a connection have the same weight.

Our objective is to somehow divide our set of friends into two ‘equal’ halves. We also want to put friends who are pretty close to each other into the same set. We formally define the problem as follows:

We have a set of friends of even size, some with bi-directional pairwise connections. Each connection has a positive integer weight, and each connection has a distinct weight. Our objective is to divide our friends into two sets of equal size with this property: The largest connection-weight that crosses between the two sets should be as small as possible. Compute this connection-weight for each friend network given. A crossing connection is one such that the two friends it connects are in different sets. Each friend network is in the following format: The first line has two numbers:

N (guaranteed to be even) and M (number of connections). M lines follow this line. Each one represents a connection and has three tokens. The first two are the friends it connects, and the last one is the weight of the connection.

This problem has some similarity with a well-known problem called , in which case you are to minimize the sum of all weights in a cut dividing the graph in two. The optimization problem is NP-hard (later in this post, I will also show you code to approximate that problem). The difference with the problem ‘Space Friends’ is that we do not care about the sum, but only the maximum.

The general idea is as follows: Let be then maximum weight over all edges. Pick a number such that and start with the two nodes connected with the highest weight . Now, color all neighbors of the two nodes having connection weight . Repeat for all previously colored nodes, until the no more nodes are to be colored. We know that if we were to split this subgraph in any way, the weight of at least one edge would be at least .

If the size of the graph is larger than half of the total number of nodes we increase , otherwise we decrease it. For this procedure, we may speed it up using binary search. Once we have found a subgraph with nodes, we may stop. Any other edge connecting this subgraph must necessarily be smaller than . We may now find the maximum weight by looking at the outgoing edges from . This is the sought value.

Embodied in Python, the code may be as follows:

import networkx as nx
import sets

def get_set(node, graph, gset, w):
    # add node to set i.e., mark as visited
    gset.add(node)

    # visit all neighbors connected with weight >= w
    for neighbor in graph[node]:
        if neighbor not in gset and graph[node][neighbor]['weight'] >= w:
            get_set(neighbor, graph, gset, w)

#create graph
graph = nx.Graph()

list_of_nodes, list_of_edges = [], []
max_weight, start_node, num_nodes = 0, -1, 0
networks = ['network1.txt','network2.txt','network3.txt','network4.txt']

# read in the nodes from the first network
f = open(networks[0],'r')

print "[ ] Reading data..."

for line in f:
    if len(line.split()) > 2: # skip first line
        # parse the line, ssv
        node1 = int(line.split()[0])
        node2 = int(line.split()[1])
        weight = int(line.split()[2])
        max_weight = max(max_weight,weight)
        if weight == max_weight: start_node = node1

        # add edge
        list_of_edges.append((node1,node2,weight))

        # make sure every node is added exactly once
        if node1 not in list_of_nodes: list_of_nodes.append(node1)
        if node2 not in list_of_nodes: list_of_nodes.append(node2)
    else:
        num_nodes = int(line.split()[0])

# add nodes
graph.add_nodes_from(list_of_nodes)
graph.add_weighted_edges_from(list_of_edges)
graph.graph['edge_weight_attr'] = 'weight'

# pivot in the middle
pivot = max_weight/2
i = 1

print "[ ] Searching..."

# binary search
while True:
    # create new set
    right_set = set()
    right_set.add(start_node)
    i += 1
    # visit graph
    get_set(start_node, graph, right_set, pivot)

    if len(right_set) == num_nodes/2: break
    if max_weight/2**i == 0: break
    if len(right_set) > num_nodes/2: pivot += max_weight/2**i
    if len(right_set) < num_nodes/2: pivot -= max_weight/2**i

highest_outgoing_weight = 0

# get the max-weight outgoing edge
for node in right_set:
    for neighbor in graph[node]:
        if neighbor not in right_set and highest_outgoing_weight < graph[node][neighbor]['weight']:
            highest_outgoing_weight = graph[node][neighbor]['weight']

print "[+] Found maximum weight:", highest_outgoing_weight

This gives us the flag sctf{43226;9474;40749;750}. Cool 🙂

Now, let us consider the second (NP-hard) problem. Now, we cannot look at a single connection, but the sum of all connections. We use the METIS software for this purpose. The algorithm in METIS is non-deterministic, so we will run it many times to amplify the probability of finding a good cut.

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
import metis

ITERATIONS = 20 # how many successful iterations?

#create graph
graph = nx.Graph()

list_of_nodes, list_of_edges = [], []

# read in the nodes from network1.txt
f = open('network1.txt','r')

for line in f:
    if len(line.split()) > 2: # skip first line

        # parse the line, ssv
        node1 = int(line.split()[0])
        node2 = int(line.split()[1])
        weight = int(line.split()[2])

        # add edge
        list_of_edges.append((node1,node2,weight))

        # make sure every node is added exactly once
        if node1 not in list_of_nodes: list_of_nodes.append(node1)
        if node2 not in list_of_nodes: list_of_nodes.append(node2)

# add nodes
graph.add_nodes_from(list_of_nodes)
graph.add_weighted_edges_from(list_of_edges)
graph.graph['edge_weight_attr'] = 'weight'

seed = 3000 # deterministic seed
best_cut = -1
iterations = 0

print "[ ] Running METIS... "

while iterations < ITERATIONS:
    # find weight minimum bisection
    (edgecuts, parts) = metis.part_graph(metis.networkx_to_metis(graph), \
                        nparts=2, rtype='sep2sided', recursive=True, seed=seed)
    # make sure the cut divides the set perfectly
    if sum(parts) == len(parts)/2:
        iterations += 1
        if edgecuts < best_cut or best_cut < 0: best_cut = edgecuts
    seed += 1

print "[+] Found two partitions with cut-value", best_cut