Результаты новогоднего Хабра-соревнования по программированию, анализ и обсуждение

в 14:59, , рубрики: 2013, c++, Алгоритмы, соревнование, Спортивное программирование, метки: ,

Результаты новогоднего Хабра соревнования по программированию, анализ и обсуждениеЧестно говоря, я не ожидал такого количества решений: за 24 часа было прислано 265 решений, из которых после удаления повторных отправок осталось 183.

Из 183 решений у 11 был превышен допустимый размер решения, в 19 случаях — не удалось скомпилировать (об этих ошибках подробнее ниже). Далее 47 дали неправильные ответы на простых тестах (1..1000000), 8 не успели посчитать ответ за минуту (образец решения из условия задачи для 1млн работал 5 минут 36 секунд).

На сложных тестах — 5 решений выдали неверный ответ, и 12 — не уложились в одну минуту. 86 — успешно прошли все тесты.

Если кто потерял, вот топик о старте соревнования.

О тестах и тестировании

Тестировалось все банальными скриптами, самая трудоёмкая операция — сохранение руками решений из почты (и повторные имена файлов… 42 штуки main.cpp....). Это видимо один из тех случаев, когда написать web-приложение для приема решений быстрее, чем разгребать тонны почты.Результаты тестирования — складывались в MySQL, откуда строилась таблица результатов.

3 самых быстрых решения тестировались со 100-кратным повторением — чтобы получить более точное время работы (отличие от одиночного прогона в пределах 1%)

Простые тесты:

function do_test($input, $expected_output)
{
	global $task_id;
	exec("echo '$input' | Solutions2/bin/$task_id &2>1", $output);
	if(count($output)==0)return false;
	return(strcmp($output[0], $expected_output)==0);
}

$result = do_test("10","17") && do_test("1","0") && do_test("1000","76127") && do_test("100000","454396537") && do_test("1000000","37550402023");

Сложные тесты:
Оценивалось усредненное время выполнения (т.е. время выполнения для 4-х разных входных значений, деленное на 4).

$start_time = microtime (true);
//for($i=0;$i<100;$i++)
	$result = do_test("980000000","23783220704190493") && do_test("1051174931","27269025983026043") && do_test("891728152","19783994900202129") && do_test("761987760","14559966509022149");
$end_time = microtime (true);

Таблица результатов

Habraname Нужен ли инвайт Результат System ID
1 shadeware Уже нет 0.035053772330284 сек. 48
2 mikhaelkh Уже нет 0.039169362783432 сек. 41
3 Icemore Уже нет 0.068273649811745 сек. 129
4 ripatti Уже нет 0.11206769943237 сек. 8
5 kbxxi Да 0.15401327610016 сек. 156
6 monoid Да 0.22840601205826 сек. 69
7 Zver1992 0.23262423276901 сек. 133
8 Mrrl 0.37099504470825 сек. 178
9 Staker Да 0.66007524728775 сек. 171
10 SyDr Да 0.93328875303268 сек. 78
11 vbarinov Да 3.2648342847824 сек. 108
12 vanla Да 3.3831697702408 сек. 19
13 MaSaK Да 3.4151287674904 сек. 20
14 dark1ight 3.5476635098457 сек. 36
15 udalov Да 3.8905065059662 сек. 116
16 bklim 4.3489827513695 сек. 149
17 cfighter 4.4272682070732 сек. 11
18 VladVR 4.7588297724724 сек. 89
19 borozdinKirill 4.775633752346 сек. 109
20 ZhekSooN 4.8941134810448 сек. 122
21 madkite 4.9126330018044 сек. 114
22 akazakow 5.208831012249 сек. 45
23 mingrief 5.2523249983788 сек. 179
24 pasky 5.9874464869499 сек. 5
25 ewnd9 6.024626493454 сек. 183
26 gnhdnb 6.0333037376404 сек. 158
27 through_horizon 6.2488570213318 сек. 21
28 kosmos89 6.2885909676552 сек. 126
29 Nickel 6.36874127388 сек. 42
30 infsega 6.4502172470093 сек. 33
31 shuternay 6.4606020450592 сек. 6
32 smyatkin_maxim 6.5664409995079 сек. 123
33 azhi 6.9450110197067 сек. 145
34 Valmount 7.2953402400017 сек. 147
35 Alick09 7.4088390469551 сек. 125
36 alexeibs 7.6391640305519 сек. 177
37 DoctorStein 7.6435596942902 сек. 128
38 Kenny_HORROR 7.8451775312424 сек. 77
39 Ratio2 7.8529967665672 сек. 53
40 @No username specified 8.0461687445641 сек. 80
41 mobi 8.129643201828 сек. 64
42 Lonsdaleite 8.2785065174103 сек. 92
43 tiirz 8.3757525086403 сек. 134
44 Goryn 8.3831282258034 сек. 167
45 Leronxp 8.5381667613983 сек. 93
46 singstio 8.5835777521133 сек. 165
47 CTAKAH4uK 8.7342492341995 сек. 173
48 XMypuK 8.8221767544746 сек. 95
49 Edelweiss 8.8413127660751 сек. 61
50 Jovfer 9.6698319911957 сек. 174
51 crimaniak 10.019654750824 сек. 113
52 luckman 10.166677713394 сек. 46
53 ladilova 10.607916533947 сек. 59
54 Gromilo 11.256841778755 сек. 86
55 FreeCoder 11.380919516087 сек. 44
56 awa 11.482711791992 сек. 102
57 sprosin 11.626729488373 сек. 76
58 BelerafonL 11.740502238274 сек. 15
59 polar_winter 11.798308491707 сек. 47
60 luckychess 11.956114530563 сек. 143
61 darinflar 11.991075217724 сек. 105
62 kreep 12.082272768021 сек. 170
63 iqmaker 12.346569001675 сек. 34
64 dima11221122 12.357870519161 сек. 54
65 kos66 12.412921786308 сек. 68
66 alex_r 12.501110970974 сек. 31
67 dannk 12.711302280426 сек. 138
68 andreybotanic 12.847037494183 сек. 40
69 realsugar 14.033301234245 сек. 10
70 kromych 14.101772785187 сек. 25
71 iamnp 14.298875749111 сек. 32
72 skripkakos 14.305522501469 сек. 96
73 OnScript 14.555817246437 сек. 142
74 aserty 15.127694249153 сек. 175
75 ivanbl4 15.24883300066 сек. 148
76 kinbote 16.56739872694 сек. 130
77 ryokuyou 16.733837723732 сек. 106
78 quarck 21.369844019413 сек. 157
79 sultanko 21.440900743008 сек. 172
80 Yura1111 22.057671248913 сек. 30
81 Troyal 22.184078454971 сек. 99
82 Izobara 23.361551761627 сек. 16
83 PutPixel 35.820213794708 сек. 180
84 CheshaNeko 53.085104465485 сек. 120
85 fromnull 53.490429997444 сек. 65
86 ronsenval Неверный ответ на сложных тестах 14
87 undiabler Неверный ответ на сложных тестах 26
88 MrDindows Неверный ответ на сложных тестах 52
89 kladov Неверный ответ на сложных тестах 66
90 Andrew146 Неверный ответ на сложных тестах 127
91 vaux Превышено допустимое время на сложных тестах 22
92 marsencpp Превышено допустимое время на сложных тестах 27
93 phrk Превышено допустимое время на сложных тестах 43
94 burtsev Превышено допустимое время на сложных тестах 55
95 yooll Превышено допустимое время на сложных тестах 58
96 DarkContact Превышено допустимое время на сложных тестах 70
97 drongosar Превышено допустимое время на сложных тестах 87
98 alexvab Превышено допустимое время на сложных тестах 90
99 MrKonshyn Превышено допустимое время на сложных тестах 91
100 appplemac Превышено допустимое время на сложных тестах 112
101 msn92 Превышено допустимое время на сложных тестах 136
102 ikalnitsky Превышено допустимое время на сложных тестах 152
103 0Chekhov0 Неверный ответ на простых тестах 1
104 savik1 Неверный ответ на простых тестах 2
105 zenden2k Неверный ответ на простых тестах 12
106 alexaol Неверный ответ на простых тестах 17
107 Avitella Неверный ответ на простых тестах 18
108 yrik04 Неверный ответ на простых тестах 24
109 topz Неверный ответ на простых тестах 35
110 drozdVadym Неверный ответ на простых тестах 37
111 anton280 Неверный ответ на простых тестах 39
112 ehead01 Неверный ответ на простых тестах 49
113 8086 Неверный ответ на простых тестах 50
114 DIMKAAAAA Неверный ответ на простых тестах 57
115 mike_4d Неверный ответ на простых тестах 60
116 alineman Неверный ответ на простых тестах 74
117 pavor84 Неверный ответ на простых тестах 75
118 denzp Неверный ответ на простых тестах 79
119 RamTararam Неверный ответ на простых тестах 81
120 DezzK Неверный ответ на простых тестах 82
121 frozendog Неверный ответ на простых тестах 83
122 sasha237 Неверный ответ на простых тестах 98
123 aX1v Неверный ответ на простых тестах 103
124 rutigl Неверный ответ на простых тестах 104
125 Joric Неверный ответ на простых тестах 107
126 LibertyPaul Неверный ответ на простых тестах 110
127 volokitinss Неверный ответ на простых тестах 111
128 Formicidae Неверный ответ на простых тестах 115
129 fao Неверный ответ на простых тестах 117
130 vkm Неверный ответ на простых тестах 124
131 kleninz Неверный ответ на простых тестах 131
132 knstqq Неверный ответ на простых тестах 135
133 ryokuyou Неверный ответ на простых тестах 139
134 morphing Неверный ответ на простых тестах 140
135 Vaddddd Неверный ответ на простых тестах 144
136 ancalled Неверный ответ на простых тестах 150
137 fasterthanlight Неверный ответ на простых тестах 154
138 sinc Неверный ответ на простых тестах 155
139 Satayev Неверный ответ на простых тестах 159
140 eversyt Неверный ответ на простых тестах 162
141 zyss Неверный ответ на простых тестах 163
142 smile616 Неверный ответ на простых тестах 166
143 Moress Неверный ответ на простых тестах 169
144 zzzeeerrr0 Неверный ответ на простых тестах 176
145 kilotaras Неверный ответ на простых тестах 182
146 I_AM_FAKE Превышено допустимое время на простых тестах 7
147 Aksiom Превышено допустимое время на простых тестах 28
148 WarAngel_alk Превышено допустимое время на простых тестах 63
149 skovpen Превышено допустимое время на простых тестах 132
150 safinaskar Превышено допустимое время на простых тестах 160
151 @No username specified Превышено допустимое время на простых тестах 168
152 jit_md Превышено допустимое время на простых тестах 181
153 mrigi Попытка работать с отсутствующей сетью 146
154 Tweekaz Ошибка компиляции 3
155 @No username specified Ошибка компиляции 4
156 Thunderbird Ошибка компиляции 9
157 shock_one Ошибка компиляции 13
158 shy Ошибка компиляции 23
159 Dgut Ошибка компиляции 38
160 ShouldNotSeeMe Ошибка компиляции 56
161 therussianphysicist Ошибка компиляции 62
162 aamuvirkku Ошибка компиляции 84
163 IntegralUnderground Ошибка компиляции 85
164 0leksandr Ошибка компиляции 88
165 ipoder Ошибка компиляции 94
166 IharBury Ошибка компиляции 97
167 xtern Ошибка компиляции 100
168 KycokCo6aku Ошибка компиляции 101
169 gridem Ошибка компиляции 118
170 minc2319 Ошибка компиляции 141
171 okneigres Ошибка компиляции 151
172 antidotcb Ошибка компиляции 164
173 merkius Превышен допустимый размер файла 71
174 iTwin Превышен допустимый размер файла 29
175 bstructure Превышен допустимый размер файла 153
176 fsv Превышен допустимый размер файла 51
177 411 Превышен допустимый размер файла 72
178 pleha Превышен допустимый размер файла 67
179 staricam Превышен допустимый размер файла 73
180 chipa Превышен допустимый размер файла 119
181 dosefose Превышен допустимый размер файла 121
182 SergeySib Превышен допустимый размер файла 161
183 Ptax Превышен допустимый размер файла 137

Об ошибках

Писали для MS VC: __int64 вместо long long или __int64_t, не подключен math.h, использование отсутствующего stdafx.h.
Писали для Windows: Math.h<>math.h
Bleeding-edge C++11 фичи: К сожалению, корректный код не всегда компилируется. У clang есть проблемы с C++11 многопоточностью (компилятор не может скомпилировать стандартную библиотеку, баг известен — я пробовал накатить патч — но не помогло). Если это не протестировать до отправки на целевом компиляторе — то проблему никак не обнаружить.
Синтаксические ошибки: Банальная внимательность — подозреваю отправку не сохраненного файла.
Непортируемый на 64-bit код: Попытки неявно привести указатель к int, и обратно.
memset: undeclared identifier 'memset'; did you mean 'wmemset'? Находилось онлайн-тестом на сайте llvm. Самая популярная ошибка.
Segmentation fault: Половина неверных ответов на коротких тестах — это segfault-ы и краши.

Увидеть свои результаты компиляции можно тут (смотреть по System ID)

Решения

Изначально я хотел рассказать и об алгоритмах решения — но сейчас я вижу, что понятия не имею, как работают первые 2 места, потому лучше нам подождать авторов :-) Тем не менее, стоит заметить, что использование потоков не является необходимым условием для победы.

Shadeware, победитель

shadeware У вас ничего не глючит, это компилируется.

//@shadeware
#include <cstdio>
#include <vector>
#include <cmath>
unsigned i,n,Q,j,L;long long u[66],A;int main(){for(;i<448;i++)u[i/7+2]=u[i/7+2]*96+"+.Uy[e^4MAqc>,3Vq8a}n3-teC`p2r/)Fl[2Z)|>Ke2O~7<Co2:Q]dpI23fM5~22'X S'}2"z;})81lu^+vx1s sc[U1g%Wzq+1s3 ?1[1HQoI$^1TH2EaX1cEzV,Z1CHMY7o1DHmqPA1D#4oe]1F&|'F^1R`5'k)0{z2\Oc1<T/G)x10BVH)~1B,ZzW:1)>FZ%$1+[%c"<0dAd/tP1->"0M!1;JwZ6!1*%j_y00V6$w!u10I dHR1PXF]r20!?Xhxw1?nbdEr0e-/ZE_0s:6:z.0[}+qG51<y9WfF0.^#nCQ0s)I(d/0XfrAQB10^,7e?0^X'W4 13M.MfL0"
"5Q2Oz50fxnC)E0V@NGo+0=Z?sS/0I_*[l0\W)O u1pw[AYJ/A?Xk;g0rbiYbu1*{Pj>f0'"aEs60OP;ZHs0zsjvXg0:~BPSu/aWY+&F1_aM,<q"[i]-32;for(i=0;i<64;i++)u[i+2]+=2*u[i+1]-u[i];scanf("%u",&n);Q=sqrt(n)+1e-7,L=n>>24<<24;A=u[(n>>24)+1]+2*!L*!!~-n;std::vector<bool>S(Q/2+1),B(n-L+2);B[1]=!L;for(i=3;i<=Q;i+=2)if(!S[i/2]){for(j=3*i;j<=Q;j+=2*i)S[j/2]=1;for(j=L?(L+i-1)/i*i:2*i;j<=n;j+=i)B[j-L]=1;}for(i=1;i+L<=n;i+=2)B[i]?0:A+=i+L;printf("%llun",A);} 
Mikhaelkh, 2-е место

mikhaelkh Кодировка русского где-то похоже побилась, и компилятор на неё ругался — но чудом все скомпилировалось.

//@mikhaelkh
#include <cstdio>
#include <bitset>
unsigned char s[]=" 3ћfСЫБ b”Ђ)Cр ®—іЈ€Я $9шэD » $ѕ|Іш®† %ЃЉЃмF© &_яВГЕЕ 'Y¶FьВµ (nsџИp± )ќлznQ2 *иSР—ж) ,oшtе\v -пW0BC† /«Ю#™)ґ 1‚ьј”8P 3sю[Y6i 5.qЛ.“ 7¤zMЃшj 9г—‹XyЇ <_‰­XжЅ >ТOh«€Y AЃМ“«n® DKr]µrЩ G.?“нU® J*Ј»‚­Џ M@˜Eп†Ь PpYґпHј S№pvdјя W>дGpІш ZєQЦаЋ~ ^qяmty= bC†,щnт f.d“¤ ¤ j1Ж [|Ј nN№BўЮ: r…ЄG­рр vФiчwЁ{ {_Лз}Lh б*sЁЭ# „ћoї‹УE ‰to]¶е~ Ћd*4:иХ “kѕK8ћш ˜Њ~ќ˜QЄ ќЕЛ7д6« Ј;Ёл0ўь Ё§Iвc§б ®ObЗюЏP імЏxь>† №Е›»ЯPo ї·NцбЬ† ЕБ1ґgп& ЛгlъІcѓ ТAdЎ“[$ Ш–Й:ілЧ Я%юі±Ю1 е«_7бќЌ мlчnєСџ уF”ЭDРЭ ъ8ћуcћЖ $$CМжМMЕ $+gDbцPр $2ЎЧтУ‡E $9цА®П†Ы ";
enum{S=1<<14,N=1<<23};
long long a[65],res;
std::bitset<S> u;
std::bitset<N> v;
int n,r,x,i,j;
int main() {
	scanf("%d",&n);
	for (i=1;i<65;++i)
		for (++j;s[j]>32;++j)
			a[i]=221*a[i]+s[j]-35;
	*a=2,res=a[j=n/2/N],x=j*2*N,v[0]=!j;
	for (i=3;i<S+S;i+=2)
		if (!u[i/2]) {
			for (j=i*i/2;j<S;j+=i)u[j]=1;
			for (j=(x?((r=i-x%i)&1?r:r+i):i*i)/2;j<N;j+=i)v[j]=1;
		}
	for(i=1;i<=n-x;i+=2)
		if(!v[i/2])res+=x+i;
	printf("%lldn", n>1?res:0);
}
Icemore, 3-е место, самое быстрое многопоточное решение

Icemore


//@Icemore
#include<iostream>
#include<cmath>
#include<memory.h>
#include<pthread.h>
#define lng long long
const int T=4,Q=33000,S=100000;
bool np[Q],b[T][S];
int p[Q],c,B,s,e;
lng A[T],R,P[]={0,1906816620981654LL,7357074544482779LL,16217881619242062LL,28422918403819825LL};
void* f(void*_){
	long id=(long)_;
	int C=(e/S-B+1)/T,q,M,i,j,k;
	M=(id==T-1)?(e/S+1):(id+1)*C+B;
	for(k=id*C+B;k<M;++k){
		memset(b[id],0,sizeof(bool)*S);q=k*S;
		for(i=0;i<c;++i){
			j=(q+p[i]-1)/p[i];j=(j>1?j:2)*p[i]-q;
			for(;j<S;j+=p[i])b[id][j]=1;
		}
		if(!k)b[id][0]=b[id][1]=1;
		for(i=std::max(0,s-q);i<S&&q+i<=e;++i)if(!b[id][i])A[id]+=q+i;
	}
	return 0;
}
int main(){
	int n,i,q,j;
	std::cin>>n;
	i=(n-1)/(1<<28);s=i*(1<<28)+2;e=(i+1)*(1<<28);
	if(n-s-1<e-n)R=P[i],e=n;else s=n+1,R=-P[i+1];
	B=s/S;q=(int)sqrt(e+.0);p[c++]=2;
	for(i=3;i<=q;i+=2)if(!np[i])for(j=i*i,p[c++]=i;j<=q;j+=i)np[j]=1;
 	pthread_t t[T];
	for(i=0;i<T;++i)pthread_create(t+i,0,f,(void*)(i));
	for(i=0;i<T;++i)pthread_join(t[i],0),R+=A[i];
	std::cout<<(R>0?R:-R);
} 
ripatti, 4-е место

ripatti

//@ripatti
//идея - блочное решето с предпросчетом ответов для нескольких первых блоков
#include <iostream>
#include <memory.h>
#define S 150000
bool F[40000],B[S];
int P[10000],p=0;
long long pre[]={0,79835127420606,307011790722811,675490692294675,
1182357709860117,1825666731904492,2603717273255596,3515373254256955,
4559774703609068,5736228298250417,7043215380181465,8481171232603598,
10049045128993920,11745741297705187,13571569117886223,15525668198679060,
17608378509778587,19817357312226874,22154562782502270,24618987306923167,
27209541722648039};
int main(){
	int a,b,c,n,Z=(1<<15),Q=S*350;
	std::cin >> n;
	long long ans=pre[n/Q];
	for(a=2;a*a<Z;a++)if(!F[a])for(b=a*a;b<Z;b+=a)F[b]=true;
	for(a=2;a<Z;a++)if(!F[a])P[p++]=a;
	for(a=(n/Q)*Q;a<=n;a+=S){
		memset(B,0,sizeof B);
		for(b=0;b<p;b++)for(c=std::max(2,(a+P[b]-1)/P[b])*P[b]-a;c<S;c+=P[b])B[c]=true;
		if(a==0)B[0]=B[1]=true;
		for(b=0;b<S&&a+b<=n;b++)if(!B[b])ans+=a+b;
	}
	std::cout << ans;
	return 0;
}
kbxxi, 5-е место

kbxxi

//@kbxxi
#include <iostream>
long long A[]={0,72619548630277,279209790387276,614333144695291,1075207199997334,1660170771905893,2367646772295462,
3196703482711201,4146437503168147,5215984059716389,6404774487532576,7711724083073573,9137303389808024,
10680189372387880,12340337443955708,14116726304047228,16010026481858292,18019518580817005,20143329357815162,
22383876593236984,24739512092254535,27209541722648039};
char S[50000100];
int p[50100],C,i,j,B=50000000,l,r;
long long R=0;   

int main(){    
	std::cin >> r;   
    for (i=2;i<=100000;i++)
    if (!S[i]){
        p[C++]=i;        
        for (j=2*i;j<=100000;j+=i)
            S[j]=1;
    } else S[i]=0;    
	l=r/B*B+1;
	for (i=1;p[i]*p[i]<=r;i++){
        int v=p[i],P=l/v*v;        
        if (P<l) P+=v;
		if (P==v) P+=v;
		if (!(P&1)) P+=v;
		v*=2;
        while (P<=r) S[P-l]=1,P+=v;        
    }
    for (i=l;i<=r;i+=2) if (!S[i-l] && i!=1) R+=i;
	if (l==1 && r>1) R+=2;
    std::cout<<A[r/B]+R;	
	return 0;
}

Singstio, самое короткое решение проходящее все тесты

singstio 304 байта, никакого «сжатия»

//@singstio
#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
int main()
{
  __int64_t n,sum=0,i,j,sn;
  cin>>n;
  sn=int(sqrt(n))+1;
  vector<bool> s(n+1,true);
  for(i=2;i<=sn;i++)
    if(s[i]){
      for(j=i*i;j<=n;j+=i)s[j]=false;}
  for(i=2;i<=n;i++)if(s[i])sum+=i;
  cout<<sum<<endl;
} 

Мораль

  • Сначала правильный алгоритм, потом многопоточность.
  • Перенос C++ программ на другую ОС, разрядность, компилятор — сложный и тернистый путь, тестировать на целевой платформе нужно обязательно. Вдвойне это касается bleeding-edge фич.
Стоит ли организовать следующее хабра-соревнование через 3-6 месяцев, только с онлайн-приемом решений и проверкой на компилируемость не отходя от кассы?

Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

Проголосовало 39 человек. Воздержалось 6 человек.

Автор: BarsMonster

Источник

Поделиться

* - обязательные к заполнению поля