Công việc nghiên cứu có lẽ là phần thú vị nhất trong quá trình đào tạo của chúng tôi. Ý tưởng là hãy thử sức mình theo hướng bạn đã chọn khi còn học đại học. Ví dụ: sinh viên thuộc lĩnh vực Kỹ thuật phần mềm và Học máy thường đến nghiên cứu tại các công ty (chủ yếu là JetBrains hoặc Yandex, nhưng không chỉ).
Trong bài đăng này, tôi sẽ nói về dự án của tôi trong Khoa học Máy tính. Là một phần công việc của mình, tôi đã nghiên cứu và áp dụng các phương pháp thực hành để giải một trong những bài toán NP-khó nổi tiếng nhất: vấn đề che phủ đỉnh.
Ngày nay, một cách tiếp cận thú vị đối với các bài toán NP-hard đang phát triển rất nhanh - các thuật toán tham số hóa. Tôi sẽ cố gắng giúp bạn cập nhật nhanh hơn, cho bạn biết một số thuật toán tham số hóa đơn giản và mô tả một phương pháp mạnh mẽ đã giúp tôi rất nhiều. Tôi đã trình bày kết quả của mình tại cuộc thi PACE Challenge: theo kết quả của các bài kiểm tra mở, giải pháp của tôi chiếm vị trí thứ ba và kết quả cuối cùng sẽ được biết vào ngày 1 tháng XNUMX.
Về bản thân
Tên tôi là Vasily Alferov, hiện tôi đang học năm thứ ba tại Trường Kinh tế Cao cấp thuộc Đại học Nghiên cứu Quốc gia - St. Petersburg. Tôi yêu thích thuật toán từ những ngày còn đi học, khi tôi học tại trường số 179 ở Moscow và tham gia thành công các cuộc thi Olympic khoa học máy tính.
Một số lượng hữu hạn các chuyên gia về thuật toán tham số hóa tham gia vào lĩnh vực...
Ví dụ lấy từ cuốn sách
Hãy tưởng tượng bạn là nhân viên bảo vệ quán bar ở một thị trấn nhỏ. Thứ sáu hàng tuần, một nửa thành phố đến quán bar của bạn để thư giãn, điều này mang đến cho bạn rất nhiều rắc rối: bạn cần phải đuổi những khách hàng ồn ào ra khỏi quán bar để tránh đánh nhau. Cuối cùng, bạn chán ngấy và quyết định thực hiện các biện pháp phòng ngừa.
Vì thành phố của bạn nhỏ nên bạn biết chính xác cặp khách quen nào có khả năng sẽ đánh nhau nếu họ cùng nhau vào quán bar. Bạn có một danh sách n những người sẽ đến quán bar tối nay. Bạn quyết định đuổi một số người dân thị trấn ra khỏi quán bar mà không để ai xảy ra đánh nhau. Đồng thời, sếp của bạn cũng không muốn bị mất lợi nhuận và sẽ không hài lòng nếu bạn không để nhiều hơn. k người.
Thật không may, vấn đề trước mắt bạn là một vấn đề NP-khó cổ điển. Bạn có thể biết cô ấy như , hoặc như một bài toán che đỉnh. Đối với những vấn đề như vậy, trong trường hợp chung, không có thuật toán nào hoạt động trong thời gian chấp nhận được. Nói một cách chính xác, giả thuyết chưa được chứng minh và khá mạnh ETH (Giả thuyết thời gian hàm mũ) cho rằng vấn đề này không thể giải quyết kịp thời , nghĩa là bạn không thể nghĩ ra điều gì tốt hơn đáng kể ngoài một tìm kiếm hoàn chỉnh. Ví dụ: giả sử ai đó sắp đến quán bar của bạn n = 1000 Nhân loại. Sau đó việc tìm kiếm hoàn chỉnh sẽ là các tùy chọn có khoảng - số tiền điên rồ. May mắn thay, quản lý của bạn đã cho bạn một giới hạn k = 10, do đó số lượng kết hợp bạn cần lặp lại nhỏ hơn nhiều: số lượng tập hợp con của mười phần tử là . Điều này tốt hơn, nhưng nó vẫn không được tính trong một ngày ngay cả trên một cụm mạnh mẽ.
Để loại trừ khả năng xảy ra đánh nhau trong bối cảnh mối quan hệ căng thẳng giữa những vị khách đến quán bar này, bạn cần phải loại Bob, Daniel và Fedor ra ngoài. Không có giải pháp nào mà chỉ có hai người bị bỏ lại phía sau.
Điều này có nghĩa là đã đến lúc phải nhượng bộ và cho mọi người vào? Hãy xem xét các lựa chọn khác. Chà, ví dụ, bạn không thể chỉ cho những người có khả năng chiến đấu với một số lượng người rất lớn vào. Nếu ai đó có thể chiến đấu ít nhất với k+1 một người khác, thì bạn chắc chắn không thể cho anh ta vào - nếu không bạn sẽ phải ngăn mọi người ra ngoài k+1 những người dân thị trấn, những người mà anh ta có thể chiến đấu, điều này chắc chắn sẽ khiến ban lãnh đạo khó chịu.
Mong bạn loại bỏ tất cả những người có thể theo nguyên tắc này. Sau đó những người khác chỉ có thể chiến đấu với không quá k mọi người. Vứt chúng ra ngoài k anh bạn, anh không thể ngăn chặn điều gì hơn ngoài xung đột. Điều này có nghĩa là nếu có nhiều hơn Nếu một người có liên quan đến ít nhất một cuộc xung đột thì bạn chắc chắn không thể ngăn chặn tất cả. Tất nhiên, vì bạn chắc chắn sẽ cho phép những người hoàn toàn không xung đột vào, nên bạn cần phải xem qua tất cả các tập hợp con có kích thước mười trong số hai trăm người. Có khoảng và số lượng thao tác này có thể đã được sắp xếp trên cụm.
Nếu bạn có thể bắt giữ những cá nhân không hề có xung đột một cách an toàn, vậy còn những người chỉ tham gia vào một cuộc xung đột thì sao? Trên thực tế, họ cũng có thể được vào bằng cách đóng cửa đối thủ. Thật vậy, nếu Alice chỉ xung đột với Bob, thì nếu chúng ta loại Alice ra khỏi hai người họ, chúng ta sẽ không thua: Bob có thể có những xung đột khác, nhưng Alice chắc chắn không có chúng. Hơn nữa, thật vô nghĩa khi chúng tôi không cho cả hai vào. Sau những hoạt động như vậy không còn lại những vị khách với số phận chưa được giải quyết: chúng tôi chỉ có xung đột, mỗi bên có hai người tham gia và mỗi bên có ít nhất hai người tham gia. Vì vậy tất cả những gì còn lại là sắp xếp các tùy chọn, có thể dễ dàng được coi là nửa ngày trên máy tính xách tay.
Trên thực tế, chỉ với những lý luận đơn giản, bạn có thể đạt được những điều kiện hấp dẫn hơn nữa. Lưu ý rằng chúng ta nhất định phải giải quyết mọi tranh chấp, tức là từ mỗi cặp xung đột, chọn ra ít nhất một người mà chúng ta không cho vào. Hãy xem xét thuật toán sau: lấy bất kỳ xung đột nào, từ đó chúng tôi loại bỏ một người tham gia và bắt đầu đệ quy từ phần còn lại, sau đó loại bỏ người tham gia khác và cũng bắt đầu đệ quy. Vì chúng tôi loại bỏ ai đó ở mỗi bước nên cây đệ quy của thuật toán như vậy là cây nhị phân có độ sâu k, vì vậy nhìn chung thuật toán hoạt động trong Đâu n là số đỉnh và m - số lượng xương sườn. Trong ví dụ của chúng tôi, con số này là khoảng mười triệu, có thể được tính trong tích tắc không chỉ trên máy tính xách tay mà ngay cả trên điện thoại di động.
Ví dụ trên là một ví dụ thuật toán tham số hóa. Thuật toán tham số hóa là thuật toán chạy theo thời gian f(k) poly(n)Đâu p - đa thức, f là một hàm tính toán tùy ý và k - một số tham số, rất có thể, sẽ nhỏ hơn nhiều so với kích thước của vấn đề.
Tất cả lý luận trước thuật toán này đều đưa ra một ví dụ sự nhân hóa là một trong những kỹ thuật chung để tạo ra các thuật toán tham số hóa. Kernelization là việc giảm kích thước bài toán xuống một giá trị được giới hạn bởi hàm của tham số. Vấn đề kết quả thường được gọi là kernel. Do đó, bằng cách suy luận đơn giản về bậc của các đỉnh, chúng ta đã thu được một hạt nhân bậc hai cho bài toán Vertex Cover, được tham số hóa bằng kích thước của câu trả lời. Có những cài đặt khác mà bạn có thể chọn cho tác vụ này (chẳng hạn như Vertex Cover Above LP), nhưng đây là cài đặt mà chúng ta sẽ thảo luận.
Thử thách tốc độ
Cuộc thi (Thử thách các thuật toán tham số hóa và thí nghiệm tính toán) ra đời năm 2015 nhằm thiết lập mối liên hệ giữa các thuật toán tham số hóa và các phương pháp được sử dụng trong thực tế để giải quyết các vấn đề tính toán. Ba cuộc thi đầu tiên được dành cho việc tìm chiều rộng cây của đồ thị (), tìm kiếm cây Steiner () và tìm tập đỉnh cắt chu trình (). Năm nay, một trong những bài toán mà bạn có thể thử sức mình là bài toán che phủ đỉnh được mô tả ở trên.
Cuộc thi đang trở nên phổ biến hàng năm. Nếu bạn tin vào số liệu sơ bộ thì năm nay có 24 đội tham gia cuộc thi chỉ giải bài toán che đỉnh. Điều đáng chú ý là cuộc thi kéo dài không phải vài giờ, thậm chí một tuần mà là vài tháng. Các đội có cơ hội nghiên cứu tài liệu, đưa ra ý tưởng ban đầu của riêng mình và cố gắng thực hiện nó. Về bản chất, cuộc thi này là một dự án nghiên cứu. Ý tưởng về các giải pháp hiệu quả nhất và trao giải cho người chiến thắng sẽ được tổ chức kết hợp với hội nghị (Hội thảo quốc tế về tính toán tham số hóa và chính xác) là một phần của cuộc họp thuật toán thường niên lớn nhất ở châu Âu . Thông tin chi tiết hơn về cuộc thi có thể được tìm thấy tại , và kết quả của những năm trước nói dối .
sơ đồ giải pháp
Để giải quyết vấn đề che phủ đỉnh, tôi đã thử sử dụng các thuật toán tham số hóa. Chúng thường bao gồm hai phần: các quy tắc đơn giản hóa (lý tưởng nhất là dẫn đến quá trình tạo hạt nhân) và các quy tắc phân tách. Quy tắc đơn giản hóa là tiền xử lý đầu vào trong thời gian đa thức. Mục đích của việc áp dụng các quy tắc như vậy là để rút gọn bài toán về một bài toán nhỏ hơn tương đương. Các quy tắc đơn giản hóa là phần tốn kém nhất của thuật toán và việc áp dụng phần cụ thể này sẽ dẫn đến tổng thời gian chạy thay vì thời gian đa thức đơn giản. Trong trường hợp của chúng tôi, các quy tắc phân chia dựa trên thực tế là đối với mỗi đỉnh, bạn cần lấy đỉnh đó hoặc đỉnh lân cận của nó làm câu trả lời.
Sơ đồ chung là thế này: chúng tôi áp dụng các quy tắc đơn giản hóa, sau đó chúng tôi chọn một số đỉnh và thực hiện hai lệnh gọi đệ quy: trong lần đầu tiên chúng tôi thực hiện phản hồi và trong lần thứ hai, chúng tôi thực hiện tất cả các đỉnh lân cận của nó. Đây là những gì chúng tôi gọi là phân tách (phân nhánh) dọc theo đỉnh này.
Chính xác một bổ sung sẽ được thực hiện cho sơ đồ này trong đoạn tiếp theo.
Ý tưởng cho quy tắc chia tách (brunching)
Chúng ta hãy thảo luận về cách chọn một đỉnh mà sự phân tách sẽ xảy ra.
Ý tưởng chính rất tham lam theo nghĩa thuật toán: hãy lấy một đỉnh có bậc tối đa và chia dọc theo nó. Tại sao nó có vẻ tốt hơn? Bởi vì trong nhánh thứ hai của lệnh gọi đệ quy, chúng ta sẽ loại bỏ rất nhiều đỉnh theo cách này. Bạn có thể tin tưởng vào một biểu đồ nhỏ còn lại và chúng tôi có thể xử lý nó một cách nhanh chóng.
Cách tiếp cận này, với các kỹ thuật nhân hóa đơn giản đã được thảo luận, thể hiện tốt và giải quyết được một số bài kiểm tra có kích thước vài nghìn đỉnh. Tuy nhiên, ví dụ, nó không hoạt động tốt đối với đồ thị bậc ba (nghĩa là đồ thị có bậc của mỗi đỉnh là ba).
Có một ý tưởng khác dựa trên một ý tưởng khá đơn giản: nếu đồ thị bị ngắt kết nối, bài toán về các thành phần liên thông của nó có thể được giải độc lập bằng cách kết hợp các câu trả lời ở cuối. Nhân tiện, đây là một sửa đổi nhỏ được hứa hẹn trong sơ đồ, sẽ tăng tốc đáng kể giải pháp: trước đây, trong trường hợp này, chúng tôi đã làm việc với tích số thời gian để tính toán phản ứng của các thành phần, nhưng bây giờ chúng tôi làm việc cho Tổng. Và để tăng tốc độ phân nhánh, bạn cần biến một biểu đồ được kết nối thành một biểu đồ bị ngắt kết nối.
Làm thế nào để làm nó? Nếu có một điểm khớp nối trong biểu đồ, bạn cần phải đấu tranh với nó. Điểm khớp nối là một đỉnh mà khi bị loại bỏ, đồ thị sẽ mất khả năng kết nối. Tất cả các điểm giao nhau trong biểu đồ có thể được tìm thấy bằng thuật toán cổ điển trong thời gian tuyến tính. Cách tiếp cận này tăng tốc đáng kể việc phân nhánh.
Khi bất kỳ đỉnh nào đã chọn bị loại bỏ, biểu đồ sẽ chia thành các thành phần được kết nối.
Chúng tôi sẽ làm điều này, nhưng chúng tôi muốn nhiều hơn nữa. Ví dụ: tìm các vết cắt đỉnh nhỏ trong biểu đồ và phân chia dọc theo các đỉnh từ nó. Cách hiệu quả nhất mà tôi biết để tìm đường cắt đỉnh toàn cục tối thiểu là sử dụng cây Gomori-Hu, được xây dựng theo thời gian khối. Trong Thử thách PACE, kích thước đồ thị thông thường là vài nghìn đỉnh. Trong tình huống này, hàng tỷ thao tác cần được thực hiện ở mỗi đỉnh của cây đệ quy. Hóa ra là không thể giải quyết vấn đề trong thời gian quy định.
Hãy cố gắng tối ưu hóa giải pháp. Điểm cắt đỉnh tối thiểu giữa một cặp đỉnh có thể được tìm thấy bằng bất kỳ thuật toán nào xây dựng luồng cực đại. Bạn có thể cho nó vào mạng như vậy , trong thực tế nó hoạt động rất nhanh. Tôi nghi ngờ rằng về mặt lý thuyết có thể chứng minh được ước tính về thời gian hoạt động , điều này đã khá chấp nhận được.
Tôi đã nhiều lần cố gắng tìm kiếm các vết cắt giữa các cặp đỉnh ngẫu nhiên và chọn điểm cân bằng nhất. Thật không may, điều này tạo ra kết quả kém trong thử nghiệm PACE Challenge mở. Tôi đã so sánh nó với một thuật toán phân chia các đỉnh ở mức độ tối đa, chạy chúng với giới hạn về độ sâu giảm dần. Một thuật toán cố gắng tìm ra vết cắt theo cách này đã để lại những biểu đồ lớn hơn. Điều này là do thực tế là các vết cắt hóa ra rất mất cân đối: sau khi loại bỏ 5-10 đỉnh, chỉ có thể tách ra 15-20.
Điều đáng chú ý là các bài viết về thuật toán nhanh nhất về mặt lý thuyết sử dụng các kỹ thuật nâng cao hơn nhiều để chọn các đỉnh để phân tách. Những kỹ thuật như vậy có cách triển khai rất phức tạp và thường có hiệu suất kém về mặt thời gian và bộ nhớ. Tôi không thể xác định được những điều nào có thể chấp nhận được để thực hành.
Cách áp dụng quy tắc đơn giản hóa
Chúng tôi đã có ý tưởng về hạt nhân hóa. Hãy để tôi nhắc nhở bạn:
- Nếu có một đỉnh bị cô lập, hãy xóa nó.
- Nếu có một đỉnh bậc 1, hãy loại bỏ nó và lấy đỉnh lân cận của nó.
- Nếu có ít nhất một đỉnh bậc k+1, lấy lại.
Với hai cái đầu tiên thì mọi thứ đều rõ ràng, với cái thứ ba thì có một mánh khóe. Nếu trong một bài toán hài hước về một quán bar, chúng ta được cho giới hạn trên là k, thì trong Thử thách PACE, bạn chỉ cần tìm bìa đỉnh có kích thước tối thiểu. Đây là một dạng chuyển đổi điển hình của Bài toán tìm kiếm thành Bài toán quyết định; thường không có sự khác biệt giữa hai loại bài toán. Trong thực tế, nếu chúng ta viết một hàm giải cho bài toán che đỉnh thì có thể có sự khác biệt. Ví dụ, như ở điểm thứ ba.
Từ quan điểm thực hiện, có hai cách để tiến hành. Cách tiếp cận đầu tiên được gọi là Lặp đi lặp lại sâu sắc. Nó như sau: chúng ta có thể bắt đầu với một số ràng buộc hợp lý từ bên dưới cho câu trả lời, sau đó chạy thuật toán của chúng ta bằng cách sử dụng ràng buộc này làm ràng buộc cho câu trả lời từ phía trên mà không bị đệ quy thấp hơn ràng buộc này. Nếu chúng tôi tìm thấy câu trả lời nào đó, nó được đảm bảo là tối ưu, nếu không, chúng tôi có thể tăng giới hạn này lên một và bắt đầu lại.
Một cách tiếp cận khác là lưu trữ một số câu trả lời tối ưu hiện tại và tìm kiếm câu trả lời nhỏ hơn, thay đổi tham số này khi tìm thấy k để cắt bỏ nhiều hơn các nhánh không cần thiết trong tìm kiếm.
Sau khi tiến hành một số thử nghiệm hàng đêm, tôi quyết định kết hợp hai phương pháp này: đầu tiên, tôi chạy thuật toán của mình với một số giới hạn về độ sâu tìm kiếm (chọn nó sao cho mất thời gian không đáng kể so với giải pháp chính) và sử dụng giải pháp tốt nhất nghiệm được tìm thấy ở giới hạn trên của câu trả lời - nghĩa là đối với điều tương tự k.
Đỉnh bậc 2
Chúng ta đã xử lý các đỉnh có bậc 0 và 1. Hóa ra điều này có thể được thực hiện với các đỉnh bậc 2, nhưng điều này sẽ đòi hỏi các phép toán phức tạp hơn từ biểu đồ.
Để giải thích điều này, bằng cách nào đó chúng ta cần chỉ định các đỉnh. Gọi đỉnh bậc 2 là đỉnh vvà các lân cận của nó - các đỉnh x и y. Tiếp theo chúng ta sẽ có hai trường hợp.
- Khi x и y - người hàng xóm. Sau đó bạn có thể trả lời x и yVà v xóa bỏ. Thật vậy, từ tam giác này cần phải lấy lại ít nhất hai đỉnh và chắc chắn chúng ta sẽ không thua nếu lấy x и y: họ có thể có những người hàng xóm khác, và v họ không phải.
- Khi x и y - không phải hàng xóm. Khi đó người ta tuyên bố rằng cả ba đỉnh đều có thể được dán lại thành một. Ý tưởng là trong trường hợp này có một câu trả lời tối ưu, trong đó chúng ta chọn một trong hai v, hoặc cả hai đỉnh x и y. Hơn nữa, trong trường hợp đầu tiên, chúng ta sẽ phải đưa tất cả các hàng xóm để phản hồi x и y, nhưng trong trường hợp thứ hai thì không cần thiết. Điều này hoàn toàn tương ứng với các trường hợp khi chúng ta không lấy đỉnh được dán để phản hồi và khi chúng ta làm như vậy. Chỉ cần lưu ý rằng trong cả hai trường hợp, phản hồi từ thao tác như vậy đều giảm đi một.
Điều đáng chú ý là phương pháp này khá khó thực hiện chính xác trong thời gian tuyến tính công bằng. Dán các đỉnh là một thao tác phức tạp; bạn cần sao chép danh sách các đỉnh lân cận. Nếu việc này được thực hiện một cách bất cẩn, bạn có thể đạt được thời gian chạy tiệm cận dưới mức tối ưu (ví dụ: nếu bạn sao chép nhiều cạnh sau mỗi lần dán). Tôi quyết định tìm toàn bộ đường đi từ các đỉnh bậc 2 và phân tích một loạt các trường hợp đặc biệt, chẳng hạn như chu trình từ các đỉnh đó hoặc từ tất cả các đỉnh như vậy ngoại trừ một đỉnh.
Ngoài ra, điều cần thiết là thao tác này có thể đảo ngược để khi quay trở lại từ đệ quy, chúng ta khôi phục biểu đồ về dạng ban đầu. Để đảm bảo điều này, tôi không xóa danh sách cạnh của các đỉnh được hợp nhất và sau đó tôi chỉ biết cạnh nào cần đi đến đâu. Việc triển khai biểu đồ này cũng đòi hỏi độ chính xác nhưng nó cung cấp thời gian tuyến tính hợp lý. Và đối với đồ thị có vài chục nghìn cạnh, nó phù hợp với bộ đệm của bộ xử lý, mang lại lợi thế lớn về tốc độ.
hạt nhân tuyến tính
Cuối cùng, phần thú vị nhất của kernel.
Để bắt đầu, hãy nhớ lại rằng trong đồ thị hai phần, có thể tìm được độ che phủ đỉnh tối thiểu bằng cách sử dụng . Để làm được điều này bạn cần sử dụng thuật toán để tìm sự kết hợp tối đa ở đó và sau đó sử dụng định lý .
Ý tưởng của hạt nhân tuyến tính là thế này: đầu tiên chúng ta chia đôi đồ thị, nghĩa là thay vì mỗi đỉnh v hãy thêm hai đỉnh и , và thay vì mỗi cạnh bạn - v hãy thêm hai xương sườn и . Biểu đồ kết quả sẽ là lưỡng cực. Chúng ta hãy tìm bìa đỉnh tối thiểu trong đó. Một số đỉnh của đồ thị ban đầu sẽ đến đó hai lần, một số chỉ một lần và một số thì không bao giờ. Định lý Nemhauser-Trotter phát biểu rằng trong trường hợp này người ta có thể loại bỏ các đỉnh không chạm tới dù chỉ một lần và lấy lại những đỉnh chạm hai lần. Hơn nữa, cô ấy nói rằng trong số các đỉnh còn lại (những đỉnh chạm một lần), bạn cần lấy ít nhất một nửa làm câu trả lời.
Chúng ta vừa học được cách rời đi không quá 2k đỉnh cao Thật vậy, nếu câu trả lời còn lại ít nhất là một nửa số đỉnh thì tổng số đỉnh không nhiều hơn 2k.
Ở đây tôi đã có thể tiến một bước nhỏ về phía trước. Rõ ràng là hạt nhân được xây dựng theo cách này phụ thuộc vào loại bìa đỉnh tối thiểu mà chúng ta đã lấy trong biểu đồ hai bên. Tôi muốn lấy một cái sao cho số đỉnh còn lại là tối thiểu. Trước đây, họ chỉ có thể làm được điều này trong thời gian . Tôi đã nghĩ ra cách triển khai thuật toán này vào thời điểm , do đó, lõi này có thể được tìm kiếm trong đồ thị hàng trăm nghìn đỉnh ở mỗi giai đoạn phân nhánh.
Kết quả
Thực tiễn cho thấy rằng giải pháp của tôi hoạt động tốt trong các bài kiểm tra hàng trăm đỉnh và hàng nghìn cạnh. Trong những thử nghiệm như vậy, hoàn toàn có thể hy vọng rằng giải pháp sẽ được tìm ra trong nửa giờ. Về nguyên tắc, xác suất tìm thấy câu trả lời trong thời gian chấp nhận được sẽ tăng lên nếu biểu đồ có số lượng đỉnh đủ lớn ở mức độ cao, ví dụ: độ 10 trở lên.
Để tham gia cuộc thi, các giải pháp phải được gửi tới . Đánh giá theo thông tin được trình bày ở đó , giải pháp của tôi trong các thử nghiệm mở đứng thứ ba trong số 20, với khoảng cách lớn so với thứ hai. Thành thật mà nói, không hoàn toàn rõ ràng các giải pháp sẽ được đánh giá như thế nào tại cuộc thi: ví dụ: giải pháp của tôi vượt qua ít bài kiểm tra hơn giải pháp ở vị trí thứ tư, nhưng đối với những giải pháp vượt qua, nó hoạt động nhanh hơn.
Kết quả của các cuộc kiểm tra kín sẽ được biết vào ngày 1 tháng 7.
Nguồn: www.habr.com