Given n 2d vectors, you are to pick those which would get you furthest from (0, 0). I used the following properties -> t1 : vectors making up the max sum will be consecutive a circular list sorted by angle, t2-> anglespan of these vectors will be less than PI.
[EDIT]: I thought I had a solution, but it turned out buggy.
Knowing t1 and t2 O(n^2) solution is trivial, but not good enough.
Any help would be appreciated.
Maximum sum of n vectors -> in O(n lg n)
Moderator: Board moderators
Maximum sum of n vectors -> in O(n lg n)
Last edited by bakalar on Thu Sep 07, 2006 8:04 pm, edited 1 time in total.
Well, I was wondering if someone has seen it on any of the online judging systems. It's part of a private competition, and the formulation is not in English. Srry. The text is pretty much what I've said in post #1, and here is the example test case (input contains N<10000, and a pair of numbers on each of the N lines following; it's terminated by N = 0; output is maximum distance on a single line, two decimal places)
Input:
2
1.55 1.55
-2 -2
4
1 1
-2 -2
1 2
-2 5
0
Output:
2.83
8.00
Input:
2
1.55 1.55
-2 -2
4
1 1
-2 -2
1 2
-2 5
0
Output:
2.83
8.00
I've seen it in Google Code Jam Europe's practice room (it's unavailable now),
Apparently, this problem was offered at GICJ 2006: http://felix-halim.net/story/gicj06/eli ... ?prob=1000
Apparently, this problem was offered at GICJ 2006: http://felix-halim.net/story/gicj06/eli ... ?prob=1000
Yeah, that solution was ok in GCJ.So, im starting to doubt the O(n^2) algorithm, which basically makes a sorted circ. list and checks all possible subsets of consecutive elements. This ok?
Last edited by mf on Thu Sep 07, 2006 8:43 pm, edited 1 time in total.
What about this...
For some vector V you know until which vector U it grows (until degree between V and U is <= 90!?). Using Binary Search you can find U. Before looking for result you can find sum of first i vectors i = 1 .. N and in O(1) for each pair of vectors you can find max distance. It's n logn or I made mistake!?
For some vector V you know until which vector U it grows (until degree between V and U is <= 90!?). Using Binary Search you can find U. Before looking for result you can find sum of first i vectors i = 1 .. N and in O(1) for each pair of vectors you can find max distance. It's n logn or I made mistake!?
It wouldn't work for most of the following
Code: Select all
1
-8 -19
2
-13 -20
8 -4
3
17 16
8 13
-2 1
4
16 -7
-9 -3
3 7
16 -17
5
-19 14
18 20
-16 -10
8 7
11 -19
6
1 -5
8 -10
9 10
15 2
11 -6
-7 -9
7
9 -19
-10 4
6 4
15 -19
14 -7
5 -1
4 16
8
13 7
3 -10
0 -19
-19 -4
11 -7
13 5
-15 -11
-9 5
9
-4 -2
12 20
4 8
14 -9
-4 -18
-1 13
0 -3
-19 2
19 -5
10
-9 -4
8 1
11 16
16 -15
-16 -17
11 20
-18 3
-6 -10
-12 -5
19 -18
11
17 3
-10 -18
-11 0
10 -18
6 -5
11 -20
-7 -18
5 -6
-8 17
2 20
20 20
12
10 -17
20 6
6 -10
8 17
6 19
10 0
-8 -5
8 12
20 -9
-18 -19
0 -12
3 -4
13
-1 -19
3 11
-2 -20
-15 -5
14 10
19 -2
11 -15
12 -17
12 -1
18 16
15 3
-14 -17
18 17
14
-4 0
20 -15
-15 -11
16 15
-10 -3
12 11
2 -8
-11 14
-5 -1
-17 -18
-13 11
3 -20
18 19
-13 2
15
15 0
8 -18
14 14
17 -12
-9 -19
-12 7
-6 -3
0 18
-10 -15
-16 20
1 15
14 -1
-3 -14
-15 -13
5 3
16
12 -10
-2 -12
-7 14
20 -4
16 -17
-7 19
-15 -8
0 -2
-12 12
13 8
19 -5
19 15
5 12
-12 -1
-12 -8
-13 -10
17
-6 -18
6 10
11 -11
-10 -17
-7 3
4 -1
13 11
16 15
3 2
15 -6
-6 -7
14 -15
-16 -14
18 -13
-7 -15
11 -8
8 2
18
-10 7
13 -14
6 -10
-6 -17
-3 18
-11 14
-8 3
5 -4
-15 5
18 -17
-14 5
-10 5
9 -12
1 -16
-16 -13
4 -14
2 -16
-16 -2
19
10 -5
-4 12
-17 -15
-7 -12
16 15
13 13
6 5
-7 -17
-6 -20
20 -19
11 -2
-8 -19
11 -14
-17 -9
-19 16
1 -2
19 5
4 2
-9 -3
20
-15 -3
20 19
5 -4
12 0
6 -4
10 -14
17 -17
2 1
8 20
2 -3
-8 7
-16 17
-4 -3
-16 -2
-13 -7
18 -3
-6 -18
-2 -4
-4 14
-10 -3
21
4 9
14 20
-9 14
-13 -11
19 -4
7 -2
-10 17
6 -6
13 -1
-20 0
17 12
9 12
13 6
11 -12
-17 14
7 3
-13 18
1 14
-15 -5
19 18
19 6
22
2 -18
9 6
-7 19
-17 7
4 20
-20 -5
-13 -12
-4 -19
15 -3
-1 -8
4 8
3 8
0 14
15 1
2 3
6 1
13 20
13 8
-13 16
4 -10
-15 20
-12 -7
23
-17 19
-9 -11
3 -11
-12 -20
0 -12
-16 6
19 -10
9 -17
-3 -6
17 19
1 -11
2 19
-18 16
-19 -9
-19 -11
-10 -6
16 -4
14 -7
-19 -16
-9 2
20 -4
-13 -15
4 19
24
16 -20
0 16
-17 8
-13 -8
-12 -4
-8 -2
-4 13
16 -12
20 10
-11 -6
-2 -15
20 19
12 -8
13 9
-8 -19
-8 -8
-1 5
-20 -8
18 16
-1 12
-8 2
14 12
12 -4
4 -4
25
-13 -19
17 15
-15 2
14 -1
4 19
-2 12
8 7
-18 -19
-3 11
16 12
7 0
17 19
-11 14
-14 18
-9 -2
5 6
5 9
10 -14
-12 9
-11 -14
9 -5
11 -5
-14 -14
-9 9
-12 4
26
0 -20
-11 12
-19 -14
-14 -5
13 -6
-10 14
-16 -16
-4 11
-1 -18
-9 -11
3 -7
-16 17
18 5
2 4
17 -15
-8 17
-20 -16
-16 14
-4 -5
16 -12
15 -17
-2 18
-11 -4
-20 10
8 7
-3 -8
27
-17 -4
11 19
2 15
-6 4
13 -17
9 4
-8 -7
10 5
4 15
-10 7
-7 -5
-7 15
5 18
7 -6
-7 -20
-8 -19
-15 6
6 -17
-14 17
15 -1
-14 -11
-2 -9
1 17
-12 18
-5 -19
-10 -15
-19 -18
28
-17 3
9 5
-17 -3
15 0
-15 11
11 20
4 -8
8 -17
6 -20
9 17
-8 19
-6 -8
-10 13
-10 -20
-18 -13
-3 7
-17 1
0 -15
7 16
-13 -16
17 5
5 14
-19 4
-19 3
-8 2
15 -6
-7 -1
5 2
29
-6 -3
-10 -15
-8 -15
-3 12
19 13
-15 10
-9 14
-10 13
-19 3
-10 -17
-14 6
15 -9
2 20
11 8
19 -14
-19 2
12 -6
19 0
-15 -12
6 -7
10 10
16 19
-8 -1
-11 -10
-15 11
3 -17
0 2
8 -2
17 -18
30
-8 -9
6 -8
4 15
14 7
12 17
7 7
-5 17
18 8
-1 6
18 -5
5 -2
10 19
10 4
17 2
-10 11
-8 -10
10 6
5 -9
-8 -6
16 -11
4 8
8 13
-9 7
-3 6
8 -2
18 17
10 -15
7 -10
4 19
10 13
31
-11 9
16 -14
5 18
-17 -14
-11 11
0 19
-19 -9
-12 -13
16 5
-14 -15
8 -10
-14 -12
1 19
-16 13
-10 -14
-13 5
19 -13
-14 4
13 -16
6 -14
-15 18
12 7
3 16
-17 -15
5 -4
-11 0
-8 2
16 -8
-20 8
-2 9
-18 12
32
-3 -19
-12 0
2 18
-19 -11
16 -16
-9 -20
14 15
-5 -9
15 12
19 9
-1 -8
-19 14
-12 -20
-9 5
6 3
4 4
-14 18
9 3
-9 -5
-17 13
-11 -9
12 -10
-16 5
13 -16
-20 -15
6 -16
-7 20
15 18
-7 14
16 -12
-19 -10
0 5
33
-8 -7
3 -4
-14 -12
12 20
1 -17
20 -16
7 -15
11 6
-9 8
-8 -14
-7 5
13 10
-18 -8
18 1
-20 -1
-9 6
-1 14
10 -11
-5 14
-11 11
-14 11
0 -17
7 9
-2 -13
-20 1
-4 11
5 -10
10 6
5 2
6 -1
-20 -3
-1 16
8 9
34
-17 13
20 12
0 -19
-5 -6
-13 -2
4 1
2 0
2 9
-17 -18
17 -4
-5 13
-18 -19
-7 -5
-8 -15
10 2
2 20
-14 3
-4 -20
-17 -2
-17 -10
12 13
-14 -1
13 3
10 4
-10 11
-12 10
16 -18
-2 20
12 10
13 -4
20 14
11 -19
-18 -20
-18 -7
35
-20 -10
-14 6
-20 -2
0 -15
-3 14
3 -12
-12 -1
20 -3
-4 12
-16 20
-11 9
1 -15
-16 18
-17 18
-12 -2
-1 -10
2 0
-19 19
-9 18
-20 16
6 14
-11 -11
9 16
4 17
2 -5
-8 -5
17 -8
-18 -20
10 -15
7 -17
15 5
20 -4
-13 -15
11 16
3 18
36
-4 13
10 0
-16 -13
0 -18
-11 -14
7 2
-10 -6
17 -6
9 15
11 -3
8 -20
11 7
-14 -8
6 17
17 16
-16 8
-6 4
-15 -20
-13 19
-8 -15
11 -11
4 -9
16 -12
4 -14
-8 15
-19 -15
-9 -3
2 11
-7 15
-16 -1
9 -7
-12 -9
4 -8
-20 -2
18 -2
-1 7
37
-5 19
-18 13
8 16
-6 -15
14 -7
8 -6
9 1
17 1
18 -2
11 -3
16 5
-9 -17
-14 1
-8 -8
20 11
-17 10
-9 -15
-19 -2
14 -13
11 -7
15 -7
-2 -7
-14 -18
2 10
-12 -11
-5 12
-9 2
-19 -13
11 18
9 -15
-7 4
2 -16
-20 1
8 12
2 13
-8 2
-14 3
38
4 -8
16 8
-13 20
7 4
-11 9
16 -7
0 -11
-13 0
10 -9
-9 20
17 -17
-3 -16
6 17
19 10
-20 9
20 13
-17 -19
3 10
7 16
9 -10
-14 17
-19 -6
-19 -7
15 5
-9 -9
-12 8
-10 -1
-9 -1
1 -12
6 -1
3 -9
-12 -1
18 3
8 16
13 18
10 8
-7 -6
-2 -9
39
12 15
9 6
20 12
-6 14
10 11
-12 -14
-5 2
-4 8
-2 16
-13 -15
-20 11
9 -7
16 -5
20 19
16 -8
16 14
14 7
20 15
5 -14
-19 -18
-9 20
-4 -1
1 2
6 -10
-11 -6
17 4
-11 -1
-18 -15
14 17
18 20
-5 0
14 -9
20 -3
1 -14
5 11
-18 3
-3 2
0 -4
-4 11
40
17 -14
-5 13
15 -11
-14 14
-5 12
12 18
1 -15
13 -18
-5 17
-2 15
-5 8
-4 -20
-11 -16
-17 19
2 2
-8 -18
15 -18
-20 15
7 19
-17 16
9 20
17 8
1 -8
-19 20
17 -4
1 -5
-8 -1
-15 8
-12 10
0 -7
17 -18
-18 0
-19 7
18 7
-9 -11
5 3
19 1
1 20
-20 -1
-11 -12
41
6 -4
-12 -7
18 -5
11 -13
-14 -6
-14 1
3 14
18 2
1 -13
17 -11
-10 -15
19 3
-9 20
-12 -6
-12 -4
-6 17
15 20
16 10
2 16
-8 -15
-18 6
20 -2
-11 19
17 -19
0 -19
-4 19
19 11
18 -10
4 -7
-15 -15
9 -16
14 3
-15 6
-3 7
-12 1
-7 14
-7 -19
13 16
11 -8
9 -1
11 4
42
-16 8
1 -11
10 -7
-5 -18
4 1
15 13
-19 -1
3 -11
-18 -4
8 7
-13 -2
-10 -8
10 -12
0 19
-16 -6
-4 7
-3 -16
-9 -15
-13 7
-20 -18
12 -19
10 12
-14 4
-13 0
-4 14
-13 14
-1 -17
2 -19
-11 -4
1 -19
5 12
-12 16
-10 3
17 19
4 -9
15 -16
11 -16
10 -2
-17 -20
11 -7
20 1
18 19
43
-2 17
-13 10
-2 14
0 -16
18 0
-8 2
20 20
-6 -17
15 -17
12 8
-11 -15
-18 -14
-15 3
7 2
-15 9
15 1
1 -4
13 12
18 -5
-12 -18
10 7
8 -11
11 -11
5 -6
-1 19
3 -7
12 -17
-13 -8
19 -1
-19 -5
5 12
-19 4
12 7
-20 -4
-13 -16
10 20
5 -8
-19 -2
-4 -2
-3 -12
-6 -18
-14 -6
-5 12
44
9 2
-20 15
-20 19
15 -1
-18 7
18 3
-19 17
18 7
-11 -10
-18 17
-19 6
8 11
-10 14
3 2
15 -6
19 -8
5 20
-20 -16
8 -16
7 -13
1 -4
0 -17
19 -3
16 -14
12 18
7 -2
1 -17
11 19
7 -15
5 -11
-9 20
14 11
-14 -7
12 -1
-6 -13
4 3
-11 -16
13 -10
16 -16
-12 17
-14 -3
-9 13
-16 1
13 -14
45
0 -16
-20 -20
-12 19
17 15
17 -2
5 9
-1 17
10 -9
-14 -12
19 -20
-11 4
17 -13
-9 16
-8 19
7 -19
-1 18
20 -12
5 3
18 2
19 -12
1 20
-19 5
-12 1
6 14
3 -17
20 9
-20 -10
9 -14
7 -1
-3 16
10 14
1 -6
8 -2
-16 17
-2 2
19 -16
-7 11
11 14
16 19
-17 -7
-13 5
7 -17
20 17
4 1
11 3
46
14 10
-7 -18
-18 6
-17 0
-7 -12
17 -4
12 -14
-1 -4
16 1
-10 -12
-19 -9
-18 20
0 12
12 13
16 -18
13 15
-15 -1
-2 -2
-1 20
-6 -17
16 -17
12 9
11 -14
11 -12
18 -14
17 -12
6 16
-12 -6
12 19
-2 1
-12 2
-14 19
15 -10
-11 11
-19 9
-17 19
10 -14
2 -8
19 -20
9 -8
2 20
19 -13
-7 17
12 4
18 -10
8 -10
47
6 -19
4 16
15 19
14 4
-6 -7
14 14
13 -4
-15 -18
-13 -16
-18 7
16 2
-1 -9
0 1
-14 3
-6 12
-15 3
10 16
18 2
-1 -12
15 -5
1 10
11 9
3 -8
14 -18
-14 -8
1 16
16 3
20 -8
19 -7
11 5
-5 -10
16 1
12 3
-12 -1
5 3
-6 11
17 12
-2 -6
-5 11
-3 3
3 1
8 -18
-14 13
18 -9
18 0
7 8
5 -15
48
3 12
1 2
1 12
-8 -17
7 3
10 1
15 -19
-2 -18
19 -2
4 2
8 20
-3 20
5 -13
-2 1
-16 -2
-2 16
-10 18
20 8
4 -16
7 8
11 -2
-17 12
10 6
-12 -17
12 15
-18 -2
2 10
19 -20
-19 -5
-9 19
6 -13
-12 10
3 -18
-9 9
-10 16
-7 -17
20 -19
-3 -16
-7 12
-5 0
-20 7
11 9
-5 -5
-12 -9
-3 15
-10 19
-15 18
-14 -10
49
-12 17
-7 1
8 14
-4 1
16 -13
-3 -19
-12 16
9 9
15 -6
13 -6
18 6
-14 5
-9 9
15 0
14 2
1 10
-7 -11
-14 -1
-18 15
0 13
7 -20
-18 1
2 18
-9 16
9 -17
15 -2
-17 8
20 -12
16 1
11 -16
-10 -17
19 -9
9 2
14 -16
-15 14
-11 -14
-1 -16
4 2
-19 20
-13 12
8 11
-20 -3
-16 10
-18 -15
-12 -17
-9 -20
-14 -8
4 -9
4 16
50
20 14
-8 -18
9 2
18 -8
6 -14
-1 15
9 12
1 -7
-18 19
-6 -9
-17 -19
14 7
-20 1
-3 3
0 -11
15 -7
-18 -11
-9 6
1 14
13 10
-14 -1
20 -15
-10 -3
2 19
-13 -17
-17 1
-8 1
11 20
3 0
19 -6
16 6
4 17
-3 -13
-18 -1
15 -2
13 12
7 4
-19 5
3 16
-17 2
-10 5
-18 3
-15 -1
18 12
3 7
15 13
5 -12
17 -13
-9 -17
11 17
0
http://www.hsin.hr/2003/national/first_ ... oblems.pdf
last problem.
You can find the official solution on the same page.
last problem.
You can find the official solution on the same page.