Итак, настало время подвести итоги прошедшего майского хабрасоревнования. Было прислано 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<N){double S=d(X,Y);if(S<H){H=S;F=X;G=Y;}}}double d(double x,double y){double q=0,Q=-1,X,Y;for(S s:z){X=x-s.x;Y=y-s.y;X=X*X+Y*Y;if(X>s.Q)q+=X-s.Q;else if(X<s.R)q+=s.R-X;else if(q==0){Y=Math.sqrt(X);Q*=Math.min(s.q-Y,Y-s.r)*.1;}}return q>0?q:Q;}void b(double r,double R){if(r+R>q){double d=Math.abs(r*r-R*R+q*q)/2/q,h=Math.sqrt(r*r-d*d),x=f.x+X*d,y=f.y+Y*d;u(x-Y*h,y+X*h);u(x+Y*h,y-X*h);}}String l(){char[]o=new char[99];int p=0,b;try{while((b=I.read())!=10)o[p++]=(char)b;}catch(Exception e){}return new String(o,0,p).trim();}public static void main(String[]a){new G();}G(){for(;i<512;i++){q=Math.PI*i/256;S[i]=Math.sin(q);C[i]=Math.cos(q);}c=new Short(l());z=new S[c];for(i=0;i<c;)z[i++]=new S();for(i=1;i<c&&H>0;i++)for(j=0;j<i&&H>0;j++){f=z[i];g=z[j];X=g.x-f.x;Y=g.y-f.y;q=Math.sqrt(X*X+Y*Y);X/=q;Y/=q;b(f.q,g.q);b(f.r,g.q);b(f.q,g.r);b(f.r,g.r);}double x=F,y=G,r=d(x,y),t=r<1e10?1e3:3e6,u,v,w,R;while(t>.1&&(i++<999||r>0)){R=r;X=x;Y=y;for(M=4;M<513&&R==r;M*=2){for(m=0;m<M;m++)if(M<5||m%2>0){j=m*512/M;u=x+S[j]*t;v=y+C[j]*t;if(u*u+v*v<N){w=d(u,v);if(w<R){X=u;Y=v;R=w;}}}}if(R<r){x=X;y=Y;r=R;}else t/=2;}System.out.println(x+" "+y);}} - AKashta — 86.9558 балла, на самом большом тесте вдвое быстрое lany, но немного проиграл по точности.Смотреть исходник
//@AKashta
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<Circle> sats = new ArrayList<Circle>(q);
for(int i = 0; i < Math.min(q, MAX_POINTS); i++) {
double x = reader.readDouble();
double y = reader.readDouble();
int offset = reader.readOffset();
double radius = ((double)SPEED / DATA_LENGTH * offset);
sats.add(new Circle(new Point(x, y), radius));
}
if(sats.size() == 2) {
ArrayList<Point> points = sats.get(0).intersect(sats.get(1));
for(Point p : points) {
result = p;
break;
}
} else {
if(ADVANCED_MODE) {
result = advancedCalc(sats);
} else {
result = simpleCalc(sats);
}
}
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<Circle> sats){
ArrayList<Point> points = new ArrayList<Point>();
for(int i = 0; i < 2; i++) {
for(int j = i + 1; j < 3; j++) {
points.addAll(sats.get(i).intersect(sats.get(j)));
}
}
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<Circle> sats){
ArrayList<Point> allPoints = new ArrayList<Point>();
for(int i = 0; i < sats.size() - 1; i++) {
for(int j = i + 1; j < sats.size(); j++) {
allPoints.addAll(sats.get(i).intersect(sats.get(j)));
}
}
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<Circle> sats){
int count = 0;
double sumX = 0;
double sumY = 0;
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(c);
}
_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<Point> intersect(Circle c) {
ArrayList<Point> result = new ArrayList<Point>();
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<Solution> calc(Satelite s1, Satelite s2) {
ArrayList<Solution> result = new ArrayList<Solution>();
double xT = s2.x - s1.x;
double yT = s2.y - s1.y;
double theta = Math.atan2(yT, xT);
double d = Math.sqrt(xT*xT + yT*yT);
double resX = (s1.range*s1.range - s2.range*s2.range + d*d)/(2*d);
double resY = Math.sqrt(s1.range*s1.range - resX*resX);
//System.out.format("Solution [%e %e]\n", resX, resY);
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<Solution> solutions) {
if (solutions.size() < 2) return false;
final double MAX_SPREAD = 400;
double minX, minY, maxX, maxY;
minX = minY = 10000000;
maxX = maxY = -10000000;
for (Solution sol : solutions) {
if (sol.x > maxX) maxX = sol.x;
if (sol.y > maxY) maxY = sol.y;
if (sol.x < minX) minX = sol.x;
if (sol.y < minY) minY = sol.y;
}
return range(minX, minY, maxX, maxY) < MAX_SPREAD;
}
static ArrayList<Solution> pickSingleCluster(ArrayList<Solution> solutions) {
final double MAX_SPREAD = 400;
// Calculate mean only for solutions close to solution 1.
Solution s1 = solutions.get(0);
ArrayList<Solution> result = new ArrayList<Solution>();
result.add(s1);
for (Solution sol : solutions) {
if (sol == s1) continue;
if (range(s1.x, s1.y, sol.x, sol.y) < MAX_SPREAD) {
result.add(sol);
}
}
return result;
}
static Solution calculateApproximation(ArrayList<Solution> solutions) {
double totalX = 0, totalY = 0;
double minX, minY, maxX, maxY;
minX = minY = 10000000;
maxX = maxY = -10000000;
for (Solution sol : solutions) {
totalX += sol.x;
totalY += sol.y;
if (sol.x > maxX) maxX = sol.x;
if (sol.y > maxY) maxY = sol.y;
if (sol.x < minX) minX = sol.x;
if (sol.y < minY) minY = sol.y;
}
Solution sol = new Solution(totalX/solutions.size(), totalY/solutions.size());
sol.spread = range(minX, minY, maxX, maxY);
sol.count = Math.pow(solutions.size(), 0.25);
return sol;
}
static ArrayList<Solution> getSolutionGrid(double x, double y, double stepX, double stepY,
ArrayList<Satelite> sateliteList) {
ArrayList<Solution> areaSolutions = new ArrayList<Solution>(11*11);
for (double xx = x - stepX*5; xx <= x + stepX*5.5; xx += stepX) {
for (double yy = y - stepY*5; yy <= y + stepY*5.5; yy += stepY) {
areaSolutions.add(new Solution(xx, yy));
}
}
return filterResults(areaSolutions, sateliteList);
}
static Solution calculateSolution(Solution approximation, ArrayList<Satelite> sateliteList) {
double step = 10;
ArrayList<Solution> areaSolutions;
Solution current = approximation;
do {
areaSolutions = getSolutionGrid(current.x, current.y, step, step, sateliteList);
if (areaSolutions.size() == 1 && current.score < 1 && areaSolutions.get(0).score > current.score) {
// Found a better single approximation point.
current = areaSolutions.get(0);
} else {
step /= 2;
current = calculateApproximation(areaSolutions);
}
} while (areaSolutions.size() < 20 && step > 0.01);
return current;
}
static void findSolutions(
int startIndex, ArrayList<Satelite> sateliteList, ArrayList<Solution> result) {
for (Satelite sat1 : sateliteList) {
for (Satelite sat2 : sateliteList) {
if (sat2.index <= sat1.index || sat2.index < startIndex) {
continue;
}
result.addAll(calc(sat1, sat2));
result.addAll(calc(sat1.halfTickCloser(), sat2));
result.addAll(calc(sat1.halfTickFarther(), sat2));
result.addAll(calc(sat1, sat2.halfTickCloser()));
result.addAll(calc(sat1.halfTickCloser(), sat2.halfTickCloser()));
result.addAll(calc(sat1.halfTickFarther(), sat2.halfTickCloser()));
result.addAll(calc(sat1, sat2.halfTickFarther()));
result.addAll(calc(sat1.halfTickCloser(), sat2.halfTickFarther()));
result.addAll(calc(sat1.halfTickFarther(), sat2.halfTickFarther()));
}
}
}
static ArrayList<Solution> filterResults(
ArrayList<Solution> solutions, ArrayList<Satelite> sateliteList) {
ArrayList<Solution> result = new ArrayList<Solution>();
Solution approximation = null;
double bestScore = 0;
for (Solution sol : solutions) {
double minScore = 1;
for (Satelite satelite : sateliteList) {
double score = satelite.scoreSolution(sol);
if (score < minScore) {
minScore = score;
}
}
if (minScore > bestScore) {
bestScore = minScore;
approximation = sol;
}
if (minScore == 1) {
result.add(sol);
sol.score = 1;
}
}
if (approximation != null && result.size() == 0) {
result.add(approximation);
approximation.score = bestScore;
}
return result;
}
static String readLine(BufferedInputStream in) throws IOException {
StringBuilder result = new StringBuilder();
int c = in.read();
while (c >=0 && c != '\n' && c != '\r') {
result.append(Character.toChars(c));
c = in.read();
}
if (c == '\r') {
in.mark(3);
int tmp = in.read();
if (tmp != '\n') {
in.reset();
}
}
return result.toString();
}
static class SateliteReader extends Thread {
LinkedBlockingQueue<Satelite> satelites;
BufferedInputStream in;
volatile int numSats = 0;
SateliteReader(LinkedBlockingQueue<Satelite> satelites) {
this.satelites = satelites;
}
@Override
public void run() {
try {
BufferedInputStream in = new BufferedInputStream(System.in);
numSats = Integer.parseInt(readLine(in));
for (int i = 0; i < numSats && !stopReader; ++i) {
satelites.add(readSatelite(in, approximation, i));
}
if (stopReader) {
satelites.add(new Satelite(-1, 0, 0, 0));
}
in.close();
} catch (NumberFormatException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
}
}
static class Scorer extends Thread {
volatile ArrayList<Satelite> sateliteList;
ArrayList<Solution> result;
LinkedBlockingQueue<Satelite> scoreSatelites;
Scorer(ArrayList<Satelite> sateliteList, ArrayList<Solution> result,
LinkedBlockingQueue<Satelite> scoreSatelites) {
this.sateliteList = sateliteList;
this.result = result;
this.scoreSatelites = scoreSatelites;
}
@Override
public void run() {
ArrayList<Satelite> localSateliteList = new ArrayList<Satelite>();
while (!stop) {
scoreSatelites.drainTo(localSateliteList);
Solution localApproximation = new Solution(approximation);
localApproximation = calculateSolution(localApproximation, localSateliteList);
approximation = localApproximation;
Satelite sat = null;
try {
sat = scoreSatelites.take();
} catch (InterruptedException e) {
return;
}
localSateliteList.add(sat);
}
stopReader = true;
}
}
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<Satelite> readSatelites = new LinkedBlockingQueue<Satelite>();
LinkedBlockingQueue<Satelite> scoreSatelites = new LinkedBlockingQueue<Satelite>();
SateliteReader sateliteReader = new SateliteReader(readSatelites);
sateliteReader.start();
//System.setIn(new FileInputStream("/media/ramdisk/test3_hi_precision.in"));
//BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
while (sateliteReader.numSats == 0) {
Thread.sleep(0, 1000);
}
int numSats = sateliteReader.numSats;
ArrayList<Satelite> sateliteList = new ArrayList<Satelite>();
ArrayList<Solution> result = new ArrayList<Solution>();
Scorer scorer = new Scorer(sateliteList, result, scoreSatelites);
ScoringDaemon scoringDaemon = new ScoringDaemon();
int startIndex = 0;
while (sateliteList.size() < numSats && !stopReader) {
Satelite sat = readSatelites.take();
if (stopReader) break;
sateliteList.add(sat);
scoreSatelites.add(sat);
if (sateliteList.size() > 1 && approximation == null) {
findSolutions(startIndex, sateliteList, result);
startIndex = sateliteList.size();
result = filterResults(result, sateliteList);
if (checkSpread(result)) {
approximation = calculateApproximation(result);
if (numSats > 2) {
scorer.start();
scoringDaemon.start();
}
}
}
}
scorer.interrupt();
if (approximation == null) {
result = pickSingleCluster(result);
approximation = calculateApproximation(result);
}
approximation = calculateSolution(approximation, sateliteList);
complete();
}
}
С полной таблицей результатов можно ознакомится тут. Красным подсвечены результаты, выходящие за допустимые пределы (ошибка более 1000 метров, или время работы более 5 секунд. ). Скачать все решения, их ответы и результаты компилации — можно тут. Некоторые догадались о возможности использовании внутреннего состояния MD5 — это позволяло ускорить расчет хэшей в 3 раза за счет того, что первые 128 байт хэшируемой строки не меняются и мы можем продолжать расчет только с 3-го 64-байтового блока. Но на практике это не понадобилось.
Так как длина передаваемой кодовой последовательности — 1 млн бит, очевидно, что там будут уникальные последовательности не длиннее 19-20 бит (2^20>1млн). Это позволяло заранее найти и хранить только эти уникальные маркеры (+ их сдвиг), и использовать их чтобы вычислять сдвиг кодовой последовательности вообще без вычисления MD5 в процессе выполнения программы.
Если использовать несколько таких маркеров — можно не читать все 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 часа — для поиска участниками моих ошибок, не сомневаюсь, что это возможно. Если ничего изменяющего таблицу не будет найдено — результаты будут финализированы и приступим к вручению призов.
This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.
Комментариев нет:
Отправить комментарий