@gojira

პროგრესიის სიგრძე ასეთი პატარა თუ იყო არ ვიცოდი :)

E ამოცანაში WA 19 მაქვს და ჰო ვერ დამეხმარებით?

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

ჯერ ბმულ კომპონენტებს ვაერთიანებდი ერთ კომკონენტში და მერე დფს-ით პასუხს მე-N ტურისთვის.
კოდი

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

რაც შეეხება მეორე ნახევარს, "დფსით პასუხი" ბევრი რამე შეიძლება იყოს. კოდიდან ვხედავ, რომ ყოველ წვეროში DFS-ით მისვლისთანავე ითვლი მაგის პასუხს და ამბობ ის საბოლოოა. განიხილე ასეთი მარტივი გრაფი:
N -> X
N -> Y
Y -> Z
X -> 1
Z -> 1
ანუ N-იდან 1-მდე ორი თანაუკვეთი გზაა, რომელთაგან ერთი უფრო გრძელია წიბოების რაოდენობით. ამ მეორე გზაზე ქულების ჯამიც მეტი იყოს. შენი დფს 1-ში X-იდან მოსვლისას დაუწერს ქულას და მეორედ აღარ შევა, ცხადია პასუხს ააცილებს.

E ამოცანაში მეც TLE 19 მაქვს, 2 DFS+Dijkstra და რამე სხვანაირად უნდა დავწერო თუ ჯავას ბრალია და უფრო მეტი ოპტიმიცაზია უნდა?

@Khatia

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

@aazizian

შემთხვევით შენ გურამ ქოთოლაშვილი ხომ არ გასწავლის?

@tsotne
კი და რა არის ?

@aazizian

არაფერი, უბრალოდ სიტყვა "დინამიკას" მე ვისაც ვიცნობ იმათ შორის მხოლოდ ის ხმარობს და დამაინტერესა :)

@tsotne
:D

@aazizian
მადლობა გავიდა, არადა მეგონა დეიქსტრაც ჩაეტეოდა დროში

@tornike
X-ში რას ინახავ?

@ცოტნე, აუ არ მეგონა პირდაპირი გზა თუ გაამართლებდა :ს.

@gojira, ც ამოცანაში საოცარია და ტესტები არ იყო ყოვლისმომცველი... გავატარე, მაგრამ ლ=1 რ=5001, რომ ვცადე ჩემთან ჯერ კიდევ მუშაობს :დ, წამი კიარა საათია ველოდები :დ.

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

L=1 R=5001 არის მე-8 ტესტი და შენი ამოხსნა 0.6 წამს მუშაობს მაგ ტესტზე სერვერზე. ლოკალურად თუ Visual Studio-ში ტესტავ, Debug პლატფორმა გექნება არჩეული და Release-ში დატესტე, იგრძნობ განსხვავებას.

ზუსტად 10 რომ არის, არაა ანალიზურად გამოყვანადი, მაგრამ მცირე რომ იქნება, მაგაზე მარტივი რიცხვების განაწილება მიანიშნებს. რომც არ მიგანიშნოს, რეალურად ხომ მარტივი რიცხვით უნდა დაიწყოს პროგრესია, მისი შემდეგი წევრიც მარტივი უნდა იყოს და სულ მარტივებზე უნდა გაიაროს. 5000 რიცხვში მაქსიმუმ ~250 მარტივია, ამიტომ ყველა მარტივიც რომ მოიცვას პროგრესიამ, O(M^3) ალგორითმი გამოვიდოდა, სადაც M~250.

@gojira, 1..5000-მდე ზუსტად 669 მარტივი რიცხვია :)

მდა, ვიღაცამ 250 მითხრა და ასე დამამახსოვრდა. შინაარსი არ იცვლება, 669^3 მარტივი ოპერაციაც ეტევა 1 წამში.

ჰო, 200 მილიონია დაახლოებით :)

მესამე ამოცანის მეხუთე ტესტი რა არი ამნაირი შეგიძლიათ მაჩვენოთ? :D
დამტანჯა რამდენიხანია უკვე ვებრძოლები და ვერ დავამარცხე :(

13-29 რამდენი გამოაქ ნახე
სწორი პასუხია 3 ჩემი შედგენილი ტესტია და თუ რამე პრეტენზიებით არ მომმართოთ :დ