Largest Square Submatrix of all 1's

Find the largest square submatrix consisting entirely of 1s as fast as possible.

Input

A 10,000 x 10,000 matrix of uint8 values (0 or 1) on STDIN.

0, 1, 0, 1, 1
0, 1, 1, 1, 1
0, 0, 1, 0, 0
1, 0, 1, 1, 0

Output

Print the side length of the largest all-ones square submatrix to STDOUT. The answer is guaranteed to be greater than 1.

For the example above, the output is:

Restrictions:60s256Mb 1 Score Packages

Feel free to create an issue if you need an extra library from the standard Ubuntu repository.

Name	Version	Description
libc6-dev	2.39-0ubuntu8.7	GNU C Library: Development Libraries and Header Files Contains the symlinks, headers, and object files needed to compile and link programs which use the standard C library.
libclang-common-14-dev	1:14.0.6-19build4	Clang library - Common development package Clang project is a C, C++, Objective C and Objective C++ front-end based on the LLVM compiler. Its goal is to offer a replacement to the GNU Compiler Collection (GCC). . Clang implements all of the ISO C++ 1998, 11, 14 and 17 standards and also provides most of the support of C++20. . This package contains the Clang generic headers.
libclang-common-15-dev	1:15.0.7-14build3	Clang library - Common development package Clang project is a C, C++, Objective C and Objective C++ front-end based on the LLVM compiler. Its goal is to offer a replacement to the GNU Compiler Collection (GCC). . Clang implements all of the ISO C++ 1998, 11, 14 and 17 standards and also provides most of the support of C++20. . This package contains the Clang generic headers.
libclang-common-16-dev	1:16.0.6-23ubuntu4	Clang library - Common development package Clang project is a C, C++, Objective C and Objective C++ front-end based on the LLVM compiler. Its goal is to offer a replacement to the GNU Compiler Collection (GCC). . Clang implements all of the ISO C++ 1998, 11, 14 and 17 standards and also provides most of the support of C++20. . This package contains the Clang generic headers.
libclang-common-17-dev	1:17.0.6-9ubuntu1	Clang library - Common development package Clang project is a C, C++, Objective C and Objective C++ front-end based on the LLVM compiler. Its goal is to offer a replacement to the GNU Compiler Collection (GCC). . Clang implements all of the ISO C++ 1998, 11, 14 and 17 standards and also provides most of the support of C++20. . This package contains the Clang generic headers.
libclang-common-18-dev	1:18.1.3-1ubuntu1	Clang library - Common development package Clang project is a C, C++, Objective C and Objective C++ front-end based on the LLVM compiler. Its goal is to offer a replacement to the GNU Compiler Collection (GCC). . Clang implements all of the ISO C++ 1998, 11, 14 and 17 standards and also provides most of the support of C++20. . This package contains the Clang generic headers.
libclang-common-19-dev	1:19.1.1-1ubuntu1~24.04.2	Clang library - Common development package Clang project is a C, C++, Objective C and Objective C++ front-end based on the LLVM compiler. Its goal is to offer a replacement to the GNU Compiler Collection (GCC). . Clang implements all of the ISO C++ 1998, 11, 14 and 17 standards and also provides most of the support of C++20. . This package contains the Clang generic headers.
libclang-common-20-dev	1:20.1.2-0ubuntu1~24.04.2	Clang library - Common development package Clang project is a C, C++, Objective C and Objective C++ front-end based on the LLVM compiler. Its goal is to offer a replacement to the GNU Compiler Collection (GCC). . Clang implements all of the ISO C++ 1998, 11, 14 and 17 standards and also provides most of the support of C++20. . This package contains the Clang generic headers.
libcrypt-dev	1:4.4.36-4build1	libcrypt development files This package contains the files needed for developing applications that use libcrypt.
libgcc-10-dev	10.5.0-4ubuntu2.1	GCC support library (development files) This package contains the headers and static library files necessary for building C programs which use libgcc, libgomp, libquadmath, libssp or libitm.
libgcc-11-dev	11.5.0-1ubuntu1~24.04.1	GCC support library (development files) This package contains the headers and static library files necessary for building C programs which use libgcc, libgomp, libquadmath, libssp or libitm.
libgcc-12-dev	12.4.0-2ubuntu1~24.04.1	GCC support library (development files) This package contains the headers and static library files necessary for building C programs which use libgcc, libgomp, libquadmath, libssp or libitm.
libgcc-13-dev	13.3.0-6ubuntu2~24.04.1	GCC support library (development files) This package contains the headers and static library files necessary for building C programs which use libgcc, libgomp, libquadmath, libssp or libitm.
libgcc-14-dev	14.2.0-4ubuntu2~24.04.1	GCC support library (development files) This package contains the headers and static library files necessary for building C programs which use libgcc, libgomp, libquadmath, libssp or libitm.
libobjc-13-dev	13.3.0-6ubuntu2~24.04.1	Runtime library for GNU Objective-C applications (development files) This package contains the headers and static library files needed to build GNU ObjC applications.
libssl-dev	3.0.13-0ubuntu3.9	Secure Sockets Layer toolkit - development files This package is part of the OpenSSL project's implementation of the SSL and TLS cryptographic protocols for secure communication over the Internet. . It contains development libraries, header files, and manpages for libssl and libcrypto.
libstdc++-10-dev	10.5.0-4ubuntu2.1	GNU Standard C++ Library v3 (development files) This package contains the headers and static library files necessary for building C++ programs which use libstdc++. . libstdc++-v3 is a complete rewrite from the previous libstdc++-v2, which was included up to g++-2.95. The first version of libstdc++-v3 appeared in g++-3.0.
libstdc++-11-dev	11.5.0-1ubuntu1~24.04.1	GNU Standard C++ Library v3 (development files) This package contains the headers and static library files necessary for building C++ programs which use libstdc++. . libstdc++-v3 is a complete rewrite from the previous libstdc++-v2, which was included up to g++-2.95. The first version of libstdc++-v3 appeared in g++-3.0.
libstdc++-12-dev	12.4.0-2ubuntu1~24.04.1	GNU Standard C++ Library v3 (development files) This package contains the headers and static library files necessary for building C++ programs which use libstdc++. . libstdc++-v3 is a complete rewrite from the previous libstdc++-v2, which was included up to g++-2.95. The first version of libstdc++-v3 appeared in g++-3.0.
libstdc++-13-dev	13.3.0-6ubuntu2~24.04.1	GNU Standard C++ Library v3 (development files) This package contains the headers and static library files necessary for building C++ programs which use libstdc++. . libstdc++-v3 is a complete rewrite from the previous libstdc++-v2, which was included up to g++-2.95. The first version of libstdc++-v3 appeared in g++-3.0.
libstdc++-14-dev	14.2.0-4ubuntu2~24.04.1	GNU Standard C++ Library v3 (development files) This package contains the headers and static library files necessary for building C++ programs which use libstdc++. . libstdc++-v3 is a complete rewrite from the previous libstdc++-v2, which was included up to g++-2.95. The first version of libstdc++-v3 appeared in g++-3.0.
libtbb-dev	2021.11.0-2ubuntu2	parallelism library for C++ - development files TBB is a library that helps you leverage multi-core processor performance without having to be a threading expert. It represents a higher-level, task-based parallelism that abstracts platform details and threading mechanism for performance and scalability. . (Note: if you are a user of the i386 architecture, i.e., 32-bit Intel or compatible hardware, this package only supports Pentium4-compatible and higher processors.) . This package includes the TBB development files.

Back to listJan 5, 2026 06:03

Josu San Martin

Error

Source Code

Source code access is restricted. Log in to request access.

Challenge History

Date	Challenger	Cost	Type	Status
May 17, 2026 14:58	M-Rochat	10.00	Custom	Solution Broken

Run Statistics

#	Date	Score	Wall Time	CPU User	CPU System	Memory	Error
1	May 17, 2026 15:30	0	10,840,415	985,000	0	2,117,632	expected "253", got "100 "
2	May 17, 2026 15:30	0	10,852,245	934,000	0	2,117,632	expected "253", got "100 "
3	May 17, 2026 15:30	0	8,368,960	808,000	0	24,576	expected "253", got "100 "
4	Jan 5, 2026 04:33	3,085	18,077,508	1,234,000	0	2,453,504
5	Jan 5, 2026 04:33	3,333	16,505,202	1,333,000	0	2,449,408
6	Jan 4, 2026 06:29	3,508	22,132,100	1,403,000	0	2,449,408
7	Jan 4, 2026 06:33	3,570	16,743,481	1,428,000	0	2,445,312
8	Jan 5, 2026 04:39	3,610	19,585,791	1,444,000	0	2,453,504
9	Jan 4, 2026 06:34	3,620	15,705,291	1,448,000	0	2,441,216
10	Jan 4, 2026 06:33	3,628	18,688,229	0	1,451,000	2,449,408
11	Jan 4, 2026 06:33	3,630	23,807,717	1,452,000	0	2,453,504
12	Jan 4, 2026 06:33	3,633	15,955,035	1,453,000	0	2,449,408
13	Jan 17, 2026 17:21	3,633	16,914,723	1,453,000	0	2,449,408
14	Jan 4, 2026 06:29	3,638	15,569,787	1,455,000	0	2,445,312
15	Jan 18, 2026 01:10	3,640	17,200,266	1,456,000	0	2,453,504
16	Jan 18, 2026 01:10	3,643	20,661,850	1,457,000	0	2,449,408
17	Jan 4, 2026 06:38	3,660	12,850,383	0	1,464,000	2,453,504
18	Jan 18, 2026 01:10	3,660	19,530,838	1,464,000	0	2,449,408
19	Jan 17, 2026 17:19	3,678	23,338,714	1,471,000	0	2,445,312
20	Jan 4, 2026 06:33	3,685	16,994,346	1,474,000	0	2,441,216
21	Jan 4, 2026 06:33	3,685	21,829,931	1,474,000	0	2,445,312
22	Jan 17, 2026 17:19	3,685	21,326,135	0	1,474,000	2,449,408
23	Jan 17, 2026 17:19	3,690	16,942,943	1,476,000	0	2,453,504
24	Jan 17, 2026 17:28	3,693	22,124,809	1,477,000	0	2,449,408
25	Jan 4, 2026 06:33	3,700	17,966,671	1,480,000	0	2,445,312
26	Jan 17, 2026 17:19	3,700	21,418,605	1,480,000	0	2,441,216
27	Jan 18, 2026 01:16	3,705	19,379,195	1,482,000	0	2,453,504
28	Jan 17, 2026 17:25	3,713	17,242,728	1,485,000	0	2,449,408
29	Jan 5, 2026 04:39	3,720	13,409,486	1,488,000	0	2,449,408
30	Jan 17, 2026 17:27	3,728	17,847,903	1,491,000	0	2,441,216
31	Jan 5, 2026 04:39	3,733	14,227,806	1,493,000	0	2,445,312
32	Jan 18, 2026 01:16	3,733	19,369,535	0	1,493,000	2,453,504
33	Jan 17, 2026 17:27	3,735	22,031,942	1,494,000	0	2,453,504
34	Jan 17, 2026 17:28	3,735	23,145,434	1,494,000	0	2,449,408
35	Jan 4, 2026 06:33	3,738	16,439,064	1,495,000	0	2,445,312
36	Jan 18, 2026 01:10	3,740	16,693,943	0	1,496,000	2,445,312
37	Jan 17, 2026 17:21	3,743	17,570,491	0	1,497,000	2,445,312
38	Jan 4, 2026 06:37	3,745	14,375,517	1,498,000	0	2,449,408
39	Jan 5, 2026 02:27	3,748	17,377,619	1,499,000	0	2,445,312
40	Jan 4, 2026 06:29	3,750	16,305,360	0	1,500,000	2,535,424
41	Jan 5, 2026 04:39	3,753	19,979,888	0	1,501,000	2,449,408
42	Jan 17, 2026 17:21	3,753	18,582,507	0	1,501,000	2,441,216
43	Jan 4, 2026 06:35	3,758	18,736,369	0	1,503,000	2,445,312
44	Jan 17, 2026 17:27	3,758	18,818,392	1,503,000	0	2,449,408
45	Jan 17, 2026 17:19	3,760	19,920,977	1,504,000	0	2,441,216
46	Jan 18, 2026 01:10	3,765	22,272,042	1,506,000	0	2,441,216
47	Jan 4, 2026 06:35	3,768	17,601,441	1,507,000	0	2,445,312
48	Jan 5, 2026 02:28	3,768	14,757,236	1,507,000	0	2,535,424
49	Jan 5, 2026 04:39	3,768	16,371,870	0	1,507,000	2,441,216
50	Jan 18, 2026 01:10	3,768	18,304,587	1,507,000	0	2,445,312
51	Jan 18, 2026 01:16	3,768	18,939,229	1,507,000	0	2,445,312
52	Jan 17, 2026 17:19	3,770	17,206,506	1,508,000	0	2,449,408
53	Jan 17, 2026 17:21	3,770	17,833,114	0	1,508,000	2,449,408
54	Jan 17, 2026 17:25	3,775	21,115,111	1,510,000	0	2,535,424
55	Jan 17, 2026 17:25	3,775	18,609,766	0	1,510,000	2,453,504
56	Jan 4, 2026 06:35	3,780	17,472,032	1,512,000	0	2,445,312
57	Jan 4, 2026 06:34	3,783	22,541,311	1,513,000	0	2,441,216
58	Jan 17, 2026 17:21	3,783	12,858,618	1,513,000	0	2,445,312
59	Jan 17, 2026 17:19	3,785	19,721,461	0	1,514,000	2,453,504
60	Jan 17, 2026 17:21	3,785	16,225,882	1,514,000	0	2,445,312
61	Jan 17, 2026 17:21	3,785	14,967,961	1,514,000	0	2,535,424
62	Jan 4, 2026 06:36	3,788	14,685,693	0	1,515,000	2,445,312
63	Jan 5, 2026 02:27	3,788	19,539,834	1,515,000	0	2,445,312
64	Jan 5, 2026 04:33	3,788	19,962,073	1,515,000	0	2,449,408
65	Jan 4, 2026 06:37	3,790	19,516,537	1,516,000	0	2,449,408
66	Jan 18, 2026 01:16	3,790	18,222,323	0	1,516,000	2,445,312
67	Jan 4, 2026 06:36	3,793	17,188,370	1,517,000	0	2,441,216
68	Jan 17, 2026 17:21	3,793	16,048,618	1,517,000	0	2,535,424
69	Jan 4, 2026 06:33	3,795	22,792,577	1,518,000	0	2,449,408
70	Jan 4, 2026 06:33	3,798	19,253,284	1,519,000	0	2,535,424
71	Jan 17, 2026 17:28	3,798	17,063,728	1,519,000	0	2,449,408
72	Jan 17, 2026 17:28	3,800	22,962,051	1,520,000	0	2,445,312
73	Jan 17, 2026 17:28	3,800	14,855,162	0	1,520,000	2,449,408
74	Jan 18, 2026 01:10	3,800	18,255,030	1,520,000	0	2,445,312
75	Jan 4, 2026 06:33	3,805	22,996,064	1,522,000	0	2,453,504
76	Jan 18, 2026 01:10	3,805	22,664,972	1,522,000	0	2,453,504
77	Jan 17, 2026 17:19	3,808	18,343,046	1,523,000	0	2,445,312
78	Jan 4, 2026 06:33	3,810	19,528,443	1,524,000	0	2,453,504
79	Jan 4, 2026 06:33	3,810	16,736,418	1,524,000	0	2,445,312
80	Jan 18, 2026 01:16	3,818	16,187,168	1,527,000	0	2,535,424
81	Jan 5, 2026 02:28	3,820	18,611,306	1,528,000	0	2,445,312
82	Jan 4, 2026 06:33	3,823	13,361,655	1,529,000	0	2,453,504
83	Jan 17, 2026 17:20	3,823	14,719,388	1,529,000	0	2,441,216
84	Jan 17, 2026 17:28	3,823	14,932,002	1,529,000	0	2,441,216
85	Jan 4, 2026 06:37	3,825	15,104,245	1,530,000	0	2,535,424
86	Jan 17, 2026 17:20	3,830	17,098,712	1,532,000	0	2,449,408
87	Jan 18, 2026 01:10	3,830	17,914,668	1,532,000	0	2,449,408
88	Jan 4, 2026 06:33	3,833	18,197,365	0	1,533,000	2,445,312
89	Jan 17, 2026 17:25	3,838	15,607,869	0	1,535,000	2,457,600
90	Jan 18, 2026 01:10	3,845	21,147,293	1,538,000	0	2,449,408
91	Jan 17, 2026 17:25	3,855	17,754,329	1,542,000	0	2,449,408
92	Jan 5, 2026 04:39	3,863	17,166,296	1,545,000	0	2,445,312
93	Jan 18, 2026 01:10	3,878	24,736,856	1,551,000	0	2,445,312
94	Jan 18, 2026 01:10	3,878	17,578,161	1,551,000	0	2,449,408
95	Jan 5, 2026 02:28	3,885	19,572,312	1,554,000	0	2,449,408
96	Jan 17, 2026 17:19	3,893	16,650,579	1,557,000	0	2,535,424
97	Jan 5, 2026 02:27	3,905	16,239,338	0	1,562,000	2,449,408
98	Jan 4, 2026 06:35	3,913	18,878,361	1,565,000	0	2,449,408
99	Jan 17, 2026 17:20	3,928	18,620,169	1,571,000	0	2,449,408
100	Jan 4, 2026 06:38	3,945	22,291,581	1,578,000	0	2,445,312
101	Jan 4, 2026 06:29	3,948	18,270,945	1,579,000	0	2,445,312
102	Jan 4, 2026 06:34	3,985	19,419,351	1,594,000	0	2,441,216
103	Jan 17, 2026 17:21	4,000	17,489,626	1,600,000	0	2,453,504
104	Jan 4, 2026 06:35	4,005	13,775,003	1,602,000	0	2,445,312
105	Jan 4, 2026 06:29	4,008	20,527,716	1,603,000	0	2,449,408
106	Jan 4, 2026 06:29	4,040	15,841,624	1,616,000	0	2,449,408
107	Jan 4, 2026 06:36	4,048	17,155,250	0	1,619,000	2,449,408
108	Jan 4, 2026 06:38	4,050	18,798,433	0	1,620,000	2,445,312
109	Jan 4, 2026 06:35	4,073	17,505,239	1,629,000	0	2,449,408
110	Jan 17, 2026 17:25	4,073	16,535,206	1,629,000	0	2,445,312
111	Jan 5, 2026 06:03	4,160	16,012,152	1,664,000	0	2,449,408
112	Jan 18, 2026 01:16	4,313	21,400,165	1,725,000	0	2,445,312
113	Jan 5, 2026 06:03	4,543	16,766,416	1,817,000	0	2,445,312
114	Jan 5, 2026 06:03	4,640	23,815,904	1,856,000	0	2,449,408

Model	Intel(R) Xeon(R) CPU E3-1271 v3 @ 3.60GHz
Cores	1