პირველის ამოხსნა ეგაა
მესამეში კი ის გავიწყდება რო ბოლო სტრიქონში მოცემულ წერტილში უნდა მიხვიდე. ანუ R*C*C*K გამოვა ეგ ამოხსნა რაც 55 ქულიანია. როგორც გავიგე სრული ამოხსნა R*C*K*log ია, ინტერვალთა ხეებით.

R*C*K კი აიღებს 100 ქულას (20 წამი ქონდა დროის ლიმიტი). როგორ ხსნი მაგ დროში?

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

ყოჩაღ, ძალიან კარგი შედეგია. წინა წლებთან შედარებით დიდი პროგრესია.

ტოპკოდერზე:

http://community.topcoder.com/tc?module=ProblemArchive&sr=&er=&sc=&sd=&class=&cat=Dynamic+Programming&div1l=&div2l=&mind1s=&mind2s=&maxd1s=&maxd2s=&wr=

ეს ბოლო ლინკი დაიჰაკა :|

ამოცანებს რა აზრი აქ, ყოველი მესამე ამოცანა ამაზეა.

მე მგონი საკმარისი რაოდენობის ლინკებია. მერე ვინმემ რო არ თქვას რო ეგ რა არის არ უსწავლებიათ ჩემთვისო :)

ხოდა მაგდენი ლინკი იმიტომაა რომ შენ თვითონ მიხვდე რომელი გინდა და იმას წაიკითხავ.

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

Topcoder Feature Articels - Dynamic Programming

ვნახოთ ვინ უფრო მეტ საიტს დადებს სადაც გარჩეული დინამიური პროგრამირების მეთოდი (ნებისმიერი რამე)

დავიწყოთ:

1. Dynamic Programming [Algorithmics@NUS]
http://algorithmics.comp.nus.edu.sg/wiki/_media/notes/dynamic_programming.doc?id=notes%3Adynamic_programming&cache=cache

2. informatics.mccme.ru - Динамическое программирование

3. e-maxx.ru - Динамика по профилю
e-maxx.ru - Нахождение наибольшей нулевой подматрицы

4. en.wikipedia.org - Dynamic programming
ru.wikipedia.org - Динамическое программирование

5. mat.gsia.cmu.edu - A Tutorial on Dynamic Programming

6. www.codechef.com - Tutorial for Dynamic Programming

7. www.avatar.se - Dynamic Programming

რას ქვია არაა ძალიან ცუდი შედეგი? შემდეგი წლის შედეგი წლევანდელს ვეღარ შეცვლის.

მილოცვას ვუერთდები.

ყველაზე ცუდი შედეგი გვაქვს მთელი ისტორიის მანძილზე. მეტის თქმა საჭირო არაა.

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

ჩვენი ნაკრები

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

როგორ მოხდა რომ შეკითხვა არავინ დასვა თუ ასეთი ხარვეზი იყო პირობაში?

G-ში რა ტესტები ამოშალეთ?

@jskhirtladze

ორნაირად შეიძლება ეგეთი ამოცანების ამოხსნა.

1) ყველა შესაძლო რიცხვის განსახილველად გადაარჩიე R ის პირველი k ციფრების რაოდენობა, გადაარჩიე რას უდრის შემდეგი ციფრი და დანარჩენი ციფრები უკვე შეიძლება ნებისმიერი იყოს და მათთვის გქონდეს დათვლილი დინამიურად წინასწარ.

2) დინამიურშივე მიუთითო პირველი რამდენიმე ციფრი რო გაქ აღებული, ემთხვევა ისინი R-ის პირველ ციფრებს თუ არა. თუ ემთხვევა, შემდეგ ციფრზე შეზღუდვა გექნება, თუ არადა ნებისმიერს აიღებ.

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

არ არის ეგ N*sqrt(N), N^log2(3) ია.

ბარემ ლინკსაც დავდებ და მერე შეჯიბრებაზე რო მოვა სადმე არ თქვან არ ვიცოდითო :)

კარაცუბა

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

მინიშნება: N აიღეთ 2 ის ხარისხი. თუ ზუსტი ხარისხი არაა, რიცხვებს წინ 0 ებს დაუმატებთ რომ შეავსოთ 2 ის ხარისხამდე.

მადლობა

ამოცანები არ ვარგოდა რაღაც თორემ მეტი გავიდოდნენ ჩვენგან ალბათ.

20 წუთში იწყება მეორე რაუნდი

წარმატებები ყველას!

პირველი დღის A ამოცანაზე იდეები:

ალბათ იმას მიხვდით რომ [L,R] ზე ამოხსნისთვის საკმარისია [0,R] ზე ხსნიდეთ.

მოვყვეთ ერთი ბოლოდან და ვთქვათ რიცხვის რაღაც ნაწილი ავაგეთ. თითოეული ციფრისთვის 3 ნაირი მდგომარეობა შეიძლება გვქოდნეს: არ შეგვხვედრია, შეგვხვდა ლუწჯერ, შეგვხვდა კენტჯერ. ანუ 3^10 მდგომარეობაა იდეაში. დალშე თქვენც მოიფიქრებთ იმედია დინამიურ ამოხსნას.

ვაა ქუთაისის ჩემპიონატი დაიდო ? :)

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

შედეგები გამოაჩინე თუ შეგიძლია, მაინტერესებს ერთი ვინ რას ხსნის