ამოცანების პირობების სანახავად ამ ბმულს მიჰყევით.

ამოცანის წასაკითხად არც ისე მარტივი პირობის მიღმა იმალება მართკუთხა ზედაპირი, რომელიც კვადრატულ მეტრებად დავყავით და თითოეულ მათგანზე ზედაპირს გარკვეული ფიქსირებული სიმაღლე აქვს. მოსაძებნია, თუ არის მოცემულ ზედაპირზე კვადრატი გვერდის სიგრძით 2 მეტრი, რომლის ზედაპირის სიმაღლე თანაბარია.

პირველი დაკვირვება, რომელიც უმეტესობამ ალბათ დაუფიქრებლად გააკეთა - თუ ასეთი კვადრატი არსებობს, მაშინ მოიძებნება ამ პირობის დამაკმაყოფილი ისეთი კვადრატიც, რომელიც ზუსტად 4 ცალ ცალკეულ კვადრატულ მეტრს შეიცავს. ამის შემჩნევის (ანაც ალტერნატივის ვერშემჩნევის) შემდეგ ამოცანა დადის მოცემულ მატრიცაში 2x2 ტოლელემენტებიანი ქვემატრიცის მოძებნაზე. ეს მარტივად შეგვიძლია გავაკეთოთ ორი ჩადგმული ციკლის და 3 შედარების მეშვეობით: ყოველი (i, j) ისეთისთვის, რომ i < N და j < M, უნდა შევამოწმოთ ტოლობაზე შემდეგი წყვილები:

H(i, j) და H(i, j + 1)
H(i, j) და H(i + 1, j)
H(i, j) და H(i + 1, j + 1)

თუ ერთი მაინც (i, j) უჯრედისთვის ეს პირობა შესრულდა, ამოცანას დადებითი პასუხი აქვს, წინააღმდეგ შემთხვევაში კი უარყოფითი.

სავარჯიშოს სახით განვიხილოთ ანალოგიური ამოცანა, სადაც სწორი ზედაპირის ზომა KxK უნდა იყოს. პირდაპირი ალგორითმით ამ ამოცანის გადაწყვეტა O(N² * K²) დროში შეიძლება. შეეცადეთ უკეთესი ალგორითმები მოიფიქროთ.

გარჩევა მომზადებულია ელდარ ბოგდანოვის მიერ.

ამ ამოცანის გადასაწყვეტად შეგვიძლია რამდენიმე გზას მივმართოთ. დავიწყოთ სტანდარტულით, რომელიც მუშაობს მიმდევრობის სიგრძეზე დაბალი შეზღუდვის (N ≤ 20) დაწესების გამო. ვიცით რა, რომ საწყისი შეტყობინება ორობითია და სიგრძით N არის, შეგვიძლია ვცადოთ N სიგრძის ყველა ორობითი სტრიქონის განხილვა და ყოველი მათგანისთვის დაშიფვრის შედეგის გამოთვლა. თუ რომელიმე ორობითი სტრიქონისთვის ჩვენი დაშიფვრის შედეგი შემომავალ მიმდევრობას დაემთხვევა, პასუხი გვიპოვია. ვინაიდან სულ 2^N-1 სტრიქონი უნდა განვიხილოთ (მხოლოდ 0-ებისგან შემდგარი სტრიქონის დაშიფვრა შეუძლებელია), სტრიქონის დაშიფვრა კი პირდაპირი გზით O(N²)-ში ხდება, მივიღებთ O(2^N * N²) ალგორითმს. დაშიფვრის რეალიზაცია უფრო სწრაფადაც, O(N) დროში შეიძლება, მაგრამ დიდი N-ებისთვის ეს მიდგომა მაინც უვარგისია.

მცირე დაკვირვების საფუძველზე შეიძლება ბევრად უფრო მარტივი ალგორითმის ჩამოყალიბება. დაშიფვრის ალგორითმიდან გამომდინარე, ყველა ის პოზიცია, სადაც დაშიფრულ მიმდევრობაში 0 წერია, საწყის ორობით შეტყობინებაში 1-ს უნდა შეიცავდეს, დანარჩენები კი 0-ებს. მაგალითად, "3 2 1 0 1 0" მიმდევრობა რამის დაშიფრულ ვარიანტს თუ წარმოადგენს, ეს იქნება 000101 ორობითი სტრიქონი. დაგვრჩენია დავშიფროთ ეს სტრიქონი და შევამოწმოთ, მართლა მივიღებთ შემომავალ მიმდევრობას თუ არა.

კიდევ ერთი მიდგომა სწორი დაშიფრული მიმდევრობების სიღრმისეულ ანალიზს ეფუძნება. თუ დააკვირდებით, რა მიმდევრობები შეიძლება მივიღოთ დაშიფვრის ალგორითმის შედეგად, შეგვიძლია შემდეგი კრიტერიუმები გამოვყოთ:
1) მიმდევრობის ყველა მეზობელ წყვილს შორის სხვაობა 1 ან 0 არის;
2) მიმდევრობაში ერთი მაინც 0 უნდა იყოს;
3) მიმდევრობის ლოკალური მინიმუმები მხოლოდ 0-ებში უნდა იყოს;
4) ორი მეზობელი ელემენტი თუ ტოლია, ისინი ლოკალური მაქსიმუმი უნდა იყონ და მათგან ორივე მხარეს უნდა იყოს 1-ით ნაკლები ელემენტები (ანუ მაქსიმუმ ორი მიყოლებით მდგომი ტოლი ელემენტი შეიძლება გვქონდეს და თან კიდურა წევრები არ უნდა იყონ).

ამ ამოხსნის იმპლემენტაცია წინაზე ბევრად რთულია და საწყისი შეტყობინების აღსადგენად მაინც სჭირდება იმის შემჩნევა, რომ საწყისი სტრიქონის 1-ებს მოცემული მიმდევრობის 0-ები შეესაბამება, მაგრამ შეჯიბრის დროს იყო ასეთი მეთოდით ამოხსნის წარმატებული მცდელობებიც.

სავარჯიშოს სახით გთავაზობთ დაშიფვრის O(N) სირთულის ალგორითმი მოიფიქროთ და ბოლო აღწერილი მეთოდის რეალიზაცია სცადოთ.

გარჩევა მომზადებულია ელდარ ბოგდანოვის მიერ.

ამოცანის პირობა მარტივად შეგვიძლია გადავთარგმნოთ გრაფთა თეორიის ენაზე: გრაფის წვეროებად განვიხილოთ თითოეული ბაზა და ორ ბაზას შორის იყოს არამიმართული წიბო მხოლოდ იმ შემთხვევაში, თუ მათ შორის მანძილი არ აღემატება მოცემულ D რიცხვს. ჩვენი მიზანია ვიპოვოთ ისეთი წყვილების რაოდენობა ამ წვეროებს შორის, რომელთა შორისაც არ არსებობს გზა, ანუ ერთიდან მეორე მიღწევადი არ არის არც სხვა წვეროების გავლით. იმისათვის, რომ ორ წვეროს შორის გზა არსებობდეს, აუცილებელი და საკმარისი პირობაა, რომ ეს 2 წვერო იყოს ერთსადაიმავე ბმულ კომპონენტში. შესაბამისად, თუ ვიპოვით ამ გრაფის ბმული კომპონენტების ზომებს, ამოცანის პასუხს მარტივად დავადგენთ: თუ გვაქვს k ცალი ბმული კომპონენტი ზომებით a1, a2, …, ak, მაშინ ისეთი წყვილების რაოდენობა, რომლებში შემავალი წვეროები ერთსადაიმავე ბმულ კომპონენტში არაა, არის a1*a2+a1*a3+…+a1*ak + a2*a3+…+a2*ak + … + a(k-1)*ak, რაც ადვილად შეიძლება დაითვალოს O(N²) დროში ორი for ციკლით. ამის პოვნა ასევე შესაძლებელია O(N) დროში შემდეგნაირად: თუ დავაკვირდებით, ჩვენი საძიებელი სიდიდე იგივეა, რაც ამ წვეროების ყველა წყვილს გამოკლებული ის წყვილები, რომლებიც იგივე ბმულ კომპონენტში არიან, ანუ N*(N-1)/2 – a1*(a1-1)/2 – a2*(a2-1)/2 - … - ak*(ak-1)/2 და ცხადია, k ≤ N, ანუ საძებნი ჯამის დათვლა მართლაც მოხერხდება O(N) დროში. ასევე შეგვიძლია ვიპოვოთ არა თუ ბმული კომპონენტების ზომები, არამედ თითოეული წვერო რომელ ბმულ კომპონენტში შედის, რის შემდეგაც თითოეული წყვილის განხილვით და მათი კომპონენტების ნომრების შედარებით დავითვლით განსხვავებულ კომპონენტებში მოთავსებული წყვილების რაოდენობას.

დაგვრჩა გასარკვევი მხოლოდ ის, თუ როგორ ვიპოვოთ გრაფში ბმული კომპონენტების ზომები. ამის გაკეთება შესაძლებელია BFS-ითაც (სიგანეში ძებნა) და DFS-ითაც (სიღრმეში ძებნა). ორივე მათგანი წვეროების და წიბოების რაოდენობის მიმართ წრფივ დროში მუშაობს, რაც ჩვენს შემთხვევაში არის O(N²) (უარეს შემთხვევაში თითოეული წვერო შეერთებულია ყველა დანარჩენთან). აქ განვიხილოთ პირველი მათგანი: მივყვეთ ციკლით წვეროებს და თითოეულისთვის გავაკეთოთ შემდეგი რამ: გავუშვათ ამ წვეროდან სიგანეში ძებნა და დავთვალოთ იმ წვეროების რაოდენობა, რომლებშიც მოვხდებით ამ საწყისი წვეროთი. შემდეგ მოვნიშნოთ თითოეული ეს წვერო, რათა ამ წვეროებში შემდეგში აღარ გადავიდეთ.

გარდა ამ ყველაფრისა, არის კიდევ ერთი მნიშვნელოვანი დეტალი - გრაფის შენახვის გზა. ვინაიდან გრაფი შეიძლება სრულიც აღმოჩნდეს, მისი მეზობელთა სიებით შენახვა წამგებიანია. ამრიგად, ოპტიმალური გზა მის შესანახად არის მოსაზღვრეობის მატრიცა. საინტერესოა, რომ გრაფი შეიძლება ცხადად საერთოდაც არ შევინახოთ და იმის დადგენა, არის თუ არა A და B წვეროები შეერთებული ერთმანეთთან, მოვახდინოთ უშუალოდ როდესაც ეს ინფორმაცია დაგვჭირდება. რა თქმა უნდა, შესამოწმებლად გარკვეული ოპერაციების (მათ შორის მანძილის D-სთან შედარება) ჩატარება მოგვიწევს, მაგრამ ამით მეხსიერებას სერიოზულად დავზოგავთ.

გარჩევა მომზადებულია ლაშა ლაკირბაიას მიერ.

დავალაგოთ მოცემული შემთხვევები დროის მიხედვით, გადავნომროთ ამ ახალი მიმდევრობით და შემდეგ გამოვიყენოთ დინამიური პროგრამირების პრინციპი. DP(i, j, k), i < j < k, იყოს ქვეამოცანის პასუხი (ანუ მინიმალური შესაძლო მაქსიმალური სიჩქარე), თუ ერთ-ერთი თეფში ბოლოს შემჩნეული იყო i-ურ შემთხვევაში, მეორე j-ურში და მესამე k-ურში. მაგალითად, DP(2, 8, 9) არის ის მინიმალური შესაძლო მაქსიმალური სიჩქარე, რომელიც უნდა ჰქონოდა სამ მფრინავ თეფშს, რომ შესაძლებელი გამხდარიყო, მათგან ერთ-ერთი ბოლოს მე-2 შემთხვევაში დაენახათ, მეორე მე-8-ში და მესამე მე-9-ში. (2, 8, 9) არის შესაბამისი მდგომარეობა.

დინამიური პროგრამირების გამოყენებისას ხშირად ვაკავშირებთ სხვადასხვა ქვეამოცანების პასუხებს რეკურენტული ფორმულებით. ამჯერად ცოტა განსხვავებული მიდგომა ავირჩიოთ და ამოვწეროთ ყველა ისეთი DP(i', j', k'), რომლის გამოთვლას სჭირდება DP(i, j, k)-ს მნიშვნელობა.

პირველ რიგში, მესამე თეფში შეიძლება k-ური შემთხვევიდან გადაფრინდეს (k+1)-ესკენ, (i, j, k+1) მდგომარეობა მივიღოთ. ამრიგად, DP(i, j, k+1) შეიძლება იყოს ტოლი MAX(DP(i, j, k), [დრო, საჭირო k-ური შემთხვევიდან (k+1)-ესკენ გადასაფრენად])-ის. არაა აუცილებელი ის მართლა ამ სიდიდის ტოლი აღმოჩნდეს, ვინაიდან შეიძლება სხვა მდგომარეობიდან უფრო მცირე მნიშვნელობა მივიღოთ.

შესაძლებელია, მეორე თეფში გადაფრინდეს (k+1)-ე შემთხვევის ადგილზე, ანუ (i, k, k+1) მდგომარეობა მივიღოთ. და ასევე შეიძლება (k+1)-ე შემთხვევის ადგილზე პირველ თეფში წავიდეს, რითაც მიიღება (j, k, k+1) მდგომარეობა. ჩვენ აქ არ ვიხილავთ ვარიანტებს, როდესაც ერთ-ერთი თეფში (k+1)-ზე უფრო გვიანდელ შემთხვევის ადგილზე მიფრინავს, ვინაიდან (k+1)-ეში რომელიმე აუცილებლად უნდა გამოჩენილიყო და შესაბამისად შეგვიძლია მხოლოდ ასეთი მდგომარეობები განვიხილოთ (i, j, k)-დან.

დარჩა ორი შეკითხვა - რა მიმდევრობით განვიხილოთ ეს მდგომარეობები და საბაზისო შემთხვევები რა არის. ვინაიდან ყოველ გადასვლაში მესამე ინდექსი ყოველთვის იზრდება, მდგომარეობები შეგვიძლია განვიხილოთ მესამე ინდექსის ზრდადობის (და წინა ორის ნებისმიერი) მიმდევრობით. უფრო რთულია საბაზისო შემთხვევების გამოვლენა და მათთვის მნიშვნელობის გამოთვლა. ალბათ იმიტომ, რომ ასე განსაზღვრულ მდგომარეობებში ცხადად საბაზისო არც ერთი არაა :) მაგალითად, (98, 99, 100) მდგომარეობის შესაბამისი სიჩქარის მინიმუმი შეიძლება მიიღებოდეს მაშინ, როდესაც მეორე თეფშმა მოიარა 1..97 შემთხვევები და გადავიდა 99-ეში, ხოლო დანარჩენი ორი თეფში პირველად გამოჩნდა შესაბამისად 98-ე და მე-100 შემთხვევებში. მაგრამ შეიძლება მინიმუმი მიიღწეოდეს მაშინ, როდესაც სამივემ კაი ხანი იტრიალა სხვადასხვა შემთხვევების ადგილებზე.

ამ საბაზისო მნიშვნელობების პოვნა არც ისე მარტივია, ამიტომ ცოტა შევცვალოთ ჩვენი მდგომარეობები. კერძოდ, დავუშვათ, რომ i და j ინდექსები იყონ არა მარტო შემთხვევების ნომრები, არამედ სპეციალური ინდექსი X-იც. ამ ინდექსის მნიშვნელობა იქნება, რომ შესაბამისი თეფში ჯერ საერთოდ არ გამოჩენილა არც ერთი შემთხვევის ადგილზე. მაგალითად, (X, 2, 5) იყოს ისეთი მდგომარეობა, რომელშიც ერთ-ერთი თეფში საერთოდ არ უნახავთ მე-5 შემთხვევის ჩათვლით, მეორე მე-2 შემთხვევაში იყო ბოლოს და მესამე მე-5-ეში. ჩავთვალოთ, რომ X ინდექსიდან ნებისმიერ ადგილზე გამოჩენა 0 დროშია შესაძლებელი. მაშინ შეგვიძლია საბაზისოდ ჩავთვალოთ მდგომარეობა (X, X, 1) - პირველ შემთხვევაში რომელიღაც თეფში მონაწილეობდა, დანარჩენი თეფშები არ გვინახახავს, DP(X, X, 1) არის 0. შემდეგ აღწერილი გადასვლების მეშვეობით შევძლებთ მივიღოთ ყველა DP(i, j, k) და DP(i, j, N)-ებს შორის მინიმალური იქნება ამოცანის პასუხი.

ვინაიდან ჩვენს დინამიურ სქემაში O(N³) მდგომარეობაა და თითოეულის დამუშავება O(1) დროში ხდება, ამ ალგორითმის მუშაობის დრო O(N³) არის. პრობლემა იმაშია, რომ მისთვის საჭირო მეხსიერებაც O(N³) არის და ამხელა მოცულობის მონაცემებს 64 მეგაბაიტში ვერ შევინახავთ. დავაკვირდეთ, რომ მესამე ინდექსს მხოლოდ ერთით ვზრდით ხოლმე, ანუ რეალურად ალგორითმის მსვლელობის პროცესში მხოლოდ მიმდინარე k და (k+1)-ის შესაბამისი მდგომარეობების პასუხები გვჭირდება. ამრიგად, შეგვიძლია მხოლოდ O(N²) მდგომარეობის პასუხი შევინახოთ და როდესაც k-ს ვზრდით, წინა მონაცემები წავშალოთ.

გარჩევა მომზადებულია ელდარ ბოგდანოვის მიერ.

ამოცანა გვთხოვს, ვიპოვოთ მინიმალური ფართობის მართკუხედი, რომელიც შემოსაზღვრავს მოცემული წრეწირების სიმრავლეს. ვინაიდან ჩვენი წრეები ერთნაირი რადიუსისაა, ადვილი დასანახია* რომ ასეთი მართკუხედის რომელიმე გვერდი პარალელური უნდა იყოს წრეწირთა ერთ-ერთი წყვილის საერთო მხების. ასევე რადიუსების ტოლობიდან გამომდინარეობს, რომ ეს საერთო მხები ყოველი წყვილისთვის მათ ცენტრებზე გამავალი წრფის პარალელურია. განვიხილოთ წრეწირების ყოველი წყვილი და ყოველი მათგანისთვის ვიპოვოთ ამ წრფის დახრის კუთხე alpha. მოვატრიალოთ კოორდინატთა სისტემა ამ კუთხით - მაშინ ეს წრფე ჰორიზონტალური გახდება. ვინაიდან ცნობილია, რომ მართკუხედის ერთი გვერდი ამ წრფის პარალელური უნდა იყოს და შესაბამისად მეორე - პერპენდიკულარული, ვიპოვოთ ახალ კოორდინატთა სისტემაში მინიმალური და მაქსიმალური X და Y კოორდინატების მქონე წრეწირების ცენტრები. აღვნიშნოთ მაქსიმალური X maxX-ით, მინიმალური minX-ით და Y-ებისთვის ანალოგიურად. ამ კოორდინატთა სისტემაში მოცემული წერტილების შემომსაზღვრელი მართკუთხედის გვერდების სიგრძეები იქნება (maxX-minX) და (maxY-minY), ხოლო ვინაიდან საჭიროა, რომ არა თუ წერტილები, არამედ მათზე აგებული წრეწირებიც შემოვსაზღვროთ, ამ სიდიდეებს 2R ემატებათ. გამოდის, რომ ასე მოტრიალებული მართკუხედის მინიმალური ფართობია (maxX-minX+2R)*(maxY-minY+2R). ყველა შესაძლო კუთხისთვის ამ სიდიდის მინიმუმი არის ამოცანის პასუხი.

საკოორდინატო სიბრტყის alpha კუთხით მოტრიალება (alpha ითვლება X ღერძისგან ისრის საწინააღმდეგო მიმართულებით) ხორციელდება შემდეგი ფორმულების მეშვეობით:

x' = x * cos(alpha) + y * sin(alpha)
y' = -x * sin(alpha) + y * cos(alpha)

ანუ ძველ კოორდინატთა სისტემაში (x, y) წერტილი alpha კუთხით მოტრიალებულ სისტემაში (x', y') წერტილში გარდაისახება.

ასევე დააკვირდით, რომ alpha კუთხის გამოთვლა და შემდეგ მისი სინუსის და კოსინუსის აღება საჭირო არაა. თუ ვიხილავთ (X1, Y1) და (X2, Y2) წერტილებზე გამავალ წრფეს, მისი დახრის კუთხის სინუსია (Y2 - Y1) / dist, ხოლო კოსინუსი - (X2 - X1) / dist, სადაც dist მანძილია ამ ორ წერტილს შორის.

საბოლოო ჯამში, O(N²) დახრის კუთხეს ვიხილავთ და თითოეულისთვის O(N) ოპერაციაში ვახდენთ საკოორდინატო სიბრტყის მოტრიალებას და პასუხის გამოთვლას, ამიტომ ალგორითმის სირთულე არის O(N³).

*ადვილი დასანახია, მაგრამ რთული დასამტკიცებელი. საინტერესოა, ვინმე თუ მოიფიქრებთ ამ დებულების დამტკიცებას (ან კონტრმაგალითს :) ).

გარჩევა მომზადებულია ელდარ ბოგდანოვის მიერ.