ამოხსნა საკმაოდ სულელურია. მოდი ყოველი i წვეროსთვის შევინახოთ სტრიქონი, სადაც j-ურ პოზიციაზე წერია '1' თუ i-დან მიიღწევა j და '0' წინააღმდეგ შემთხვევაში. თავიდან არაფერი არ ვიცით და ამ მატრიცის დიაგონალზე წერია 1-ები. ახლა გავუშვათ სიღრმეში ძებნა რაიმე v წვეროდან. მისი ყოველი u შვილისთვის რომ დაამთავრებს მუშაობას dfs, ავიღოთ და u-ს სტრიქონში სადაც 1 ეწერა ყველა ამოვიტანოთ v-ს სტრიქონშიც. ასევე დაგვჭირდება დამახსოვრება, რომელი წვეროები დავამუშავეთ, რომ მაგის მეორე მცდელობა არ მოვახდინოთ. როდესაც dfs-ს ყოველი წვეროსთვის გავუშვებთ, იმ სტრიქონებში გვექნება ინფორმაცია, რომელი წვეროდან რა წვეროები მიიღწევა. ეგ ამოხსნა არის O(N^2) მეხსიერების და O(NM) დროის მჭამელი. ერთადერთი ოპტიმიზაცია: სტრიქონების ნაცვლად შევინახოთ ბიტმასკების მასივები. აშკარად მასივში საჭიროა სულ ceil(N/32) ელემენტი და ამიტომ მეხსიერება N^2/32 გახდა. ასევე v-ს სტრიქონში u-ს სტრიქონიდან 1-ანების ამოტანა ბიტური OR ოპერაციით შეიძლება ჩავწეროთ და ამიტომ გვჭირდება გადავყვეთ იმ მასივს და ბიტური OR-ები ჩავატაროთ. სირთულე არ შეიცვალა, მაგრამ რეალურად ესაა NM/32 და დროში ეტევა.

შეზღუდვებით არაა აკრძალული და :) თუმცა დიდად ლოგიკური არც მე მეჩვენება ამ შემთხვევაში.

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

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

@Quick - არაა სწორი შენი ალგორითმი, რამდენიმეჯერ ითვლი კონკრეტული წვეროსგან მიღწევადებს. მაგალითად:
1->2
1->3
2->3

წვერო 3 წვერო 1-ისთვის ორჯერ დაითვლება როგორც შთამომავალი.

ისე შენი შედარებით ძველი გაგზავნები ვნახე ახლა, რაც მე-18 და მე-17 ტესტზე იჭრებოდა. მე-18 იყო ზუსტად მეხსიერების გადავსება (ოღონდაც ჯავა ამ დროს ისვრის out of heap space exception-ს). და იმ File-ის FileWriter-ად ჩანაცვლებამ თითქმის ორჯერ შეანელა კოდი. ეჭვი მაქვს, რომ როცა FileWriter ობიექტს აძლევ კონსტრუქტორს, PrintWriter ავტომატურად flush-ს აკეთებს ყოველი print-ის მერე და ამიტომ ნელდება ასე ძალიან.

Time limit exceeded რა ტესტზეც მიიღო, იქ N=3000 და ინფორმაციის სკანერით წაკითხვას, 3000x3000 მატრიცის შექმნას, ალგორითმის ამუშავებას და ინფორმაციის გამოტანას კი შეიძლება 1 წამი წაეღო. მეხუთე ტესტზე არ ბეჭდავ იმდენ ნომერს რამდენიც საჭიროა, არ აკეთებს ეტყობა იგივეს :)

Topcoder-ზე ქვეყნის რეიტინგის 75% განისაზღვრება საუკეთესო 10 მონაწილის რეიტინგით, ამიტომ დაბალრეიტინგიანი მომხმარებლები მასზე გავლენას თითქმის არ ახდენენ. ზუსტი ფორმულაა აქაა: http://community.topcoder.com/tc?module=Static&d1=statistics&d2=info&d3=topCountries

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

@qasrava, @Elle
დოკუმენტაციაში აღწერილი ეგეთი რაღაცეები. კერძოდ, ტანკი ითიშება თუ მისი crewHealth (ჯანმრთელობა) ან hullDurability (ჯავშანი) 0-მდე ჩადის.

@giunagio5
ჰმ მართალი ხარ, K=2 უნდოდა მანდ. (2^0+1) ხოა 2-ის ტოლი...
N=1 L=1 R=2 index=1 - პასუხი 1-ია
N=1 L=1 R=2 index=3 - პასუხი 2-ია
შენ ხომ 3 რიცხვისგან შემდგარი მიმდევრობა გაქვს და მარცხენა კიდეში რიცხვი 1 წერია, მარჯვენაში რიცხვი 2.

@Dixtosa
შენ არც ძველად გამოირჩეოდი გასაგები ტექსტებით. ამჯერად რა გინდა?

@giunagio5
K ყოველთვის (2^i+1) სახის რიცხვია და ამიტომ K=2 შეუძლებელია.

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

@gpataraia
ანალოგიურ ამოხსნაზე ეჭვი გამოითქვა, რომ პრობლემა ამ ხაზშია:
pair<ll,ll> c(a.first*b.second + a.second*b.first,a.second*b.second*2);
second-ები 2^N-მდე შეიძლება იყოს, ხოლო first 10^9 * 2^N-მდე. იდეაში შუალედურმა შეკვეცებმა უნდა გადაგარჩინონ, მაგრამ როგორც ჩანს ყოველთვის არ მუშაობენ. შეეცადე წილადების ასე ცხადი სახით შენახვის ნაცვლად სხვანაირად დაითვალო რაღაცეები, რომ გარანტირებულად ჩაეტიო long long-ში.

@Dixtosa
მგონი ინტერნეტ-რაუნდის შედეგებს უყურებ და არა დასწრებული ფინალის.

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

@giorgi123
სისტემა არ არგვალებს გამოყოფილ მეხსიერებას, უბრალოდ С++-ის კომპილატორი არ ახდენს მეხსიერებაზე წვდომის კონტროლს და მასივს რომ გადასცდები, მარტო იმ შემთხვევაში ისვრის run time error-ს, თუ სხვის რესურსებს შეუტიე. ხშირად კი იგი უბრალოდ მეხსიერების შესაბამისი ადგილიდან რაღაც "ნაგავ" მნიშვნელობას იღებს.

რატოა კაცო წაშლილი, 1106 არის მაგ წლის ფინალის კონტესტი.

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

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

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

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

@aazizyan
D-ში კიდევ ცხადია, რომ ყველა გადანაცვლების განხილვა და შემოწმება, რამდენ K-ზე გაიყო, ზედმეტად ნელია. თუმცა შეგვიძლია ჯერ შევამოწმოთ, შეიძლება თუ არა მოცემული ციფრებით მივიღოთ 2, 3, 4 და 5-ზე გაყოფადი რიცხვი. დადებით შემთხვევაში ჩვენი რიცხვის ბოლო ციფრი ცალსახად 0 უნდა იყოს, ხოლო ბოლოსწინა 0, 2, 4, 6 ან 8. მეორე დებულებით ერთი შეხედვით ბევრი ვერაფერი მოვიგეთ - ხომ შეიძლება ყველა ციფრი {0,2,4,6,8} სიმრავლიდან იყოს - მაგრამ რეალურად ამ დროს ვარიანტების რაოდენობა 11!-თან ახლოსაც კი არ დგას, იმიტომ რომ ციფრები მრავლად მეორდება.

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

ეს იყო საავტორო ამოხსნა და ისე meet-in-the-middle-ის მეშვეობითაც იხსნება. აიღე 12-დან ციფრების ყველა 6-ეული, მათი ყოველი გადანაცვლებისთვის ნახე რა ნაშთები მიიღება lcm(1, ..., i) რიცხვზე გაყოფისას ყოველი i = 1..40-სთვის (40-ზე ნაკლებია იქ ზღვარი, 36 ალბათ) და შემდეგ მარცხენა მხარეს რომ დააფიქსირებ რა 6 ციფრი უნდა გქონდეს, მარჯვნივ შეძლებ სწრაფად შეამოწმო რა საუკეთესო ექვსეული ეტევა. თუმცა ზედმეტად რთულია ეგ ამოხსნა D-სთვის.

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

დეკარტის ხე სულ არაა აქ საჭირო, უბრალოდ DFS-ით შემოვიაროთ ხე და ყოველმა წვერომ დააბრუნოს, მისგან ქვემოთ (ანუ მის ქვეხეში) წასული ყველაზე გრძელი გზა რამხელა იყო და რამდენი იყო ასეთი სიგრძის გზა. ახლა ვთქვათ X წვეროს ჰყავდა N შვილი და მათ დააბრუნეს წყვილები (Ai, Bi) - A არის რა სიგრძის გზა იყო i-ური წვეროდან ქვემოთ და B რამდენი იყო ასეთი. ცხადია, რომ X წვეროდან ქვემოთ წასული უგრძესი გზა იქნება ის, რომლისთვისაც Ai+[წიბოს სიგრძე X-დან i-მდე] არის მაქსიმალური, ხოლო მათი რაოდენობაა ყველა იმ Bi-ს ჯამი, რომლებისთვისაც Ai+[X->i წიბოს სიგრძე] ტოლია მაქსიმალურის. ამავე დროს უნდა გამოვთვალოთ, X-ის ქვეხეში უგრძესი გზა რა იყო - ანუ იგი შეიძლება დაიწყოს X-ის ერთ-ერთი შვილის ქვეხეში, გაიაროს X-ზე და წავიდეს მეორე შვილის ქვეხეში. ესე იგი უნდა ვიპოვოთ L = მაქსიმუმი(Ai+Aj+[წიბო X->i]+[წიბო X->j]) და დავითვალოთ ეს მაქსიმუმი რამდენჯერ შეგვხვდა. თუ L აღემატება მიმდინარე უგრძეს გზას, ესე იგი უკეთესი პასუხი გვიპოვნია.

ნოდარ, ისე ხსნი ხოლმე რო ასი წელი ვერ გავიგებდი ამოხსნას :D

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