Table of Contents

ExplanationImplementation

Explanation

The formula given for adding an edge may seem a little weird, but the key observation is that we can turn it into the following with some algebraic manipulation:

i−ai=j−aji-a_i=j-a_j

From this we can give each node an "ID" of sorts, and only nodes with identical IDs can be linked. In other words, our overall graph will consists of a bunch of sets of nodes that are all pairwise connected.

Within these groups of nodes, we try to match as many pairs that have positive weight as possible. There's many ways to do this; in my implementation I sorted them in descending order and matched all adjacent pairs.

Implementation

Time Complexity: O(nlog⁡n)\mathcal{O}(n \log n)

C++

#include <algorithm>
#include <iostream>
#include <map>
#include <vector>


using std::cout;
using std::endl;
using std::vector;


int main() {

Java

import java.io.*;
import java.util.*;


public class Matching {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int testNum = Integer.parseInt(read.readLine());
		for (int t = 0; t < testNum; t++) {
			read.readLine();
			int[] arr = Arrays.stream(read.readLine().split(" "))

Python

for _ in range(int(input())):
	input()
	arr = [int(i) for i in input().split()]


	groups = {}
	for i in range(len(arr)):
		id_ = i - arr[i]
		if id_ not in groups:
			groups[id_] = []
		groups[id_].append(arr[i])

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum