Результаты и обсуждение майского хабрасоревнования: делаем свой ГЛОНАСС
Итак, настало время подвести итоги прошедшего майского хабрасоревнования. Было прислано 49 решений, удовлетворяющих требованиям по оформлению и 8 решений вне конкурса (позже дедлайна, с ошибками оформления, на неверный адрес). Что-ж, посмотрим, кто что написал.Хотя в обсуждении топика с самой задачей люди переживали, что самое компактное и самое быстрое решение — это разные вещи, оказалось что решение победителя lany — является и самым компактным, удовлетворяющим всем требованиям. Решение Frommi было вдвое компактнее, 863 байта —, но не смогло пройти все тесты. Следующим шло решение ibessonov на 1613 байта —, но оно внезапно показало большую ошибку на первом тесте.
Если у меня читатели не найдут ошибки, тройка победителей будет выглядеть так:
lany — двойной победитель, 89.9448 баллов и самое компактное решение.Самый большой тест (2.4Гб) пройден за 0.61 секунду.Смотреть исходник
//@lany
public class G{java.io.InputStream I=System.in; int c, i=0, j, m, M; double[]S=new double[512], C=new double[512]; byte[]P=»111001100011101101».getBytes (), d=new byte[999999]; double N=4.0678884e13, L=29.9792458, X, Y, q, F, G, H=1e99; S[]z; S f, g; class S{double x, y, r, q, R, Q; S (){x=new Double (l ()); y=new Double (l ()); try{I.read (d); I.skip (9000001);}catch (Exception e){}q=L*o ()+L/2; Q=q*q; r=q-L; R=r*r; l ();}int o (){int o=0, p; for (;; o+=10){for (p=0; p<18;p++)if(P[p]!=d[o+p*10])break;if(p==18){while(d[--o]>48); return o+1;}}}}void u (double X, double Y){if (X*X+Y*Y import java.io.*;
import java.util.ArrayList; public class Main { public static final boolean ADVANCED_MODE = true;
public static final int MAX_POINTS = 50;
public static final double PRECISION = 30;
public static final int THRESHOLD = 300; public static final String START_TOKEN = »111001100011101101»;
public static final long DATA_LENGTH = 10000000;
public static final long SPEED = 299792458;
public static final long EARTH_R = 6378000;
public static final long MIN_SAT_POS = 10000000;
public static final long MAX_SAT_POS = 20000000;
public static final int MIN_OFFSET = (int)((MIN_SAT_POS — EARTH_R) * DATA_LENGTH / SPEED);
public static final int MAX_OFFSET = (int)((MAX_SAT_POS + EARTH_R) * DATA_LENGTH / SPEED); public static void main (String args[ ]) {
//long startTime = System.currentTimeMillis ();
try {
DataInputStream in = new DataInputStream (System.in);
DataReader reader = new DataReader (in);
Point result = null; int q = reader.readInt ();
ArrayList double radius = ((double)SPEED / DATA_LENGTH * offset); sats.add (new Circle (new Point (x, y), radius));
} if (sats.size () == 2) {
ArrayList System.out.println (result.x + » » + result.y);
//long time = (System.currentTimeMillis () — startTime);
//System.out.println («Time:» + time);
} catch (Exception e) {
System.out.println (e.getMessage ());
}
} public static Point findRefPoint (ArrayList Point p0 = null, p1 = null, p2 = null;
for (Point p: points) {
for (Point t: points) {
if (p1 == null && t!= p && p.distance (t) < THRESHOLD){
p1 = t;
continue;
}
if(p1 != null && t != p && t != p1 && p.distance(t) < THRESHOLD){
p2 = t;
break;
}
}
if(p1 != null && p2 != null) {
p0 = p;
break;
} else {
p1 = null;
p2 = null;
}
}
return new Point((p0.x + p1.x + p2.x) / 3, (p0.y + p1.y + p2.y) / 3);
} public static Point advancedCalc (ArrayList int count = 0;
double sumX = 0;
double sumY = 0; for (Point p: allPoints) {
boolean containsInAll = true;
for (Circle sat: sats){
if (! sat.hasPoint (p)) {
containsInAll = false;
break;
}
}
if (containsInAll) {
count++;
sumX += p.x;
sumY += p.y;
}
}
return new Point (sumX / count, sumY / count);
} public static Point simpleCalc (ArrayList Point refPoint = findRefPoint (sats);
for (int i = 0; i < sats.size() - 1; i++) {
for(int j = i + 1; j < sats.size(); j++) {
for(Point p : sats.get(i).intersect(sats.get(j))) {
if(refPoint.distance(p) < THRESHOLD) {
count++;
sumX += p.x;
sumY += p.y;
}
}
}
}
return new Point(sumX / count, sumY / count);
} public static class DataReader {
private DataInputStream _in; public DataReader (DataInputStream in){
_in = in;
} public int readOffset () throws Exception {
byte firstByte = _in.readByte ();
int offset = 1;
while (_in.readByte () == firstByte) {
offset++;
}
int needToSkip = ((MIN_OFFSET — offset) / 10) * 10;
_in.skipBytes (needToSkip);
offset += needToSkip; byte[] buffer = new byte[MAX_OFFSET — offset];
_in.read (buffer);
_in.skipBytes ((int) DATA_LENGTH — offset — buffer.length — 1 + 2); StringBuilder sb = new StringBuilder (buffer.length / 10);
for (int i = 0; i < buffer.length / 10; i++ ){
sb.append((char) buffer[i * 10]);
} int index = sb.indexOf (START_TOKEN)* 10; return index + offset;
} public String readLine () throws Exception {
StringBuilder sb = new StringBuilder ();
char c;
while ((c = (char)_in.readByte ()) != '\r') {
sb.append©;
}
_in.readByte (); // read '\n' char
return sb.toString ();
} public int readInt () throws Exception {
String s = readLine ();
return Integer.parseInt (s);
} public Double readDouble () throws Exception {
String s = readLine ();
return Double.parseDouble (s);
}
} public static class Point {
public double x;
public double y; public Point (double x, double y) {
this.x = x;
this.y = y;
} public double distance () {
return Math.sqrt (x*x + y*y);
} public double distance (Point p) {
return Math.sqrt (Math.pow (x — p.x, 2) + Math.pow (y — p.y, 2));
}
} public static class Circle {
public Point center;
public double radius;
public Circle (Point p, double r) {
center = p;
radius = r;
} public ArrayList double dx = c.center.x — center.x;
double dy = c.center.y — center.y;
double d = Math.sqrt ((dy * dy) + (dx * dx)); if (d < Math.abs(radius - c.radius)) {
if(radius < c.radius)
radius += Math.abs(radius - c.radius) - d + 0.1;
else
c.radius += Math.abs(radius - c.radius) - d + 0.1;
}
if (d > (radius + c.radius)) {
double add = (d — (radius + c.radius))/ 2.0 + 0.1;
radius += add;
c.radius += add;
} if (d > (radius + c.radius) || d < Math.abs(radius - c.radius)) {
//System.out.println("do not intersect");
return result;
} double a = ((radius * radius) — (c.radius * c.radius) + (d *d)) / (2.0 * d); Point p2 = new Point (center.x + (dx * a/d), center.y + (dy * a/d)); double h = Math.sqrt ((radius * radius) — (a*a));
double rx = -dy * (h/d);
double ry = dx * (h/d); Point p = new Point (p2.x + rx, p2.y + ry);
if (p.distance () <= EARTH_R) {
result.add(p);
}
p = new Point(p2.x - rx, p2.y - ry);
if(p.distance() <= EARTH_R) {
result.add(p);
} return result;
} public boolean hasPoint (Point p) {
double d = center.distance (p);
return Math.abs (d — radius) <= PRECISION;
}
}
}
Staker — 83.3059 балла, еще чуть медленнее и чуть менее точно.Смотреть исходник
//@Staker
import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.regex.Matcher;
import java.util.regex.Pattern; public class Staker {
static final double M_PER_TICK = 29.9792458;
static final double TICK_PER_M = 0.03335640951;
static final double MAX_RANGE = 6378000;
static final int MINIMUM_READ_SKIP = 120800;
static final int MAX_READ_SIZE = 885000;
static final int SEQ_SIZE = 10000001;
static final int APPROXIMATION_MARGIN = 50;
static final String START_COMPACT = »111001100011101101»;
static final Pattern START_COMPACT_PATTERN = Pattern.compile (START_COMPACT, Pattern.LITERAL);
static byte[] buf = new byte[SEQ_SIZE]; static long startTime = 0;
static volatile boolean stop = false;
static volatile boolean stopReader = false;
static volatile Solution approximation = null; static class Satelite {
static final double HALFTICK_MARGIN = 0.001;
static final double HALFTICK = 14.9896229;
static final double HALFTICK_ALLOWED_RANGE = HALFTICK + 0.002; int index;
double x;
double y;
double range;
double checkRange;
Satelite (double x, double y, double range) {
this (-1, x, y, range);
}
Satelite (int index, double x, double y, double range) {
this.index = index;
this.x = x;
this.y = y;
this.range = range;
}
double scoreSolution (Solution s) {
double solutionRange = range (x, y, s.x, s.y);
double score = 1;
double delta = Math.abs (range — solutionRange);
if (delta > HALFTICK_ALLOWED_RANGE) {
double tempScore = 1/(1 + delta — HALFTICK_ALLOWED_RANGE);
if (tempScore < score) {
score = tempScore;
}
}
return score;
}
Satelite halfTickCloser() {;
return new Satelite(x, y, range - HALFTICK + HALFTICK_MARGIN);
}
Satelite halfTickFarther() {
return new Satelite(x, y, range + HALFTICK - HALFTICK_MARGIN);
}
}
static class Solution {
double x;
double y;
double score;
double spread;
double count;
Solution(double x, double y) {
this.x = x;
this.y = y;
this.score = 0;
this.spread = 0;
this.count = 0;
}
Solution(Solution other) {
this.x = other.x;
this.y = other.y;
this.score = other.score;
this.spread = other.spread;
this.count = other.count;
}
boolean check() {
return range(0, 0, x, y) <= MAX_RANGE;
}
}
static class Buffer extends Object implements CharSequence {
final byte[] byteBuf;
final int offset;
final int len;
Buffer(byte[] buf, int offset, int len) {
this.offset = offset;
this.len = len;
this.byteBuf = buf;
}
@Override
public char charAt(int arg0) {
return (char)byteBuf[offset + arg0 * 10];
} @Override
public int length () {
return len / 10;
} @Override
public CharSequence subSequence (int arg0, int arg1) {
return null;
}
}
static double range (double x1, double y1, double x2, double y2) {
return Math.sqrt ((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1));
}
static ArrayList double resR = Math.sqrt (resX*resX + resY*resY);
double resT1 = Math.atan2(resY, resX) + theta;
double resT2 = Math.atan2(-resY, resX) + theta;
double finalX1 = resR*Math.cos (resT1) + s1.x;
double finalY1 = resR*Math.sin (resT1) + s1.y;
double finalX2 = resR*Math.cos (resT2) + s1.x;
double finalY2 = resR*Math.sin (resT2) + s1.y;
Solution solution = new Solution (finalX1, finalY1);
if (solution.check ()) {
result.add (solution);
}
solution = new Solution (finalX2, finalY2);
if (solution.check ()) {
result.add (solution);
}
return result;
}
static int indexOf (byte[] buf, int len, byte[] pattern) {
for (int i = 0; i < len - pattern.length; ++i) {
int j;
for (j = 0; j < pattern.length; ++j) {
if (buf[i + j] != pattern[j]) {
break;
}
}
if (j == pattern.length) {
return i;
}
} return -1;
}
static Satelite readSatelite (BufferedInputStream in, Solution approximation, int index) throws IOException {
double x = Double.parseDouble (readLine (in));
double y = Double.parseDouble (readLine (in));
in.read (buf, 0, SEQ_SIZE);
// Handle \r\n EOL.
if (buf[SEQ_SIZE — 1] == '\r') {
in.mark (3);
int c = in.read ();
if (c!= '\n') {
in.reset ();
}
}
double satOriginDistance = range (0, 0, x, y);
int headSkipSize = (int)((satOriginDistance — MAX_RANGE) * TICK_PER_M);
headSkipSize -= (headSkipSize % 10);
int readSize = MAX_READ_SIZE;
boolean seen0 = false, seen1 = false;
int shift = -1;
while (! seen0 || ! seen1) {
++shift;
if (buf[shift] == '0') seen0 = true;
if (buf[shift] == '1') seen1 = true;
}
shift = shift % 10; if (approximation!= null) {
double approximateRange = range (x, y, approximation.x, approximation.y);
headSkipSize = (int)(approximateRange * TICK_PER_M — APPROXIMATION_MARGIN);
headSkipSize -= (headSkipSize % 10);
readSize = 2 * APPROXIMATION_MARGIN + START_COMPACT.length () * 10;
}
headSkipSize += shift;
Buffer seq = new Buffer (buf, headSkipSize, readSize);
Matcher matcher = START_COMPACT_PATTERN.matcher (seq);
if (! matcher.find ()) {
headSkipSize = MINIMUM_READ_SKIP + shift;
seq = new Buffer (buf, headSkipSize, MAX_READ_SIZE);
matcher.reset (seq);
matcher.find ();
}
int ind = matcher.start () * 10 + headSkipSize; return new Satelite (index, x, y, ind * M_PER_TICK);
} static boolean checkSpread (ArrayList static ArrayList static Solution calculateApproximation (ArrayList static ArrayList static Solution calculateSolution (Solution approximation, ArrayList static class Scorer extends Thread {
volatile ArrayList @Override
public void run () {
ArrayList static class ScoringDaemon extends Thread { ScoringDaemon () {
} @Override
public void run () {
double pScore = 0;
while (true) {
try {
Thread.sleep (0, 10000);
} catch (InterruptedException e) {
return;
}
long currTime = System.nanoTime ();
long timePassed = currTime — startTime;
double tScore = 10/(timePassed/1000000000.0 + 1.1);
double curPScore;
if (approximation == null) {
curPScore = 0;
} else if (approximation.spread > 1000) {
curPScore = 0;
} else if (approximation.spread > 0) {
curPScore = 100/(approximation.spread/2.2 + 10);
} else {
curPScore = 100/(1/approximation.score+10.01);
}
if (curPScore > pScore) {
pScore = curPScore;
}
if (pScore > 0 && timePassed > 4800000000L) {
stop = true;
} else if (pScore > tScore) {
// Good time-precision balance. Stop on next iteration.
stop = true;
}
if (stop) {
return;
}
if (timePassed > 4900000000L) {
// We have some score and 4.9 seconds passed. Stop now!
complete ();
}
}
}
} static void complete () {
if (approximation!= null) {
System.out.format (»%f %f», approximation.x, approximation.y);
} else {
System.out.print (»0 0»);
}
System.exit (0);
} public static void main (String[] args) throws IOException, InterruptedException{
startTime = System.nanoTime ();
LinkedBlockingQueue while (sateliteReader.numSats == 0) {
Thread.sleep (0, 1000);
}
int numSats = sateliteReader.numSats;
ArrayList Если использовать несколько таких маркеров — можно не читать все 10 мегабайт по каждому спутнику, а обходится лишь маленьким кусочком кодовой последовательности из входного потока и пропускать остальное для скорости. Конечно, это дало бы больший прирост производительности, если бы данные давались в файле (где можно сделать seek), а не потоке стандартного ввода. Крайне важно использовать факт того, что принимаемая последовательность идет с бОльшей частотой. Это позволяет увеличить точность определния расстояния до спутника с 300 до 30 метров. Прочитав последовательность до первой единицы — мы однозначно определяем остаток деления на 10 от сдвига последовательности. Далее — искать маркеры можно уже по прореженной в 10 раз последовательности (для скорости). Теперь мы знаем расстояние до спутника. Если бы оно не было округлено до ближайшего 100нс интервала (1 секунда/10МБит = 100нс = 29.9 метров) — то возможные точки расположения приемника лежали бы на окружности. С округлением — они лежат на кольце шириной в 29.9 метров. Если подходить к задаче геометрически — далее нам нужно найти пересечение N таких колец и окружности земли. Затем найти в полученной области возможных положений приемника точку, обеспечивающую минимальное математическое ожидание ошибки. Реализация такого «точного» решения обещает быть громоздкой —, но оно может быть упрощено: например можно примерно находить множество допустимых точек на сетке с фиксированным шагом (например 0.1 метра) в районе приблизительного оптимума, можно использовать алгоритмы последовательного приближения, но тут нужна аккуратная целевая функция, чтобы не потерять точность когда у нас много «неудобных» спутников висят с одной стороны земли. Надеюсь участники нам раскажут о своих других хитростях в решении.
Тесты 1–3 — простые тесты с количеством спутников 3–5.Тест 4 — 50 равномерно распределенных спутников.Тест 5 — максимальный тест, 255 равномерно распределенных спутников (2.4Гб данных).Тест 6 — 40 первых спутников неудобно висят с одной стороны земли и не позволяют построить точные координаты, затем идут 10 равномерно распределенных спутников.Скачать тесты можно тут (200Мб в архиве).
Очень много людей пострадало от невнимательности — несколько решений выводили отладочную информацию. Несколько решений выводило вещественные числа с запятой, а не точкой как было показано в примере. Несколько решений падало с различными ошибками. Там, где в таблице результатов вы видите очень большую ошибку — скорее всего в выходном файле не число.Тем не менее, некоторые вещи, о которых не было упомянуто в условии — я исправил. Одно решение пришло в кодировке cp1251 с русскими комментариями, и javac без дополнительных пинков не хотел проходить мимо русских комментариев. Решение было руками конвертировано в utf-8 и использован ключ компиляции -encoding UTF-8. В нескольких программах был указан package — его я закомментировал, для унификации процесса тестирования. Решения вне конкурса также были протестированы, однако пока на таблицу результатов они не смогли повлиять — так что кусать локти пока не стоит. Причины «вне конкурса»: Redmoon — оформление (не по формату указан пользователь), strelok369 — оформление (не по формату указан пользователь), Agath — позже дедлайна, vadimmm — позже дедлайна, jwriter — позже дедлайна, xio4 — позже дедлайна, VadosM — позже дедлайна, oleksandr17 — неверный адрес отправки. Скачать все решения вне конкурса, их ответы и результаты компиляции — можно тут
Будет интересно услышать дополнения и хитрости, используемые в решениях. Следующие 24 часа — для поиска участниками моих ошибок, не сомневаюсь, что это возможно. Если ничего изменяющего таблицу не будет найдено — результаты будут финализированы и приступим к вручению призов.
