როგორ მოვიპოვე გამოთვლითი ოლიმპიადაზე 3 ოქროს მედალიდან 4

ვემზადებოდი Google HashCode მსოფლიო ჩემპიონატის ფინალისთვის 2017. ეს არის Google-ის მიერ ორგანიზებული ყველაზე დიდი შეჯიბრი ალგორითმული პრობლემებით.

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

ორდღიანი შეჯიბრის შემდეგ შედეგები მოვიდა: ოქროს მედალი მოვიგე.

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

ვიცი, რამ მიმიყვანა წარმატებამდე და მინდა გაგიზიაროთ.

სტატია ითარგმნა EDISON Software-ის მხარდაჭერით, რომელიც ზრუნავს პროგრამისტების ჯანმრთელობაზე და მათ საუზმეზედა ავითარებს საბაჟო პროგრამულ უზრუნველყოფას.

რომელი პროგრამირების ენა აირჩიოს

• C++ - ძალიან გირჩევთ! ის ძალიან სწრაფია. ალგორითმების დანერგვას ცოტა დრო სჭირდება STL-ის გამო. C++ მიიღება ყველა კონკურსში. მე დავწერე ჩემი პირველი ხაზი კოდი C++-ში.
• C - ისწავლეთ C++ STL-ის გამო. თუ იცით C, შეგიძლიათ დაპროგრამოთ C++-ზეც.
• Java არის ნელი პროგრამირების ენა. მას აქვს Big Integer კლასი, მაგრამ ეს დიდად არ გამოგადგებათ. თუ კონკურსს აქვს დროის ლიმიტი, ჯავის საშუალებით თქვენ მას აუცილებლად გადააჭარბებთ. ჯავა არ მიიღება ყველა კონკურსზე.

სად შეიძლება ვარჯიში

ვურჩევ Sphere Online Judge (SPOJ). ეს არის ეფექტური რესურსი რაოდენობის და ხარისხის თვალსაზრისით. რედაქტორები და გადაწყვეტილებები ხელმისაწვდომია ონლაინ რეჟიმში, თუ პრობლემების გადაჭრის პროცესში გაჩერდებით. ამ საიტის გარდა გირჩევთ SPOJ ინსტრუმენტარიუმის и პრობლემის კლასიფიკატორი SPOJ.pl-ისთვის.

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

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

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

როდესაც მას ეძებთ, გახსოვდეთ ორი ძირითადი პრინციპი:

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

აი ჩემი მაგალითი პროგრამირების სტილი.

როგორ გააუმჯობესოთ თქვენი განვითარების უნარები

ივარჯიშე, ივარჯიშე და მეტი ვარჯიში. გირჩევთ, პირველ 250 პრობლემის გადაჭრაზე გადახედოთ SPOJ. გადაჭრით ისინი თანმიმდევრობით. მინიმუმ ერთი საათი დაუთმეთ ფიქრს თითოეული მათგანის გადაწყვეტაზე.

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

აიღეთ ფურცელი და ფანქარი. Იფიქრე ამაზე. იქნებ გამოსავალი იპოვო, შეიძლება არა. მინიმუმ ალგორითმული აზროვნება განივითარებთ. თუ ერთ საათში გამოსავალს ვერ იპოვით, მოძებნეთ მზა გამოსავალი ფორუმზე ან სტატიებში.

რას მიაღწევთ ამ მიდგომით? ისწავლეთ თქვენი იდეების სწრაფად განხორციელება კოდის გამოყენებით. და შეისწავლეთ კლასიკური პრობლემები და ალგორითმები.

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

დაიცავით იერარქიული მიდგომა. დაიწყეთ სირბილი ისე, რომ სიარული არ იცოდით? არა. შეგიძლიათ ცათამბჯენის აშენება მყარი საძირკვლის გარეშე? Აღარ.

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

დაიწყეთ ფუნდამენტური ალგორითმებით და მონაცემთა სტრუქტურებით

ძნელია დაწყება. ალბათ იმიტომ, რომ ჯერ არ იცი რა ისწავლო. Ამიტომაც შევქმენი ვიდეო კურსი "ალგორითმები და მონაცემთა სტრუქტურები". ამ კურსის შექმნისას მე მას ვაფუძნებდი იმაზე, თუ როგორ მინდა მასწავლონ. რეაქცია წარმოუდგენელი იყო! პირველ თვეში კურსზე დარეგისტრირდა 3000-ზე მეტი სტუდენტი 100-ზე მეტი ქვეყნიდან.

თუ იოლი პრობლემების გადაჭრაზე მუშაობ, ვერასოდეს გაუმჯობესდები.

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

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

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

ჩაუღრმავდით თითოეულ მთავარ თემას

აქ არის ღირებული რესურსი ბევრი ინფორმაციით. აქ ნახავთ ტოპ 10 ალგორითმს და მონაცემთა სტრუქტურას თითოეული თემისთვის. SPOJ-ის 250 პრობლემის შემდეგ, ამ სიიდან ბევრს გაიგებთ. მაგრამ თქვენ ასევე წააწყდებით ბევრ რამეს, რაც აქამდე არასოდეს გსმენიათ. ამიტომ დაიწყეთ ამ თემების შესწავლა ზრდადი თანმიმდევრობით.

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

დაეუფლეთ დინამიურ პროგრამირებას, რადგან ის მიგიყვანთ გამარჯვებამდე
ჩემი გამოცდილებიდან გამომდინარე, ყველა კონკურსს ერთი პრობლემა მაინც აქვს დინამიური პროგრამირება. ბევრ ადამიანს უჩნდება თავის ტკივილი, როდესაც ისმენს ფრაზას „დინამიური პროგრამირება“, რადგან მათ ეს საერთოდ არ ესმით.

და ეს კარგია. რადგან თუ გესმით დინამიური პროგრამირება, მაშინ გაიმარჯვებთ.

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

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

იმუშავე

გსმენიათ ოდესმე სპორტსმენების შესახებ, რომლებიც ოლიმპიურ თამაშებს წლების განმავლობაში ვარჯიშის გარეშე იგებენ? Მე არ.

ყოველწლიურად კომპიუტერული ოლიმპიადისთვის მზადება სექტემბერში იწყებოდა და აპრილში სრულდებოდა.

ამ 8 თვის განმავლობაში ყოველდღე ვვარჯიშობდი 5 საათის განმავლობაში.

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

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

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

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

თავად სცადე. ეს მაგიას ჰგავს.

შევქმენი ვიდეო ბლოგი

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

იმუშავე ჭკვიანურად

ეს არის წარმატების საიდუმლო. გჭირდება მიზნები.

ხალხი ვართ და მოგვწონს გადადება. ჩვენ ყოველთვის გვინდა გადავდოთ ის, რაც ახლა უნდა გაკეთდეს. Netflix-ის ყურება ყოველთვის უფრო სასიამოვნოა, ვიდრე დინამიური პროგრამირების პრობლემების მოგვარება. თქვენ ეს იცით და უნდა გამოასწოროთ.

როგორ დავამარცხოთ გაჭიანურება

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

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

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

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

როგორ მოვახდინოთ ეფექტურად გამართვა

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

შეგიძლიათ შეადაროთ თავი დიდოსტატს, რომელიც თამაშობს ჭადრაკს და ფიქრობს 3 ნაბიჯით წინ.

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

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

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

შესახებ ავტორი

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

თარგმანი: დიანა შერემიევა

წყარო: www.habr.com