Results of the New Year Habr Programming Contest, Analysis and Discussion

To be honest, I didn’t expect such a number of solutions: in 24 hours 265 solutions were sent, of which 183 remained after the removal of resets.

Of the 183 solutions, 11 had exceeded the allowable size of the solution, in 19 cases they could not compile (for these errors, see below for details). Then 47 gave incorrect answers on simple tests (1..1000000), 8 did not have time to calculate the answer in a minute (the sample solution from the problem statement for 1 million worked 5 minutes 36 seconds).

On complex tests - 5 solutions gave the wrong answer, and 12 - did not meet in one minute. 86 - successfully passed all tests.
')
If someone lost, here is the topic of the start of the competition with the conditions of the problem .

About tests and testing

All the banal scripts were tested, the most time-consuming operation is to save hands from the mail (and duplicate file names ... 42 pieces main.cpp ....). This is probably one of those cases when writing a web application for receiving decisions is faster than raking tons of mail. Test results were added to MySQL, from where the results table was built.

Simple tests:

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");

Difficult tests:
The average execution time was estimated (i.e., the execution time for 4 different input values divided by 4). The 3 fastest solutions were tested with 100-fold repetition - in order to get a more accurate run time (difference from a single run within 1%).

 $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);

Result table

Colleagues, let's push on invites:

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

Out of competition

Decisions sent after the deadline:

No	Habraname	Result	System id
one	@bstructure	1.5542407631874 sec.	192
2	@corsairnv	12.768928468227 sec.	194
3	@theirbaldness	15.648555219173 sec.	191
four	@ pavor84	Wrong answer on simple tests	189
five	@Jamim	Wrong answer on simple tests	193
6	@ 1dash	Compilation error	188

About errors

They wrote for MS VC : __int64 instead of long long or __int64_t, math.h is not connected, using the missing stdafx.h.
Wrote for Windows : Math.h <> math.h
Bleeding-edge C ++ 11 features : Unfortunately, correct code is not always compiled. Clang has problems with C ++ 11 multithreading (the compiler cannot compile the standard library, the bug is known - I tried to roll the patch - but it did not help). If this is not tested before being sent to the target compiler, then the problem cannot be detected.
Syntax errors : Banal attention - I suspect sending an un Saved file.
Unported code to 64-bit : Attempts to implicitly cast a pointer to an int, and vice versa.
memset : undeclared identifier 'memset'; did you mean 'wmemset'? It was an online test site llvm. The most popular mistake.
C # : One case.
Invalid comment format with user name : Solutions are still tested, so that someone else will suffer now :-).
Segmentation fault : Half of the incorrect answers on short tests are segfault and crash.

You can see your compilation results here (see System ID).
Full archive of source code solutions .

Solutions

Initially, I wanted to talk about the algorithms of the solution - but now I see that I have no idea how the first 2 places work, so it’s better to wait for the authors :-) However, it is worth noting that the use of streams is not a necessary condition for victory.

Shadeware, winner

@shadeware You have nothing buggy, it compiles.

 //@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\'XS\'}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_*[l 0\\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[jL]=1;}for(i=1;i+L<=n;i+=2)B[i]?0:A+=i+L;printf("%llu\n",A);}

Mikhaelkh, 2nd place

@mikhaelkh The compiler cursed the text string - but everything compiled.

 //@mikhaelkh #include <cstdio> #include <bitset> unsigned char s[]=" 3ћf b”Ђ)C —іЈ€ $9D » $ѕ|І† %ЃЉЃF &_ 'Y¶Fµ (nsџp± )ќznQ2 *S—) ,ot\\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Ћ~ ^qmty= bC†,n fd“¤ ¤ j1 [|Ј nN№Bў: r…ЄG viw{ {_}Lh *s# „ћoї‹E ‰to]¶~ Ћd*4: “kѕK8ћ ˜Њ~ќ˜QЄ ќ76« Ј;0ў §Ic§ ObЏP іЏx>† №›»Po ї·N† 1ґg& lІcѓ AdЎ“[$ –:і %і±1 «_7ќЌ lnєџ F”D 8ћcћ $$CM $+gDbP $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=ix%i)&1?r:r+i):i*i)/2;j<N;j+=i)v[j]=1; } for(i=1;i<=nx;i+=2) if(!v[i/2])res+=x+i; printf("%lld\n", n>1?res:0); }

Icemore, 3rd place, fastest multithreaded solution

@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,sq);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(ns-1<en)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, 4th place

@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, 5th place

@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[Pl]=1,P+=v; } for (i=l;i<=r;i+=2) if (!S[il] && i!=1) R+=i; if (l==1 && r>1) R+=2; std::cout<<A[r/B]+R; return 0; }

Singstio, the shortest solution passing all tests

@singstio 304 bytes, no “compression”

 //@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; }

Morality

First, the correct algorithm, then multithreading.
Moving C ++ programs to another OS, bit depth, compiler is a difficult and thorny path, it is necessary to test on the target platform. Twice it concerns bleeding-edge features.

About my mistakes

It seems to you that everything works for you, but is something wrong in the table?
I recommend to take the decision you sent from the archive with the solutions, and compile it on clang 3.2 64bit - and if it works, then write to me. Already 10 people have written that everything works for them, and the problem has always been either in another compiler or in care.

Source: https://habr.com/ru/post/164567/

All Articles