Ponder This Challenge - June 2015 - Drifting complex anomaly detection

Ponder This Challenge:

IBM's QRadar system keeps track of events by measuring something every second. It has an anomaly detection system that alerts the user when the current measurement is more than three standard deviations away from the average of all previous measurements.

An imaginary attacker is trying to deceive the system by slowly drifting the measurements, without violating the anomaly detection rule at any stage. If the first two authentic measurement were -100 and 100, then the second can be anywhere between -300 and 300 without triggering an alert.

The attacker can throw the measurements off quite fast. For example, the sequence {-100, 100, -300, 389, 786, 1318, -1284} is a legal sequence (every measurement is no more than three standard deviations from the average of the previous ones), spanning an interval length of 2602.

To make things more complex, we ask the question in two dimensions: where each measurement is a Gaussian integer (a complex number whose real and imaginary parts are both integers) and the attacker tries to maximize the area of the convex hull of the sequence.

Your task is to find a legal sequence of 9 measurements starting with -100i,100i that achieves a convex hull area of at least 7,700,000.

Please supply the solution in the following format: (-100,0),(100,0),(110,279), ...

Solution

• Click here to view the solution

  Liubing Yu sent us a proof that 7,720,220 is an upper bound for this month's challenge (without the constraint that the points need to be integers).

  The best solution we received is 7,720,004. For example, Armin Krauss's solution: (-100,0),(100,0),(288,84),(139,-460), (603,-676),(780,780),(1585,-1086),(-1619,766),(-1360,-2802).

Solvers

• Robert Gerbicz (03/06/2015 12:12 AM IDT)
• Daniel Bitin (03/06/2015 01:39 PM IDT)
• Al Zimmermann (04/06/2015 08:11 PM IDT)
• Vladimir Sedach (04/06/2015 10:33 PM IDT)
• Sergey Koposov (05/06/2015 05:46 AM IDT)
• *Lorenz Reichel (05/06/2015 10:00 PM IDT)
• James Dow Allen (06/06/2015 02:22 PM IDT)
• Dan Ismailescu (07/06/2015 03:54 AM IDT)
• *Alex Wagner (08/06/2015 07:38 AM IDT)
• Di Luo (08/06/2015 12:26 PM IDT)
• Lorenzo Gianferrari (08/06/2015 05:21 PM IDT)
• Don Dodson (08/06/2015 07:04 PM IDT)
• Stéphane Higueret (08/06/2015 08:40 PM IDT)
• Jesse Rearick (09/06/2015 12:32 AM IDT)
• *Li Li (09/06/2015 02:06 AM IDT)
• Nyles Heise (09/06/2015 06:52 AM IDT)
• John Snyder (09/06/2015 06:32 PM IDT)
• *Hugo Pfoertner (10/06/2015 01:32 AM IDT)
• *Yanwu He (10/06/2015 06:38 AM IDT)
• David Greer (10/06/2015 11:22 PM IDT)
• Lei Fu (11/06/2015 08:35 PM IDT)
• Andrei Malashevich (11/06/2015 10:00 PM IDT)
• Minxi Jiang (12/06/2015 11:49 AM IDT)
• Graham Hemsley (13/06/2015 01:46 PM IDT)
• Shirish Chinchalkar (14/06/2015 05:28 AM IDT)
• Andreas Stiller (16/06/2015 01:08 AM IDT)
• Michael Rosola (16/06/2015 04:57 AM IDT)
• Dieter Beckerle (17/06/2015 12:04 AM IDT)
• *Armin Krauss (19/06/2015 02:33 AM IDT)
• Peter Gerritson (19/06/2015 11:54 PM IDT)
• *Radu-Alexandru Todor (20/06/2015 01:43 AM IDT)
• Yochay Lustmann (21/06/2015 07:36 PM IDT)
• Mathias Schenker (23/06/2015 01:02 AM IDT)
• Frank Marrs (23/06/2015 07:13 PM IDT)
• Liubing Yu (23/06/2015 09:23 PM IDT)
• Harald Bögeholz (24/06/2015 08:53 PM IDT)
• Chris Shannon (25/06/2015 08:09 AM IDT)
• Paolo Farinelli (25/06/2015 04:28 PM IDT)
• Gyorgy Gyomai (26/06/2015 09:06 AM IDT)
• *Uoti Urpala (28/06/2015 06:09 AM IDT)
• Jitesh Gandhi (28/06/2015 09:20 PM IDT)
• Don Ryan (29/06/2015 01:43 AM IDT)
• Emilio Del Tessandoro (30/06/2015 12:01 PM IDT)
• Dan Dima (30/06/2015 03:57 PM IDT)
• *Ioan Marius Popdan (30/06/2015 06:07 PM IDT)
• Erik Wünstel (30/06/2015 06:54 PM IDT)
• Todd Will (30/06/2015 08:44 PM IDT)
• Thomas Choi (30/06/2015 11:48 PM IDT)
• Phillip Ahn (30/06/2015 11:54 PM IDT)
• Bradley Sherman & Mason Bouffard (01/07/2015 07:41 AM IDT)
• *Mark Pervovskiy (30/06/2015 04:28 AM IDT)
• Motty Porat (30/06/2015 11:15 PM IDT)
• Chintan Maggu (02/07/2015 11:16 AM IDT)
• Kai Guttmann (02/07/2015 11:18 AM IDT)