მოკლედ ახლა კვირას იყო opencup-ის მე–2 დივიზიონში K ამოცანა გრაფის ტრანზიტულ ჩაკეტვაში წიბოების რაოდენობის გაგებაზე. რამდენიმენაირად ვცადე ამოხსნა მაგრამ TLE–ს აგდებს ყველაზე.მოცემულია აციკლური ორიენტირებული გრაფი. 1<=N<=50 000 წვეროების რაოდენობა, 0<=K<=50 000 წიბოების რაოდენობა. ყველაზე მეტი ტესტი რომ გაიარა იმ ალგორითმს გეტყვით როგორ ვაკეთებდი. ყველა წვეროდან ცალ–ცალკე ვუშვებ DFS და რამდენ წვეროს აღმოაჩენს ვითვლი ყველას. დრო 1 წამია და მეხსიერება 512 MB. იქნებ დამეხმაროთ ალგორითმის გაუმჯობესებაში ან რამე სხვა ალგორითმი მითხარით რომ დროში გავიდეს :)))

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

http://opencup64.cs.istu.ru/~ejudge/files/opencup/oc13/gp2/noanime-e.pdf
K ამოცანა, მასე წერია ზუსტად :)) ინგლისურად - transitive closure,
რუსულად - транзитивное замыкание.

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

გაიხარე მადლობა :)) მასე ვცდილობდი, მაგრამ რაღაც შემთხვევას თავი ვეღარ გავართვი... ახლა რაღაც იდეა დამებადა ვცდი და თუ რამეა კიდე მოგმართავ თუ არ შეწუხდები :D

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

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

@gojira - მოკლედ ვერ დაგვიწერ სწორ ამოხსნას ?

ამოხსნა საკმაოდ სულელურია. მოდი ყოველი 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 და დროში ეტევა.

კარგი ამოხსნაა :)

მსგავსი ამოცანის მოტანას ვაპირებდი ადრე ჯეოლიმპზე და აი კი დამასწრეს იმათ :D