რაც შეეხება მასივებს და ვექტორებს, მუშაობის დროში განსხვავება მინიმალური აქვთ, თუ vector-ს სწორად გამოიყენებთ. მაგალითად, თუ ამოცანაში მოცემულია N ცალი რიცხვი და გინდათ ისინი ვექტორში შეინახოთ, ბევრად უკეთესია, თავიდანვე N ზომის ვექტორი შექმნათ და არა ცარიელით დაიწყოთ და push_back მეთოდის მეშვეობით ამატოთ მასში ელემენტები. ამ მეორე შემთხვევაში მასივის შევსებაზე დაახლოებით ორჯერ მეტი დრო გახდება საჭირო და ასევე მას უარეს შემთხვევაში ორჯერ მეტი მეხსიერებაც დასჭირდება.

ვისაც აინტერესებს, ეს რისი ბრალია, უნდა იცოდეთ რისი მეშვეობით ახერხებს vector ამორტიზებულ O(1) დროში (მარტივად რომ ვთქვათ, "სწრაფად") ელემენტის დამატებას. და რომ გესმოდეთ, რატომ არაა ეგ მარტივი, უნდა იცოდეთ როგორ ხდება მეხსიერებაში მასივის შენახვა.

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

მაშინ როგორ მუშაობს vector? იგი ელემენტებს მასივით ინახავს სწრაფი წვდომისთვის, მაგრამ გარკვეულ შემთხვევებში ამ მასივს შლის და ქმნის ახალს, რომლის სიგრძე ორჯერ მეტია წინაზე. მაგალითად, თუ vector-ის მასივის სიგრძე 2-ის ტოლია და მასში მხოლოდ 1 ელემენტია მიმდინარე მომენტში, მაშინ ელემენტის ჩამატებისას იგი თავისუფალ ადგილს დაიკავებს. აი კიდევ ერთი ელემენტის ჩამატებას რომ მოვინდომებთ, vector ავტომატურად შექმნის 4-ელემენტიან მასივს, გადაიტანს მასში თავის ძველ 2 ელემენტს, დაუმატებს ახალს და ძველ 2-ელემენტიან მასივს გაანადგურებს. როდესაც vector-ში ელემენტების რაოდენობა 4-ს მიაღწევს, იგი ანალოგიური გზით 8 სიგრძის მასივს შექმნის და ძველს წაშლის. ერთი შეხედვით, ეს არც ისე სწრაფია, მაგრამ დააკვირდით, რომ თუ vector-ში ჩავამატეთ N ელემენტი, მისი სიგრძე აუცილებლად 2N-ზე ნაკლებია, ხოლო ოპერაციების რაოდენობა, რომელიც ჯამში შესრულდა N ელემენტის დასამატებლად, ასევე 2N-ის პროპორციულია (1+2+4+...+2^i ხომ (2^(i+1)-1)-ის ტოლია).

ამრიგად, როგორც GeOlymp-ის ამოცანებში, ასევე სხვა შეჯიბრებზე vector-ების მასივებად გადაკეთება მნიშვნელოვნად არ ასწრაფებს ამოხსნას, თუ ვექტორის კარგად გამოყენება იცით.

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

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

ამოხსნის დაწერისას აუცილებლად უნდა ითვალისწინებდეთ ოპერაციების "სიმძიმეს". მაგალითად, შეკრება და გამოკლება იაფი ოპერაციებია და სერვერზე შეიძლება 500-600 მილიონი შეკრება ერთ წამში ხორციელდებოდეს. შედარებით უფრო მძიმეა გამრავლების ოპერაცია. ყველაზე ცუდადაა საქმე გაყოფასთან და ნაშთის აღებასთან. ეს ოპერაციები 40-50 მილიონი ესწრება 1 წამში. მაგალითად, თუ თქვენს პროგრამას რამდენიმე მილიონჯერ სჭირდება p1/q1 და p2/q2 წილადების შედარება, აზრი აქვს რომ ამის ნაცვლად მოახდინოთ p1*q2 და p2*q1 სიდიდეების შედარება (ამას არა მხოლოდ სწრაფქმედებისთვის აქვს აზრი, მაგრამ ეს უკვე სხვა საკითხია).

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

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

მე-4-ში კი განისაზღვრება, მაგრამ მაგას მხოლოდ მაჭავარიანი მიხვდა (ყოველ შემთხვევაში მხოლოდ მაგან გამოიყენა).

მე-5-ში 2 ამოხსნა იყო პრეპროცესინგში ფესვიდან ყოველ წვერომდე რასების რაოდენობის დათვლა და შემდეგ O(logN + K) დროში პასუხი ყოველ შეკითხვაზე, 1 კი პრეპროცესინგის დროს იმახსოვრებდა წვეროდან მის 2^i მშობლებამდე შეხვედრილი რასების ბიტმასკს და შეკითხვებს logN * K/32 დროში პასუხობდა.

უცნაური იმ ამოხსნაში მხოლოდ იმის დადგენაა, მასივის ნაწილი წარმოადგენს თუ არა გადანაცვლებას. ძირითადი იდეა ყველგან დინამიური პროგრამირებაა.

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

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

საქართველოდან მონაწილეთა სია: http://www.go-hero.net/jam/12/regions/Georgia

4 მონაწილის სახელი არ მეცნობა, მაგრამ დანარჩენი 23 ნამდვილად საქართველოდან ვართ :) გილოცავთ.

არაა საჭირო 18 წლის იყო :) ვისაც 18 არ შესრულებია, მონაწილეობა შეუძლია, უბრალოდ ფინალში ვერ მოხვდება.

პროგრამა რაიმე მომენტში თუ გამოიყენებს გამოყოფილ მეხსიერებაზე მეტს, Memory Limit Exceeded ვერდიქტი დაიწერება. მესამე ეპიზოდთან რა კავშირშია ეგ შეკითხვა?

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

სრმ 540-ზე თუ გაინტერესებს რამე, გახსენი შესაბამისი თემა და იქ იკითხე. თვითონ Topcoder თავის გარჩევას რამდენიმე დღეში გამოაქვეყნებს.

ამიანად ცხადი O(კუბური ფესვი N-იდან) სირთულის ალგორითმი გამოდის და ამის გარეშე რატომ უნდა ემუშავა :)

ჰეშების გამოთვლისას რა მნიშვნელობა აქვს k-ზე ციკლებს 0-დან n-მდე უშვებ თუ პირიქით, თუ მაინც ერთსადაიმავე (1<<k)-ს იყენებ მერე?

ტესტირება უნდა ისწავლოთ კოდების.

რამე მიახლოებულს აკეთებ აქ აღწერილ ორ მიდგომასთან?

უაზრო ჩატი წაიშლება ხოლმე.

@nikasvanidze - ხომ წერია, არ შეგვიძლია-თქო ელექტრონული სახით მოგაწოდოთ.

@aazizian - ჩავრთავთ.

ხოდა 24 საათით ადრე უნდა ყოფილიყავი მაშინ. ახლა თუ ხარ, შაბათს არ შეგექმნება პრობლემა.

არ შეიძლება, დაელოდეთ NAEC-ის მიერ გამოქვეყნებას.

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

სავარაუდოდ, s-ში არა თუ ხარისხების მაჩვენებლების შეკრება უნდოდა, არამედ n-ის ყოველი მარტივი p გამყოფისთვის თუ მისი ხარისხი იყო k, s-ს ამრავლებს p^(k/2)-ზე და ბოლოსაც თუ შემორჩენილი რიცხვი სრული კვადრატია, მის ფესვზე ამრავლებს s-ს.

ყველაზე რთული ამოცანა იყო ეგ მე-8 კლასის კრებულში და 5 საათისთვისაც გერთულება? :)

"რა უნდათი" იწყებ და ბოლოს თვითონვე უთითებ შენი ამოხსნის პრობლემაზე. 20 წამი ხო არ ექნება.