[go: up one dir, main page]
Scribd
Upload
63 views29 pages

4 Sum

This document describes an algorithm to find four integers from given sets that sum to 0. It explains that the sum of the first two integers must equal the negative sum of the last two. It then details the steps: listing all possible sums of the first two sets and negatives of the last two sets, and finding the number present in both lists. An example is provided to demonstrate the algorithm.

Uploaded by

Wang Zerui
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
63 views29 pages

4 Sum

This document describes an algorithm to find four integers from given sets that sum to 0. It explains that the sum of the first two integers must equal the negative sum of the last two. It then details the steps: listing all possible sums of the first two sets and negatives of the last two sets, and finding the number present in both lists. An example is provided to demonstrate the algorithm.

Uploaded by

Wang Zerui
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 29

PRIME

LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Problem

In this task, you are provided with four sets of integers. Your task
consists of selecting one integer from each set, such that their sum
is 0. You can assume that exactly one such selection exists.

Martin Henz NOI 2008—Solutions to Contest Tasks 78


PRIME
LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Input File

3 2 4 2
5
17
-8
-13
19
6
-9
10
0
-14
7

Martin Henz NOI 2008—Solutions to Contest Tasks 79


PRIME
LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Input File

3 2 4 2
5 |
17 |
-8 |
-13 |
19 |
6 |
-9 |
10 |
0 |
-14 |
7 |

Martin Henz NOI 2008—Solutions to Contest Tasks 80


PRIME
LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Output File

17 -13 10 -14

Martin Henz NOI 2008—Solutions to Contest Tasks 81


PRIME
LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Algorithm

Idea
In order for the overall sum to be 0, the sum of the first two values
must be minus the sum of the last two values.

Procedure
List the sums of all possible first two values, and the negatives of
the sums of all possible second two values.

Martin Henz NOI 2008—Solutions to Contest Tasks 82


PRIME
LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Algorithm

Idea
In order for the overall sum to be 0, the sum of the first two values
must be minus the sum of the last two values.

Procedure
List the sums of all possible first two values, and the negatives of
the sums of all possible second two values. Then find the place
where the two lists have same value.

Martin Henz NOI 2008—Solutions to Contest Tasks 83


PRIME
LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Example

First value: 5,17,-8


Second value: -13,19

Martin Henz NOI 2008—Solutions to Contest Tasks 84


PRIME
LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Example

First value: 5,17,-8


Second value: -13,19
Possible sums: -8

Martin Henz NOI 2008—Solutions to Contest Tasks 85


PRIME
LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Example

First value: 5,17,-8


Second value: -13,19
Possible sums: -8, 24

Martin Henz NOI 2008—Solutions to Contest Tasks 86


PRIME
LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Example

First value: 5,17,-8


Second value: -13,19
Possible sums: -8, 4, 24

Martin Henz NOI 2008—Solutions to Contest Tasks 87


PRIME
LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Example

First value: 5,17,-8


Second value: -13,19
Possible sums: -8, 4, 24, 36

Martin Henz NOI 2008—Solutions to Contest Tasks 88


PRIME
LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Example

First value: 5,17,-8


Second value: -13,19
Possible sums: -21, -8, 4, 24, 36

Martin Henz NOI 2008—Solutions to Contest Tasks 89


PRIME
LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Example

First value: 5,17,-8


Second value: -13,19
Possible sums: -21, -8, 4, 11, 24, 36

Martin Henz NOI 2008—Solutions to Contest Tasks 90


PRIME
LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Example

Third value: 6, -9, 10, 0


Fourth value: -14, 7

Martin Henz NOI 2008—Solutions to Contest Tasks 91


PRIME
LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Example

Third value: 6, -9, 10, 0


Fourth value: -14, 7
Possible negative sums: 8

Martin Henz NOI 2008—Solutions to Contest Tasks 92


PRIME
LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Example

Third value: 6, -9, 10, 0


Fourth value: -14, 7
Possible negative sums: -13, 8

Martin Henz NOI 2008—Solutions to Contest Tasks 93


PRIME
LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Example

Third value: 6, -9, 10, 0


Fourth value: -14, 7
Possible negative sums: -17, -13, -7, 2, 4, 8, 14, 23

Martin Henz NOI 2008—Solutions to Contest Tasks 94


PRIME
LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Example

Find match between sorted lists:


Possible positive sums: -21, -8, 4, 11, 24, 36
Possible negative sums: -17, -13, -7, 2, 4, 8, 14, 23

Martin Henz NOI 2008—Solutions to Contest Tasks 95


PRIME
LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Example

Find match between sorted lists:


Possible positive sums: -8, 4, 11, 24, 36
Possible negative sums: -17, -13, -7, 2, 4, 8, 14, 23

Martin Henz NOI 2008—Solutions to Contest Tasks 96


PRIME
LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Example

Find match between sorted lists:


Possible positive sums: -8, 4, 11, 24, 36
Possible negative sums: -13, -7, 2, 4, 8, 14, 23

Martin Henz NOI 2008—Solutions to Contest Tasks 97


PRIME
LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Example

Find match between sorted lists:


Possible positive sums: -8, 4, 11, 24, 36
Possible negative sums: -7, 2, 4, 8, 14, 23

Martin Henz NOI 2008—Solutions to Contest Tasks 98


PRIME
LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Example

Find match between sorted lists:


Possible positive sums: 4, 11, 24, 36
Possible negative sums: -7, 2, 4, 8, 14, 23

Martin Henz NOI 2008—Solutions to Contest Tasks 99


PRIME
LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Example

Find match between sorted lists:


Possible positive sums: 4, 11, 24, 36
Possible negative sums: 2, 4, 8, 14, 23

Martin Henz NOI 2008—Solutions to Contest Tasks 100


PRIME
LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Example

Find match between sorted lists:


Possible positive sums: 4, 11, 24, 36
Possible negative sums: 4, 8, 14, 23

Martin Henz NOI 2008—Solutions to Contest Tasks 101


PRIME
LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Example

Find match between sorted lists:


Possible positive sums: 4, 11, 24, 36
Possible negative sums: 4, 8, 14, 23
Bingo!

Martin Henz NOI 2008—Solutions to Contest Tasks 102


PRIME
LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Complexity

We need to calculate all possible sums of the first two numbers


and all possible sums of the second two numbers.

Martin Henz NOI 2008—Solutions to Contest Tasks 103


PRIME
LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Complexity

We need to calculate all possible sums of the first two numbers


and all possible sums of the second two numbers.
The amount of work to be done grows with the square of the list
size.

Martin Henz NOI 2008—Solutions to Contest Tasks 104


PRIME
LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Complexity

We need to calculate all possible sums of the first two numbers


and all possible sums of the second two numbers.
The amount of work to be done grows with the square of the list
size.
Then we need to sort the two lists, incurring an amount of work
that grows with the square of the list size times the logarithm of
the square of the list size.

Martin Henz NOI 2008—Solutions to Contest Tasks 105


PRIME
LVM
Problem
GECKO
Algorithm
HOUSING
Java Program
RANK
4SUM

Complexity

We need to calculate all possible sums of the first two numbers


and all possible sums of the second two numbers.
The amount of work to be done grows with the square of the list
size.
Then we need to sort the two lists, incurring an amount of work
that grows with the square of the list size times the logarithm of
the square of the list size.
This turns out to be equivalent to saying: The amount of work
grows with the square of the list size times the logarithm of the list
size.

Martin Henz NOI 2008—Solutions to Contest Tasks 106

You might also like