Voor degenen die het niet weten. SPOJ is een online judge system for programming problems. Ik ben nu al een tijd bezig met het volgende probleem: SUMFOUR.
Het vinden van de equal range gaat op dit moment door het lineair doorlopen van de arrays (index in beide arrays worden dus bijgehouden). Ik deed dit eerst door recursief binary search toe te passen, maar lineair de lijst doorlopen blijkt in de meeste gevallen sneller te zijn (zeker wanneer er in AB en CD veel waarden voorkomen met relatief kleine equal ranges). De equal_range functie die je in C++ standaard beschikbaar hebt, heb ik in die vorm niet kunnen vinden voor Java.
Ik maak de a, b, c, d, AB en CD arrays static, zodat ze niet bij elke test opnieuw local worden aangemaakt.
Mijn eerste probleem dat ik krijg bij de eerste opzet is dat ik een NZEC krijg. Via het try/catchen van verschillende Throwables en Exceptions ben ik erachter gekomen dat er een OutOfMemoryError optreedt. Deze treedt op wanneer ik AB en CD aanmaak met size 4000*4000. Maak ik ze aan met bijvoorbeeld 2250*2250 dan gaat het nog net goed. Echter kunnen de lijstjes a,b,c en d maximaal lengte 4000 krijgen. Dus heb ik voor AB en CD 4000*4000 nodig om alle summaties te kunnen opslaan (en te sorteren). Wellicht dat iemand hier een idee heeft hoe dit op te lossen.
Bij 2250*2250 krijg ik een TLE (time limit exceeded). Ik weet dat een dergelijke oplossing in C++ kan werken. In Java is deze opdracht sowieso lastiger (er zijn maar zes werkende oplossingen ingeleverd). Dit vind ik een uitdaging, maar optimalisatie is soms echt een huzarenstukje. Vandaar mede ook dit topic. Ik heb ook nog een Parser geschreven die sneller de input kan inlezen. Deze zal ik hieronder ook nog even posten. Mocht niet baten in ieder geval.
Zelf zat ik al te denken om eventueel deze hele opzet te verlaten en eerder richting een hashtable (eventueel BitSet) te denken. Echter bij een Hashtable zonder collission heb ik mijnsinzien al snel 2^29 plaatsen nodig.
Mijn aanpak is als volgt:The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c, d ) belongs to A x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n
Input
The first line of the input file contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as 2^28 ) that belong respectively to A, B, C and D .
Output should be printed on a single line.
- Lees de input in (respectievelijk array a, b, c en d van alle vier lengte n)
- Vul array AB (lengte n^2) met alle mogelijke optellingen van a X b
- Vul array CD (lengte n^2) me de negatie van alle mogelijke optellingen van c X d
- Sorteer AB en CD met behulp van Arrays.sort()
- Zie verder onderstaande code:
code:
1
2
3
4
5
6
7
8
9
| idxAB = idxCD = result = 0
while (idxAB <AB.length-1 && idxCD <CD.length-1)
int value = max(AB[idxAB], CD[idxCD])
bepaal in AB en CD het aantal element (nAB en nCD) in de equal range voor waarde value.
bepaal ook nieuwe idxAB en idxCD
(index van de eerste waarde v in respectievelijk AB en CD waarvoor geldt v>value)
result += nAB * nCD
value = max(AB[idxAB], CD[idxCD])
return result |
Het vinden van de equal range gaat op dit moment door het lineair doorlopen van de arrays (index in beide arrays worden dus bijgehouden). Ik deed dit eerst door recursief binary search toe te passen, maar lineair de lijst doorlopen blijkt in de meeste gevallen sneller te zijn (zeker wanneer er in AB en CD veel waarden voorkomen met relatief kleine equal ranges). De equal_range functie die je in C++ standaard beschikbaar hebt, heb ik in die vorm niet kunnen vinden voor Java.
Ik maak de a, b, c, d, AB en CD arrays static, zodat ze niet bij elke test opnieuw local worden aangemaakt.
Mijn eerste probleem dat ik krijg bij de eerste opzet is dat ik een NZEC krijg. Via het try/catchen van verschillende Throwables en Exceptions ben ik erachter gekomen dat er een OutOfMemoryError optreedt. Deze treedt op wanneer ik AB en CD aanmaak met size 4000*4000. Maak ik ze aan met bijvoorbeeld 2250*2250 dan gaat het nog net goed. Echter kunnen de lijstjes a,b,c en d maximaal lengte 4000 krijgen. Dus heb ik voor AB en CD 4000*4000 nodig om alle summaties te kunnen opslaan (en te sorteren). Wellicht dat iemand hier een idee heeft hoe dit op te lossen.
Bij 2250*2250 krijg ik een TLE (time limit exceeded). Ik weet dat een dergelijke oplossing in C++ kan werken. In Java is deze opdracht sowieso lastiger (er zijn maar zes werkende oplossingen ingeleverd). Dit vind ik een uitdaging, maar optimalisatie is soms echt een huzarenstukje. Vandaar mede ook dit topic. Ik heb ook nog een Parser geschreven die sneller de input kan inlezen. Deze zal ik hieronder ook nog even posten. Mocht niet baten in ieder geval.
Zelf zat ik al te denken om eventueel deze hele opzet te verlaten en eerder richting een hashtable (eventueel BitSet) te denken. Echter bij een Hashtable zonder collission heb ik mijnsinzien al snel 2^29 plaatsen nodig.
Java:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
| import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; class Main { private static int[][] ABCD = new int[4000][4]; private static int[] AB = new int[4000 * 4000]; private static int[] CD = new int[4000 * 4000]; private static int LENGTH, LENGTH_2; public static void main(String[] args) throws Exception { System.out.println(sumfour()); } private static long sumfour() throws Exception { BufferedReader bin = new BufferedReader( new InputStreamReader(System.in)); LENGTH = Integer.parseInt(bin.readLine()); LENGTH_2 = LENGTH * LENGTH; String[] stra; // read four lists into abcd[0] to abcd[3] for (int i = 0; i < LENGTH; i++) { stra = bin.readLine().split(" "); for (int j = 0; j < 4; j++) { ABCD[i][j] = Integer.parseInt(stra[j]); } } // compute sum(A[] X B[]) into AB[] // compute sum(C[] X D[]) into CD[] int counter = 0; for (int i = 0; i < LENGTH; i++) { for (int j = 0; j < LENGTH; j++) { AB[counter] = ABCD[i][0] + ABCD[j][1]; CD[counter++] = (-1) * (ABCD[i][2] + ABCD[j][3]); } } // sort ab[] and cd[] Arrays.sort(AB, 0, LENGTH_2); Arrays.sort(CD, 0, LENGTH_2); long start = System.nanoTime(); int idxAB = 0, idxCD = 0, countAB, countCD, value; long result = 0; int results[] = new int[2]; // determine first value to look for in both arrays value = Math.max(AB[idxAB], CD[idxCD]); boolean isEndOfArray = false; while (true) { // elements in equal range of value in AB plus index of first // element larger than value results = findRangeIdx(AB, idxAB, value); isEndOfArray = results[1] == -1; idxAB = results[1]; countAB = results[0]; // elements in equal range of value in CD plus index of first // element larger than value results = findRangeIdx(CD, idxCD, value); if (!isEndOfArray) isEndOfArray = results[1] == -1; idxCD = results[1]; countCD = results[0]; result += (long) countAB * (long) countCD; if (isEndOfArray) break; // determine value for next step value = Math.max(AB[idxAB], CD[idxCD]); } long end = System.nanoTime(); //System.out.println("Running time: " + (end - start)); return result; } /** * @param arr * sorted array to scan * @param idx * start scan from this index * @param value * check how many elements have this value * @return [0]number of elements in equal range [1]index of first element > * value (-1 if no such element) */ private static int[] findRangeIdx(int[] arr, int idx, int value) { int counter = 0; while (idx <= LENGTH_2 - 1 && arr[idx] < value) idx++; while (idx <= LENGTH_2 - 1 && arr[idx] == value) { idx++; counter++; } int[] result = { counter, -1 }; if (idx < LENGTH_2) result[1] = idx; return result; } } //Hieronder nog de Parser voor snellere input class SPOJParserX { final private int BUFFER_SIZE = 1 << 16; private BufferedInputStream bin; public SPOJParserX(InputStream in) { bin = new BufferedInputStream(in, BUFFER_SIZE); } public void close() throws IOException { if (bin != null) { bin.close(); } } public int nextInt() throws Exception { int ret = 0; byte c = (byte) bin.read(); while (c <= ' ') { c = (byte) bin.read(); } boolean neg = (c == '-'); if (neg) { c = (byte) bin.read(); } do { ret = ret * 10 + c - '0'; c = (byte) bin.read(); } while (c > ' '); if (neg) { return -ret; } else { return ret; } } } |
[ Voor 41% gewijzigd door RobIII op 19-11-2012 16:37 ]
:strip_icc():strip_exif()/u/43400/avatar.jpeg?f=community){kind=avatar}
/u/70160/herko-icon.png?f=community){kind=icon}
:strip_exif()/u/13818/episodebutler_60x60.gif?f=community)