StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>You can greatly cut execution time if you make a first pass over the list and only extract number pairs that it is possible to have an 3 term AP between (difference is 0 mod 2). And then iterating between such pairs.</p> <p>Pseudo C++-y code:</p> <pre><code>// Contains information about each beginning point struct BeginNode { int value; size_t offset; SortedList<EndNode> ends; //sorted by EndNode.value }; // Contains information about each class of end point struct EndNode { int value; List<size_t> offsets; // will be sorted without effort due to how we collect offsets }; struct Result { size_t begin; size_t middle; size_t end; }; SortedList<BeginNode> nodeList; foreach (auto i : baseList) { BeginNode begin; node.value = i; node.offset = i's offset; //you'll need to use old school for (i=0;etc;i++) with this // baseList is the list between begin and end-2 (inclusive) foreach (auto j : restList) { // restList is the list between iterator i+2 and end (inclusive) // we do not need to consider i+1, because not enough space for AP if ((i-j)%2 == 0) { //if it's possible to have a 3 term AP between these two nodes size_t listOffset = binarySearch(begin.ends); if (listOffset is valid) { begin.ends[listOffset].offsets.push_back(offsets); } else { EndNode end; end.value = j; end.offsets.push_back(j's offset); begin.ends.sorted_insert(end); } } } if (begin has shit in it) { nodeList.sorted_insert(begin); } } // Collection done, now iterate over collection List<Result> res; foreach (auto node : nodeList) { foreach (auto endNode : node.ends) { foreach (value : sublist from node.offset until endNode.offsets.last()) { if (value == average(node.value, endNode.value)) { // binary_search here to determine how many offsets in "endNode.offsets" "value's offset" is less than. do this that many times: res.push_back({node.value, value, endNode.value}); } } } } return res; </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload