#	ამოცანა	გარჩევის ავტორი
A	Automated Telephone Exchange	ელდარ ბოგდანოვი
B	Black Square	ხატია ჭითაშვილი
C	Cube Coloring	ელდარ ბოგდანოვი
D	Dice	ელდარ ბოგდანოვი
E	Electrification	-
F	Flat	ელდარ ბოგდანოვი
G	Galaxy Interconnection	ირაკლი მერაბიშვილი
H	High Security	ირაკლი მერაბიშვილი
I	Immediate Delivery	ელდარ ბოგდანოვი
J	John’s Inversions	ნიკა ჯიმშელეიშვილი
K	Kids Like Cakes	ნიკა ჯიმშელეიშვილი

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

ამოცანაში გვთხოვენ ორი ცალი ორნიშნა რიცხვის პოვნას, რომელთა ჯამი მოცემული სამნიშნა N-ის ტოლია. ორნიშნა რიცხვებში დაშვებულია 0 პირველ პოზიციაში, ანუ 00, 01, …, 09 ასევე ორნიშნა რიცხვებად ითვლება.

ამოხსნა ტრივიალურია: გადავარჩიოთ ციკლით 0-დან 99-ის ჩათვლით პირველი რიცხვი და შემდეგ ანალოგიურად მეორე რიცხვი და შევადაროთ მათი ჯამი N-ს. მოცემულ შეზღუდვებში ეს სრულიად საკმარისია, თუმცა ეს შეგვიძლია დავიყვანოთ ერთ ციკლამდე (მეორე რიცხვი ცალსახად განისაზღვრება როგორც N-ს მინუს პირველი რიცხვი და შეგვიძლია შევამოწმოთ რომ [0, 99] შუალედშია), ანაც საერთოდ O(1)-ში ამოვხსნათ მარტივი მსჯელობით.

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

ამოცანაში შეგვიძლია გამოვყოთ ორი შემთხვევა: პირველი, როცა შემოსულ სტრიქონში არცერთი შავი ბლოკი არაა და მეორე - როცა შემოსული სტრიქონი შეიცავს შავ ბლოკებს.
ორივე შემთხვევაში შეგვიძლია დავადგინოთ, რა დროს გვექნება უნიკალური ან შეუძლებელი სიტუაცია და ყველა დანარჩენი გაურკვეველს მიეკუთვნება.

პირველი შემთხვევა:
მოცემული k-ური სტრიქონი საწყის მართკუთხედს ორ - ზედა და ქვედა მართკუთხედად გაყოფს.

უნიკალური სიტუაცია: უნიკალური შემთხვევა გვექნება მხოლოდ მაშინ, თუ ამ ორი მართკუთხედიდან მხოლოდ ერთში შეიძლება ჩავდგათ მოცემული კვადრატი და ისიც მხოლოდ ერთნაირად. ეს კი მოხდება მხოლოდ მაშინ თუ ორი მართკუთხედიდან რომელიმე ერთის გვერდები ზუსტად S-ის ტოლი იქნება, ხოლო მეორე მართკუთხედში ეს კვადრატი ვერ ჩაეტევა.

შეუძლებელი სიტუაცია: როცა კვადრატის ჩასმა არ შეგვიძლია არც სტრიქონის მაღლა და არც დაბლა, ანუ როცა ორივე მიღებული მართკუთხედის სიმაღლე კვადრატის გვერდზე ნაკლებია (k - 1 < s და m - k < s).

ყველა დანარჩენი სიტუაცია გაურკვეველს მიეკუთვნება - ანუ რამდენიმენაირად შეიძლება კვადრატის ჩასმა ამ ორ მიღებულ მართკუთხედში.

მეორე შემთხვევა:
შეუძლებელი სიტუაცია შეიძლება იყოს მხოლოდ ორ შემთხვევაში: პირველი შემთხვევა - როცა მოცემულ სტრიქონში შავი ბლოკების რამდენიმე მიმდევრობაა, ანუ მიიღება რამდენიმე შეკრული შავი ფიგურა და არა ერთადერთი. მეორე შემთხვევა - როცა სტრიქონში შავი ბლოკების მიმდევრობის სიგრძე არ უდრის ჩასახატი კვადრატის გვერდს.

თუ კვადრატის ჩახატვა შესაძლებელია, მაშინ ვნახოთ, შეიძლება თუ არა მისი უნიკალურად ჩასმა:
კვადრატის უნიკალურად ჩასმა სამ შემთხვევაშია შესაძლებელი:
1) როცა საწყისი მათკუთხედის სიმაღლე ჩასასმელი კვადრატის გვერდის ტოლია.
2) როცა k = 1 ან k = m, ანუ კვადრატი სულ ზემოთ იწყება ან სულ ქვემოთ მთავრდება.
3) როცა ჩასასმელი კვადრატის გვერდი 1-ის ტოლია, ამ შემთხვევაში ჩასახატი კვადრატი უკვე მოცემულ სტრიქონშია.
ყველა დანარჩენი შემთხვევა გაურკვეველს მიეკუთვნება.

გარჩევა მომზადებულია ხატია ჭითაშვილის მიერ.

ეს ამოცანა ამომხსნელისგან ბევრად უფრო მეტ ტექნიკას ელოდა, ვიდრე იდეურ სირთულეს წარმოადგენდა. ავიღოთ პირველივე წახნაგის “ხილვა” და გადავარჩიოთ მისი მეზობელი ოთხი წახნაგის მიმდევრობა (ანუ ABCDE ხილვისთვის BCDE A-ს გარშემო რა მიმდევრობით დალაგდება). ასეთი სულ 4! კომბინაციაა, მაგრამ რეალურად ერთ-ერთი მეზობელი წახნაგი შეგვიძლია ნებისმიერ ადგილას, მაგალითად წინა წახნაგის მარჯვნივ დავაფიქსიროთ და 3! ვარიანტის გადარჩევა დაგვრჩება. ეს პირველი წახნაგი ჩვენი ასაგები კუბის წინა წახნაგი იყოს (ის, რომელიც პასუხში მე-3 პოზიციაში გამოგვაქვს). მისი მეზობლების დაფიქსირების შემდეგ ჩვენ გაურკვეველი გვრჩება კუბის ერთადერთი წახნაგი - უკანა, რომელიც პირველ ხილვაში არ ჩანს. გადავარჩიოთ, დარჩენილი 5 ხილვიდან რომელი იქნება უკანა წახნაგის ხილვა. მისი მეზობელი წახნაგების სიმრავლე ზუსტად უნდა ემთხვეოდეს პირველი ხილვის მეზობელი წახნაგების სიმრავლეს, წინააღმდეგ შემთხვევაში ეს ორი ხილვა ვერ იქნება ერთსადაიმავე კუბის მოპირდაპირე წახნაგების ხილვები. შესაბამისი ხილვის შერჩევის შემდეგ კუბის ყველა წახნაგი ცნობილია და უნდა შევამოწმოთ, რომ დარჩენილი 4 ხილვა შეიძლება შევუსაბამოთ კუბის დანარჩენ წახნაგებს. გადავარჩიოთ, რომელი ხილვა რომელ წახნაგს შევუსაბამოთ (4! ვარიანტი) და შევამოწმოთ, რომ ხილვა თავსებადია აგებული კუბის ამ წახნაგთან - ამისთვის მისი წინა წახნაგი კუბის შესაბამის წახნაგს უნდა დაემთხვას და ასევე უნდა დაემთხვას მეზობელ წახნაგთა სიმრავლეები.

ამგვარად, 3! * 5 * 4! ვარიანტიდან უნდა ვიპოვოთ ისეთები, რომლებშიც ხილვები თავსებადია ერთმანეთთან. შეიძლება შედეგად რამდენიმე სტრიქონი მივიღოთ, რომლებიც ტოლი არაა, მაგრამ მაინც ერთსადაიმავე კუბს აღწერენ, მაგალითად BEACFD და AEDCBF. ამ შემთხვევაში ორი კუბი ერთმანეთისგან გადატრიალებით მიიღება. ამიტომ სტრიქონების წყვილებისთვის უნდა შევამოწმოთ ერთი კუბისთვის მისი ყველა შესაძლო პოზიცია და ვნახოთ, მისი ჩანაწერი მეორე კუბისას თუ დაემთხვევა. ვინაიდან კუბს სულ 24 შესაძლო პოზიცია აქვს (წინა წახნაგის და მის ერთ-ერთი მეზობლის დაფიქსირებით კუბსაც აფიქსირებთ), შეგიძლიათ ყოველი მათგანისთვის ჩამოწეროთ კუბის ყველა წახნაგი (სულ 144 რიცხვი :) ) და ასე შეადაროთ. ანაც ჩამოწეროთ მხოლოდ 4 გადატრიალების (წინ, უკან, მარცხნივ, მარჯვნივ) დროს წახნაგები როგორ გადალაგდება და შემდეგ BFS-ით ან DFS-ით პროგრამის დასაწყისში დაადგინოთ ყველა მიღებადი პოზიცია.

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

გავიხსენოთ ამოცანა: გვაქვს N ცალი უჩვეულო კამათელი, მათგან i-ურს A_i ცალი გვერდი (წახნაგი) აქვს. აღვნიშნოთ M-ით ყველა A_i რიცხვის ჯამი. უნდა გადავანაწილოთ რიცხვები 1-დან M-ის ჩათვლით კამათლების გვერდებზე ისე, რომ ყველა კამათლის ერთდროულად გაგორებისას ამოსულ რიცხვთა ჯამის მათემატიკური მოლოდინი მაქსიმალური იყოს.

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

ვთქვათ, გვაქვს კამათელი K გვერდით და გვერდებს აწერია რიცხვები b₁, b₂, …, b_K. ამ კამათელზე ერთი გაგორების შედეგად მოსული რიცხვის მათ. მოლოდინია b რიცხვების საშუალო არითმეტიკული: (b₁ + b₂ + … + b_K) / K. გამოდის, რომ რაც უფრო დიდია გვერდების რაოდენობა, მით უფრო პატარა წონა აქვს მასზე დაწერილ თითოეულ რიცხვს საბოლოო მათ. მოლოდინში. ვინაიდან მისი მაქსიმიზაცია გვინდა, უფრო დიდი რიცხვები უფრო მცირეგვერდიან კამათლებზე უნდა მოვათავსოთ.

ამ დასკვნის შემდეგ ამოხსნა მარტივი ხდება: დავალაგოთ კამათლები გვერდების რაოდენობის მიხედვით (მათი საწყისი ნომრები შევინახოთ) და მივანიჭოთ მათ რიცხვები M-იდან ქვემოთ. დავადგინოთ ფორმულის თანახმად ჯამის მათ. მოლოდინის მნიშვნელობა და დავბეჭდოთ ისიც და კამათლებისთვის მინიჭებული რიცხვებიც კამათლების საწყისი მიმდევრობის დაცვით.

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

ამ ამოცანაში რამდენიმეოთახიანი ბინის ყველა ოთახის და დასაძინებელი ოთახების ფართობი და ბინის საფასური უნდა დაგვეთვალა მოცემული ფორმულის მეშვეობით. ყოველი ოთახი შეიძლება ყოფილიყო bedroom, bathroom, kitchen, balcony ან other ტიპის. ბინის საფასურის ფორმულა შემდეგი იყო: (ბალკონების გარდა ყველა ოთახის ფართობი + ბალკონების ფართობის ნახევარი) * 1 კვადრატული მეტრის ფასზე. გამოდის, რომ რეალურად ცალკე მხოლოდ bedroom და balcony ტიპის ოთახები უნდა დაგვემუშავებინა, დანარჩენი სამისთვის ერთიდაიგივე პროცედურა ხორციელდებოდა.

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

საკმაოდ რთულად დაწერილი პირობის ყურადღებით წაკითხვის შემდეგ შეიძლება ამოცანას მივცეთ შემდეგი ინტერპრეტაცია გრაფთა თეორიის ენაზე:
მოცემულია ბმული გრაფი, რომელშიც აუცილებლად არსებობს ერთი მაინც K სიგრძის ციკლი და რომელშიც ყველა წვეროს ჰყავს K–ზე ნაკლები რაოდენობის მეზობელი. საჭიროა ამ გრაფის წვეროები შევღებოთ ფერებით 1..K ისე, რომ ყოველი ორი მეზობელი განსხვავებული ფერის იყოს და ასევე ყოველი წვეროდან შეიძლებოდეს K-1 წიბოს გავლა ისე, რომ ყველა K (საწყისის ჩათვლით) გავლილი წვეროს ფერი სხვადასხვა იყოს.

იდეა
თუ ყოველ წვეროს ეყოლება მეზობელი, რომლის ფერიც “1–ით ნაკლებია” ამ წვეროს ფერზე (ანუ, წვეროს ფერით K უნდა ყავდეს მეზობელი ფერით K-1, …, 2–ს – 1, ხოლო 1–ს - K.), მაშინ მეორე პირობა შესრულებული იქნება.

ამოხსნა
მანამ გვაქვს შესაღები წვერო, გავიმეოროთ შემდეგი:
თუ ყველა წვერო შეუღებავია, რომელიმე შევღებოთ ფერით 1.
თუ არა: ავიღოთ წვერო, რომელსაც ყავს 1 მაინც შეღებილი მეზობელი. ვთქვათ მისი მეზობლების ფერებია 1,2,5,7,8 (K=8), დავუმატოთ ამ სიმრავლის ყველა ელემენტს 1, მივიღებთ სიმრავლეს {2, 3, 6, 8, 1}. ვიპოვოთ მეორე სიმრავლეში ისეთი, რომელსაც არ შეიცავს პირველი, მაგ.: 6. მიღებული რიცხვი “გამოდგება” ამ წვეროს ფერად, იგი განსხვავდება ყველა მეზობლის ფერისგან და ამასთან ყავს მეზობელი ფერით 5. იოლი დასანახია, რომ ამგვარად შეღებილი გრაფი დააკმაყოფილებს ამოცანაში მოთხოვნილ ორივე პირობას.

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

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

მოცემულია 5 სიმბოლოსგან შემდგარი N ცალი სტრიქონი. გვეკითხებიან ყოველი 0 ≤ k ≤ 5 თვის ვიპოვოთ ისეთ სტრიქონთა წყვილების რაოდენობა, რომლებიც განსხვავდებიან ზუსტად k პოზიციაში.

(1) განვიხილოთ გამარტივებული ამოცანა: ვიპოვოთ ერთნაირ სტრიქონთა წყვილების რაოდენობა. ამისთვის შეიძლება გამოვიყენოთ სტანდარტული სტრუქტურა Map, რომელშიც ყოველი სტრიქონისთვის შევინახავთ მის ტოლ სტრიქონთა რაოდენობას მოცემულებიდან. ყოველი სტრიქონისთვის შევამოწმებთ არის თუ არა უკვე სტრუქტურაში მისი ტოლი, თუ არ არის – დავამატებთ და შევუსაბამებთ 1–ს, თუ უკვე არის – დავუმატებთ 1–ს მის შესაბამის რიცხვს. მაგ. მიმდევრობისთვის {A, B, B, A, A, A, X} მივიღებთ შესაბამისობას: A:4, B:2, X:1. ამის შემდეგ უკვე შეგვიძლია გავიაროთ სტრუქტურაში ყოველი სტრიქონის შესაბამისი რიცხვი T და პასუხს დავუმატოთ T*(T-1)/2:
4*3/2 + 2*1/2 + 1*0/2 = 7 (დარწმუნდით, რომ წინა მაგალითში არის ზუსტად 7 ერთნაირი სტრიქონების წყვილი).

(2) იმისთვის, რომ დავთვალოთ ისეთ სტრიქონთა წყვილების რაოდენობა, რომლებიც მაგ. არ განსხვავდებიან პირველ და მეოთხე პოზიციებზე, შეგვიძლია თითოეული სტრიქონიდან წავშალოთ მე–2, მე–3 და მე–5 სიმბოლოები, ხოლო მიღებული მიმდევრობისთვის გავიმეორებთ წინა ამოცანაში გამოყენებული მეთოდი. ისეთი წყვილების დასათვლელად, რომლებსაც სულ ცოტა 2 სიმბოლო აქვთ საერთო, საკმარისი იქნება გავიმეოროთ წინამდებარე ყოველი წასაშლელი პოზიციების სამეულისთვის და მიღებული პასუხები შევკრიბოთ.
გასაგებია რომ ასეთ წყვილთა რაოდენობაში მოხვდებიან ისეთებიც, რომლებსაც სამი საერთო სიმბოლო აქვთ. მაგ.: ABCXX და ABCYY დაემთხვევიან {1,2}, {1,3} და {2,3} პოზიციებზე. თუ გვაინტერესებს ისეთი წყვილების რაოდენობა, რომლებსაც ზუსტად 2 სიმბოლო აქვთ საერთო, დამატებითი გამოთვლების გაკეთება იქნება საჭირო.

(3)
ბაზა (k=0 საწყის ამოცანაში) წინამდებარე მეთოდით ზუსტად დაითვლება ერთნაირ სტრიქონთა წყვილების რაოდენობა F(0).

გადასვლა
დათვლილია G(t): ისეთი წყვილების რაოდენობა, რომლებსაც სულ ცოტა 5-t საერთო სიმბოლო აქვთ, ასევე დათვლილია F(0), …, F(t-1).

F(t) = G(t) - C(5-0, 5-t) * F(0) - C(5-1, 5-t) * F(1) - … - C(5-(t-1), 5-t) * F(t-1).

დამტკიცებას მკითხველს ვუტოვებთ დამოუკიდებელი მუშაობისთვის.

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

ამოცანაში მოცემული გვქონდა ბმული გრაფი N ≤ 18 წვეროთი. დროის საწყის მომენტში პირველი წვეროდან მოძრაობას იწყებდა ორი ადამიანი. ისინი კურიერები არიან, წვერო 1 მათ ოფისს, ხოლო დანარჩენი წვეროები დანიშნულების ობიექტებს წარმოადგენს. კურიერები პარალელურად და დამოუკიდებლად მოძრაობენ და უნდა მოახერხონ ყოველ დანიშნულების ობიექტში მიიტანონ გზავნილი. გზავნილის მისატანად ობიექტს ერთ-ერთი კურიერი მაინც უნდა ეწვიოს. საპოვნელია მინიმალური დრო, რომელშიც მოხერხდება ყველა ობიექტში გზავნილის მიტანა.

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

ამოსახსნელად მივმართოთ დინამიურ პროგრამირებას. აღვნიშნოთ minTime (S, V) -თი მინიმალური დრო, რომელშიც ერთმა კურიერმა შეიძლება მიიტანოს S წვეროების სიმრავლის ყოველ წვეროში გზავნილები ისე, რომ ბოლოს V წვეროში აღმოჩნდეს. შეიძლება მან ამ დროს სხვა წვეროებზეც გაიაროს, მაგრამ ისინი S სიმრავლეში არ შეგვაქვს. ანუ მაგალითად თუ სულ გვაქვს 4 წვერო და S = {1, 4}, ვიცით რომ კურიერმა ნამდვილად გაიარა წვეროები 1 და 4, ხოლო 2 და 3-ში შეიძლება იყო, შეიძლება არა.

თუ გვეცოდინება ყველა შესაძლო S სიმრავლესა და V წვეროსთვის minTime(S, V)-ს მნიშვნელობა, ამოცანის შეკითხვას პასუხს მარტივად გავცემთ. ყოველი შესაძლო S-ისთვის ვიპოვოთ მინიმალური minTime(S, i) ყველა i-ს შორის და მინიმალური minTime({1,2,...,N} \ S, j) ყველა j-ს შორის, ანუ S სიმრავლის შემოვლის ყველაზე იაფი ვარიანტი და {S} სიმრავლის სრულ სიმრავლემდე დამატების შემოვლის ყველაზე იაფი ვარიანტი. კონკრეტული S-ისთვის ამ ორ მნიშვნელობას შორის მაქსიმუმია ის დრო, რომელიც დასჭირდება ორ კურიერს ყველა წვეროს შემოსავლელად, თუ პირველმა S სიმრავლის ობიექტებში მიიტანა გზავნილები, მეორემ კი დარჩენილ ობიექტებში. შესაბამისად, ყველა S-ისთვის ავირჩიოთ ამ მაქსიმუმებს შორის მინიმალური და გვექნება ამოცანის პასუხი.

როგორ გამოვთვალოთ minTime(S, V) მნიშვნელობები? თავიდან ვიპოვოთ გრაფში წვეროს ყველა წყვილს შორის უმოკლესი მანძილი. ამისთვის ფლოიდ-ვორშელის ალგორითმია ზედგამოჭრილი. დასაწყისში ყველა minTime-ს შევუსაბამოთ უსასრულობა, რაც გამოხატავს რომ ალგორითმის საწყის ეტაპზე ეს მნიშვნელობები უცნობია. minTime({1}, 1) კი 0-ის ტოლი იქნება. შემდეგ S სიმრავლეებს მივყვეთ ისეთი მიმდევრობით, რომ ყოველი სიმრავლისთვის ჯერ აუცილებლად მისი ქვესიმრავლეები იყოს განხილული, ხოლო V წვეროებს ნებისმიერი მიმდევრობით. ყოველი ({S}, V) წყვილისთვის განვიხილოთ ისეთი U წვერო, რომელიც არ შედის S სიმრავლეში და შევამოწმოთ, ნაკლები ხომ არაა minTime(S, V) + pathLen(V, U), ვიდრე minTime(S + {U}, U), რა შემთხვევაშიც განვაახლოთ minTime(S + {U}, V) მნიშვნელობა. ეს განახლება ტოლფასია იმის თქმის, რომ ჯერ S სიმრავლის შემოვლა ისე, რომ V წვეროში დავამთავროთ, და შემდეგ V-დან U-ში გადასვლა არის უფრო სწრაფი ვარიანტი S+{U} სიმრავლის შემოვლის U-თი დამთავრებით, ვიდრე რაც იყო ცნობილი ალგორითმის მუშაობის მიმდინარე მომენტამდე.

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

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

განვიხილოთ ბარათების ყოველი წყვილი (i,j).

არის 2 შემთხვევა:
1) კარგი შემთხვევა: r[i] ≤ r[j] და b[i] ≤ b[j] (ან პირიქით).
ამ შემთხვევაში თუ ბარათებს დავალაგებთ r[i] ების ზრდადობით (ტოლობის შემთხვევაში b[i] ების ზრდადობით), მაშინ ასეთი წყვილისთვის ინვერსიების რაოდენობა იქნება 0, ანუ საუკეთესო შესაძლო.

2) ცუდი შემთხვევა: r[i] > r[j] და b[i] < b[j] (ან პირიქით)
ამ დროს ეს 2 ბარათი როგორც არ უნდა დავალაგოთ, გვექნება 1 ინვერსია. ასეთი წყვილებისთვის დალაგების თანმიმდევრობას აზრი არ აქვს.

შესაბამისად, ჩვენ თუ დავალაგებთ ბარათებს ისე, როგორც კარგ შემთხვევაშია აღწერილი, გვექნება ინვერსიების მინიმალური რაოდენობა.

დასათვლელი რჩება მხოლოდ ერთ მასივში ინვერსიების რაოდენობა, რაც ძალიან ცნობილი ამოცანაა. N ≤ 100000, ამიტომ საჭიროა სწრაფი ამოხსნა. ეს ამოცანა O(NlogN) დროში იხსნება რამდენიმე გზით, მათ შორის:
1) QuickSort ის ოდნავ შეცვლით.
2) MergeSort ის ოდნავ შეცვლით.
3) ინტერვალთა ხეებით (ფენვიკის ხეც საკმარისია).

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

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

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

საჭიროა მხოლოდ ამ ყველაფრის აკურატული რეალიზაცია.

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