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

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

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

ალგორითმული სირთულის თვალსაზრისით ოპტიმალური ალგორითმი იქნება პრეფიქს ხეების გამოყენება. მათი საშუალებით დასმული ამოცანის ამოხსნა შეიძლება O(N*L) დროში.

ერთი მომენტი, რომელზეც მინდა თქვენი ყურადღების გამახვილება, არის ინფორმაციის შეტანა. ჩვენს შემთხვევაში პირველი ხაზი შეიცავს რიცხვს N და შემდეგ უნდა შევიტანოთ N ცალი ხაზი, რომლებზეც შეიძლება ჰარის სიმბოლოებიც იყოს. ასეთ შემთხვევაში უნდა გამოვიყენოთ ხაზის სრულად წაკითხვის რომელიმე მეთოდი, მაგალითად readln პასკალში, gets ან cin.getline C++–ზე და Scanner კლასის nextLine ან BufferedReader კლასის readLine მეთოდები Java–ზე. გთავაზობთ საკმაოდ ხშირი შეცდომის შემცვლელ კოდის ნაწყვეტებს სხვადასხვა ენებზე:

cin >> N;
for(int i = 0; i < N; i++) cin.getline(school[i]);

scanf("%d",&N);
for(int i = 0; i < N; i++) gets(school[i]);

Scanner in = new Scanner(new File("semifinals.in"));
int N = in.nextInt();
for(int i = 0; i < N; i++) school[i] = in.nextLine();

read(N);
for i := 1 to N do readln(school[i]);

ყველა ამ კოდში არის დაშვებული ერთიდაიგივე შეცდომა: N-ის შეტანის შემდეგ პროგრამა ჯერ არ გადასულა შესატანი მონაცემების შემდეგ ხაზზე და პირველი getline/gets/nextLine/readln ბრძანების შესრულებისას წავიკითხავთ არა თუ მეორე ხაზზე მყოფ სტრიქონს, არამედ პირველი ხაზის დასასრულს – ცარიელ სტრიქონს. ამგვარად, N–ის წაკითხვის შემდეგ ერთი ზედმეტი ხაზის შეტანა გვჭირდება, რომ წაკითხვამ შემდეგ ხაზზე გადაინაცვლოს.

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

ჩამოვაყალიბოთ ამოცანა კარაოკეების და სიმღერის ნიჭის მაჩვენებლების გარეშე: მოცემული 2N რიცხვი უნდა დავყოთ ორ ტოლ სიმრავლედ ისე, რომ პირველში უდიდესი K ცალის და მეორეში უდიდესი K ცალის ჯამი იყოს

ა) მინიმალური
ბ) მაქსიმალური

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

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

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

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

ამოცანის მთავარ სირთულეს წარმოადგენს ავტობუსის მოძრაობის სიმულაცია, რომელიც წარმოდგენილია 'F', 'L' და 'R' სიმბოლოებით. 'F' - ნიშნავს მოძრაობის მიმართულებით ერთი უბნის გავლას, 'L' - მოძრაობის მიმართულების მარცხნივ შეცვლას და ერთი უბნის გავლას, და 'R' - მოძრაობის მიმართულების მარჯვნივ შესვლას და ერთი უბნის გავლას. მოძრაობის მარტივად სიმულაციისთვის დავიმახსოვროთ ავტობუსის მიმდინარე კოორდინატები (X , Y) და მიმართულების ვექტორი (V_x , V_y). შემდეგ უბანში გადასვლისას ავტობუსის კოორდინატები იქნება (X+V_x , Y+V_y).

მიმართულების ვექტორის ოთხი შესაძლო მნიშვნელობა გვაქვს:

(0 , 1) - ჩრდილოეთი
(-1 , 0) - დასავლეთი
(0 , -1) - სამხრეთი
(1 , 0) - აღმოსავლეთი

მიმართულების მარცხნივ შეცვლა იგივეა, რაც მიმართულების ვექტორის 90 გრადუსით მარცხნივ მოტრიალება, მარჯვნივ შეცვლა კი - მიმართულების ვექტორის 90 გრადუსით მარჯვნივ მოტრიალება.

(V_x , V_y) ვექტორის 90 გრადუსით მარცხნივ მოტრიალებისას მიიღება (-Vy , Vx) ვექტორი, ხოლო, მისი მარჯვნივ მოტრიალებისას მიიღება (V_y , -V_x) ვექტორი. შესაბამისად ავტობუსის მოძრაობასაც ადვილად აღვწერთ.

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

განვიხილოთ სტრიქონი, რომელიც მიიღება S სტრიქონის თავის თავთან კონკატენაციისას. ამოცანის პირობაში მოყვანილი მაგალითისთვის ესაა სტრიქონი ABRACADABRAABRACADABRA. როგორ შეგვიძლია მისი შემოკლება ისე, რომ ისევ 2 ცალ ABRACADABRA–ს შეიცავდეს? პირველ რიგში, შეგვიძლია მეორე S-ის საწყისი A სიმბოლო ამოვშალოთ, ვინაიდან პირველი S ამ ასოთი მთავრდება და მეორე სტრიქონი მაინც აიგება:

ABRACADABRA
          ABRACADABRA

მომდევნო დაკვირვების შედეგად შეგვიძლია A-ს მაგივრად მთელი ABRA ამოვშალოთ, ვინაიდან S სტრიქონი ამ სიმბოლოებით მთავრდება და მეორე სტრიქონი შეგვიძლია იქ დავიწყოთ:

ABRADACABRA
       ABRACADABRA

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

გაითვალისწინეთ, რომ ზოგიერთი S-ისთვის მისი თავის თავთან კონკატენაცია შეიძლება ისეთ შედეგს იძლეოდეს, რომელშიც 2–ზე მეტი ქვესტრიქონი არის S-ის ტოლი. მაგალითად, S=AAA სტრიქონისთვის მისი გაორმაგება AAAAAA უკვე 4–ჯერ შეიცავს S-ს. მაგრამ როდესაც მას შეამოკლებთ ზემოთაღწერილი პროცესის ანალოგიურად, მიიღებთ სტრიქონს AAAA, რომელშიც ზუსტად 2 S-ის შესვლაა.

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

L + (K - 1) * (L - P)

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

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

უფრო ზოგადი მიდგომაა ჰეშირება, ამ შემთხვევაში კი რაბინ–კარპის ალგორითმი. იდეა ასეთია: შემოვიღოთ ჰეშ–ფუნქცია H(S), რომელიც სტრიქონს იღებს პარამეტრად და აბრუნებს მთელ რიცხვს [0..M) შუალედში, სადაც M-ს თვითონ ავირჩევთ. ფუნქცია უნდა იყოს დეტერმინირებული, ანუ ერთსადაიმავე სტრიქონზე ორჯერ გამოძახებისას ერთსადაიმავე შედეგს აბრუნებდეს. ასევე ის ისეთ რიცხვებს უნდა უსაბამებდეს სტრიქონებს, რომ ყველა შესაძლო სტრიქონისთვის, რომელიც შეიძლება განვიხილოთ ალგორითმის მსვლელობის პროცესში, მნიშვნელობები რაც შეიძლება თანაბრად განაწილდეს. მაგალითად, ფუნქცია, რომელიც M=100 შემთხვევაში შესაძლო სტრიქონების ნახევარზე 5–ს აბრუნებს, ცუდი ჰეშ–ფუნქციაა. და ბოლოს, ფუნქცია ისეთი უნდა იყოს, რომ თუ ვიცით H(S), შევძლოთ O(1) დროში H(S+c) და H(c+S)–ის პოვნა, სადაც c რაღაც სიმბოლოა (ზოგად შემთხვევაში უნდა შეგვეძლოს სტრიქონის დასაწყისიდან ერთი სიმბოლოს ამოშლა და ბოლოში ერთი სიმბოლოს ჩამატება ისე, რომ O(1)-ში მოხდეს ჰეშ–ფუნქციის გადათვლა). ორი განსხვავებული სტრიქონისთვის H ფუნქციის მნიშვნელობები შეიძლება დაემთხვას, მაგრამ რაც უფრო დიდია M, მით უფრო მცირეა ამის ალბათობა.

დავუშვათ, შევარჩიეთ ასეთი H(S) ფუნქცია და M არის მაგალითად მილიარდის ტოლი. მივყვეთ S სტრიქონს მარცხნიდან და ვიპოვოთ H(S(1)), H(S(2)), H(S(3)), ..., H(S(L-1)), სადაც S(i)–თი აღნიშნულია S სტრიქონის i სიგრძის პრეფიქსი, ხოლო L–ით S სტრიქონის სიგრძე. დააკვირდით, რომ H(S(i))–ის გამოთვლის შემდეგ H(S(i+1)) შეგვიძლია O(1) დროში გამოვთვალოთ, ვინაიდან ეს სტრიქონზე ერთი სიმბოლოს დამატებას ნიშნავს. ამრიგად, ყველა მნიშვნელობის გამოთვლა ერთად მოხდება O(L) დროში. ასევე გამოვთვალოთ H(S(-1)), H(S(-2)), ..., სადაც S(-i) არის S სტრიქონის i სიგრძის სუფიქსი. ამასაც ანალოგიურად მოვახერხებთ ჯამურ O(L) დროში. ახლა შევადაროთ H(S(L-1)) და H(S(-(L-1)). თუ ეს მნიშვნელობები ტოლია, შევადაროთ შესაბამისი სტრიქონებიც. თუ სტრიქონები დაემთხვევა, P–ს მნიშვნელობა L-1 ყოფილა და პროცესი დამთავრდება. თუ არა, შევამოწმოთ H(S(L-2)) და H(S(-(L-2)) და ასე შემდეგ. ერთი შეხედვით, ზედმეტი თავის ტკივილი გავიჩინეთ, არადა სტრიქონების შედარება მაინც გვიწევს და შესაბამისად ისევ კვადრატული ალგორითმი გვაქვს. აქ საქმეში უკვე ალბათობის თეორია შედის: თუ ჰეშ–ფუნქცია კარგად გვქონდა შერჩეული, მაშინ იმის ალბათობა, რომ H–ის მნიშვნელობები ტოლია, ხოლო სტრიქონები არა, ძალიან მცირეა. ისეთი S სტრიქონის შერჩევა, რომ H-ის მნიშვნელობები ერთმანეთს ბევრჯერ დაემთხვას განსხვავებულ სტრიქონებზე, პრაქტიკულად შეუძლებელია. ასევე გაითვალისწინეთ, რომ ამოცანის ტესტების კრებული წინასწარ მზადდება და ავტორი ვერ მოიგონებს ისეთ S–ს, რომელიც ნებისმიერი H ფუნქციისთვის ცუდ შედეგებს გამოიღებს. ამგვარად, მოყვანილი ალგორითმი მოსალოდნელ O(L) დროში მუშაობს.

დავამთავროთ იმით, თუ როგორი შეიძლება იყოს H(S) ფუნქციის სახე. ერთ–ერთი გავრცელებულია მისი შემდეგი მრავალწევრით ჩაწერა: H(s₁s₂...s_L) = ( A^(L-1)*|s₁| + A^(L-2)*|s₂| + ... + A^1*|s_L-1| + A^0*|s_L| ) mod M, სადაც s₁, s₂, ... არიან S სტრიქონის შესაბამისად პირველი, მეორე და ასე შემდეგ სიმბოლოები, ^ ახარისხების ოპერაციას ნიშნავს, ხოლო |s_i| არის s_i სიმბოლოს ASCII კოდი. M-ის როლში უმჯობესია დიდი მარტივი რიცხვი აიღოთ, მაგალითად 10^9+7.

ვთქვათ, ჩვენ ვცდილობთ s₁s₂₁...s_L სტრიქონზე ერთი სიმბოლოს მიმატებას, ანუ s₁s₂...s_Ls_L+1 სტრიქონის ჰეშს ვეძებთ. მაშინ H(s₁s₂...s_Ls_L+1) = ( A^L*|s₁| + A^(L-1)*|s₂| + ... + A^2*|s_L-1| + A^1*|s_L| + A^0*|s_L+1| ) mod M. დააკვირდით წინა ჰეშ–მნიშვნელობისგან განსხვავებას: მთელი მრავალწევრის ხარისხმა 1–ით აიწია და დაემატა ერთი ელემენტი. მართებულია შემდეგი ტოლობა: H(s₁s₂...s_L+1) = (H(s₁s₂...s_L)*A+|s_L+1|) mod M, რაც O(1) დროში შეგვიძლია გადავთვალოთ. იმის დადგენას, თუ როგორ ხდება ჰეშ–ფუნქციის O(1) დროში გადათვლა სტრიქონზე სიმბოლოს მარცხნიდან მიმატებისას და სხვა ოპერაციებისას, მკითხველს დამოუკიდებლად ვთავაზობ.

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

ჯერ განვიხილოთ, როგორ გამოვთვალოთ და საერთოდ რა არის მათემატიკური მოლოდინი იმ შემთხვევაში, თუ R ფიქსირებული რიცხვია. ამისთვის უნდა ამოვწეროთ თავსატეხების ყველა შესაძლო მიმდევრობა, რომლითაც გუნდს შეეძლო ევლო და თან გამოვთვალოთ ყოველი ასეთი მიმდევრობისთვის იმის ალბათობა, რომ გუნდი თავსატეხებს ზუსტად ასე შემოივლიდა. განვიხილოთ ამოცანის პირობაში მოყვანილი მეორე მაგალითი: 3 თავსატეხი გვაქვს წერტილებში (0,2), (2,0) და (3,0) და სამივე 100-ქულიანია. განვიხილოთ თავსატეხების შემოვლის მიმდევრობები R=2.9 შემთხვევაში:

1) კოორდინატთა სათავიდან ჩანს (0,2) და (2,0) წერტილები. დავუშვათ, გუნდი წავიდა (0,2)-ში, რისი ალბათობაც 1/2 არის. იქიდან იგი მხოლოდ (2,0) წერტილს დაინახავს და გადავა მასში, იქიდან კი (3,0)-ში. შედეგად გუნდი შემოივლის სამივე თავსატეხს და დააგროვებს 300 ქულას და ამ სცენარის ალბათობა 1/2-ის ტოლია.

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

გუნდის მიერ დაგროვებული ქულების მათემატიკური მოლოდინი არის ამ ყველა სცენარის ქულების წონითი საშუალო, ანუ სცენარებში აღებული ქულების მათ მოხდენის ალბათობაზე ნამრავლთა ჯამი. ამ მაგალითში ესაა 1/2 * 300 + 1/4 * 200 + 1/4 * 200 = 250. ამ რიცხვს შეგვიძლია ასეთი ინტერპრეტაცია გავუკეთოთ: გუნდის მიერ თავსატეხების შემოვლის შემთხვევითი პროცესი ძალიან ბევრჯერ რომ განმეორებულიყო, საშუალოდ ისინი 250 ქულას აიღებდნენ.

განვიხილოთ ამოცანის ამოხსნა R-ის ფიქსირებული მნიშვნელობისთვის. როგორც მაგალითიდან დავინახეთ, შეგვიძლია თავსატეხების შემოვლის ყველა შესაძლო მიმდევრობა განვიხილოთ, რომლის ბოლოს გუნდი მეტ ახალ თავსატეხს ვეღარ ხედავს. ეს მიდგომა რა თქმა უნდა სწორ პასუხს იძლევა, მაგრამ მოცემული შეზღუდვების პირობებში ზედმეტად ნელი შეიძლება აღმოჩნდეს. მაგალითად, თუ R საკმარისად დიდია, შეიძლება ნებისმიერი თავსატეხის წერტილიდან ნებისმიერი სხვა თავსატეხი ჩანდეს. ამ შემთხვევაში N! მიმდევრობა გვაქვს განსახილველი, რაც N=12-ისთვის ნახევარ მილიარდს უკაკუნებს. ამდენი მიმდევრობის განხილვა და მანდ ალბათობების დათვლა 2 წამზე ბევრად მეტ დროს წაიღებს.

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

განვიხილოთ მაგალითი. დავუშვათ, ალგორითმის მსვლელობის პროცესში დავინახეთ, რომ (2,6,3,1,4) მიმდევრობის შემოვლის შემდეგ შეგვეძლო რაღაც მე5 და მე7 თავსატეხებთან მისვლა, ხოლო მე5-დან ასევე მე8 და მე9 თავსატეხები ჩანდა. ვთქვათ, მე5 თავსატეხის ქულა იყო 10, მე7 - 20, მე8 - 4 და მე9 - 15. (2,6,3,1,4) მიმდევრობის შემოვლის შემდეგ ჩვენ რაღაც X ქულა გვქონდა, ხოლო გაგრძელების ვარიანტები გვაქვს:

1) 1/2 ალბათობით გადავალთ მე7 თავსატეხთან და დავამთავრებთ X+20 ქულით.
2) 1/2 ალბათობით გადავალთ მე5 თავსატეხთან, საიდანაც კიდევ 1/2 ალბათობით მოვხვდებით მე8 თავსატეხთან, შედეგად დავამთავრებთ X+14 ქულით. მთელი სცენარის ალბათობაა 1/2 * 1/2 = 1/4.
3) 1/2 ალბათობით გადავალთ მე5 თავსატეხთან, საიდანაც კიდევ 1/2 ალბათობით მოვხვდებით მე9 თავსატეხთან, შედეგად დავამთავრებთ X+25 ქულით. მთელი სცენარის ალბათობაა 1/2 * 1/2 = 1/4.

ამრიგად, (2,6,3,1,4) მიმდევრობის შემოვლის შემდეგ თუ გავაგრძელებთ სიარულს, საბოლოო ჯამში საშუალოდ X + (1/2 * 20 + 1/4 * 14 + 1/4 * 25) ქულა გვექნება. ამ ჯამის მეორე შესაკრები განიშიფრება როგორც "ასაღები ქულების მათ.მოლოდინი, თუ ვიწყებთ მე4 თავსატეხიდან და უკვე შემოვიარეთ {1,2,3,4,6} თავსატეხები". ზუსტად ეს მათ.მოლოდინი შეგვიძლია შევინახოთ. როდესაც განვიხილავთ (3,6,1,2,4) მიმდევრობას, დაგვჭირდება იგივე ინფორმაცია - {1,2,3,4,6} თავსატეხები შემოვლილი გვაქვს, მე4-სთან ვიმყოფებით და გვაინტერესებს, რამდენ ქულას დავიმატებთ საშუალოდ. ხოდა ნუღარ გამოვთვლით ხელმეორედ, გამოვიყენოთ წინა ჯერზე შენახული მნიშვნელობა.

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

რაც შეეხება იმპლემენტაციის დეტალებს, ასეთ ამოცანებში, სადაც მცირე ზომის სიმრავლეებთან გვაქვს საქმე, ხელსაყრელია ბიტმასკების გამოყენება. რეალურად ბიტმასკი რიცხვს წარმოადგენს, რომელზეც ბიტურ ოპერაციებს ჩავატარებთ. თითოეული ბიტი შეესაბამება ელემენტების სრული სიმრავლის ერთ კონკრეტულ ელემენტს. დავუშვათ, გვაქვს სიმრავლე 4 ელემენტით და გვჭირდება მისი ქვესიმრავლე, რომელშიც პირველი და მესამე ელემენტები შედის. განვიხილოთ 4ბიტიანი ორობითი რიცხვი, რომლის პირველი და მესამე ბიტი 1-ის ტოლია: 0101. ეს არის 5-ის ორობითი ჩანაწერი, ამიტომ შეგვიძლია ასეთი სიმრავლე ერთი რიცხვით 5 ჩავწეროთ. სრული 4ელემენტიანი სიმრავლე 15-ით, ხოლო ცარიელი სიმრავლე 0-ით ჩაიწერება. ბიტმასკების გამოყენება იმითაა მოსახერხებელი, რომ ისინი მაქსიმალურად ცოტა მეხსიერებას იკავებენ და მათზე ოპერაციები ძალიან სწრაფია. ბიტური ოპერაციების შესახებ კარგი რესურსი შეგიძლიათ აქ იხილოთ.

ჩვენ განვიხილეთ ფიქსირებული R-ისთვის ქვეამოცანის ამოხსნის მონახაზი, მაგრამ რეალურად R არის შემთხვევითი სიდიდე [0,M] შუალედიდან. ვინაიდან R უწყვეტი სიდიდეა, ფორმალურად დაგროვებული ქულების მათ.მოლოდინი იქნება განსაზღვრული ინტეგრალის მნიშვნელობა E(R)dR-იდან [0,M] შუალედზე, სადაც E(R) არის R ხედვის რადიუსისთვის დაგროვებული ქულების მათ.მოლოდინი, რომლის გამოთვლა ჩვენ უკვე ვისწავლეთ. შევნიშნოთ, რომ ორი R1 და R2 რადიუსისთვის E(R1) და E(R2) მარტო მაშინ შეიძლება განსხვავდებოდეს, თუ რომელიმე ორ თავსატეხს ან კოორდინატთა სათავეს და თავსატეხს შორის მანძილი არის R*, რომელიც მოთავსებულია R1 და R2-ს შორის. თუ ასეთი მანძილი არ მოიძებნა, მაშინ კოორდინატთა სათავიდან და ყველა თავსატეხიდან ერთიდაიგივე თავსატეხები ჩანს და შესაბამისად თავსატეხების შემოვლის სცენარებიც ზუსტად იგივეა. ამ დავკირვების შედეგად შეგვიძლია ინტეგრალი გამოვსახოთ შემდეგი ჯამით: (E(R1) * (R2-R1) + E(R2) * (R3-R2) + ... + E(RK) * (M-RK) ) / M, სადაც K წარმოადგენს იმ განსხვავებულ მანძილთა რაოდენობას, რომლებიც გვხვდება თავსატეხებს (ან კოორდინატთა სათავეს და თავსატეხებს) შორის და ნაკლებია M-ზე, R1, R2, ..., RK კი არის ეს მანძილები, დალაგებული ზრდის მიხედვით. ფორმულას შემდეგი შინაარსი აქვს: R1-დან R2-მდე რადიუსის შემთხვევაში ქულების მათემატიკური მოლოდინი E(R1)-ის ტოლია, ხოლო იმის ალბათობა, რომ რადიუსი იქნება R1-დან R2-მდე შუალედში, არის (R2-R1)/M. ანალოგიურად სხვა შესაკრებებისთვის.

გამოვიდა, რომ ჩვენ გვჭირდება კოორდინატთა სათავეს და თავსატეხებს შორის ყველა M-ზე მცირე მანძილი განვიხილოთ, დავალაგოთ ისინი ზრდადობის მიხედვით და ყოველი მათგანისთვის გამოვთვალოთ E-ს მნიშვნელობა, რომელიც O(2^N * N^2) დროში ითვლება. ვინაიდან განსხვავებული მანძილების რაოდენობა N^2-ის რიგისაა, მთელი ამოცანის ამოხსნის ალგორითმული სირთულეა O(2^N * N^4).

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