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

ვექტორი რომ მოვაშორე 14ტლე-ზე ავიდა.


ჰეშირებაც გავაკეთე. მაინც 14ტლე.

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








ხოდა :დ. რავიცი . ანბანი დიდი რომაა ბოიერი ხომ არ ვიხმარო?

მარა რა ვერ გავიგე კმპ ხო წრფივია M+N (უფრო ზუსტად მაქსიმუმ 2*N შედარება როგორც ვიცი). ხოდა აქ N,M მაქსიმუმ შეიძლება იყვნენ 3*10^5 და 3*10^5. ხოდა მილიონ მარტივ შედარებას რატო ვერ ასწრებს ორ წამში?

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

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

იქნებ ვინმემ 2010 წლის ფინალის G და 2011 წლის ფინალის E ამოცანის გარჩევები მოკლედ დამიწეროთ :)

2011-E. გრაფად წარმოვიდგინოთ მოცემული რუკა და ვთქვათ რომ A-დან მივდივართ B-ში და მერე C-ში. (A, B) და (B, C) გზების საერთო წვეროების ფასი ერთხელ უნდა გავითვალისწინოთ. ასეთ უმოკლეს მარშრუტს ზოგადად ექნება შემდეგი სახე: A-დან მივდივართ გარკვეულ X წვერომდე, შემდეგ იქიდან B-ში, შემდეგ ვბრუნდებით ამ X წვეროში და იქიდან მივდივართ C-ში (B=X შემთხვევაში (A, B) და (B, C) გზებს საერთო წვეროები არ აქვთ). ამ გზის სიგრძე არის d(A, X) + d(X, B) + d(X, C). A, B და C წვეროებიდან ყველა სხვა წვერომდე უმოკლეს მანძილებს თუ გამოვთვლით, შემდეგ შეიძლება X წვეროს გადარჩევა და ყველაზე პატარა d(A, X) + d(X, B) + d(X, C) სიდიდის ამორჩევა.

მე გრაფს ვაგებ და უჯრედებს ვთვლი წვეროებად და წიბოებს ვავლებ მეზობელ უჯრედებს შორის. ერთი წვეროდან სხვა ყველა წვერომდე მანძლების გამოსათვლელად O((h*w)*(2*h*w)) ჭირდება,სადაც h*w წვეროების რაოდენობაა და 2*h*w წიბოების რაოდენობა ეს კი დროში არ გავა.სხვა მეთოდი არ არსებობს მანძილების დასათველად?

გრაფი თუ გაქვს h*w წვეროთი, ხომ შეგიძლია დეიქსტრას ალგორითმის მეშვეობით h*w*log(hw) დროში გამოთვალო მანძილები :) აქ უბრალოდ მოდიფიცირებული გრაფია (წონა წვეროებს აქვს და არა წიბოებს) და ამიტომ მცირეოდენ მოდიფიცირებული დეიქსტრა დაგჭირდება.

მივხვდი :) უცბად აღარ მომაგონდა რომ დეიქსტრის ალგორითმი ყველა წვერომდე თვლის მანძლებს,მადლობა გავატარებ ეხლა :)

2011 წლის ფინალის F ამოცანაში სირთულე როგორია?
და კიდევ, რიცხვთა საშუალო დამრგვალებული ზემოდან ან ქვემოდან არ იქნება მინიმალურ გადახრას რომ მოგვცემს? WA4 იყო მაგაზე. მარა მერე საშუალოს გადარცევასაც ვაკეთებდი ოღონდ რიცხვთა საშუალოს ფარგლებში მხოლოდ იმიტომ რომ სხვანაირად TLEს იძლევა:

int delta = 5;
int average_low = max(0.0, floor(sum/(double)(num_of_pixels))-delta),
average_high = min(255.0, ceil(sum/(double)(num_of_pixels))+delta);
და მერე გადარჩევა:
for(int average = average_low; average<=average_high; average++)

ხოდა ვეჭვობ ეს არაა ავტორისეული ამოხსნა :?

"O"(256^3) დროში მუშაობს ჩემი ამოხსნა, ოღონდაც ეს დრო მიაქვს პრეპროცესინგს: ყოველი [i, j] შუალედისთვის ვითვლი, რომელი k პიქსელით ჯობია ჩავანაცვლო ისინი და რა იქნება ამ გადაკოდირების ფასი. შემდეგ ამ ცხრილს ვიყენებ "O"(16*256*256) დინამიური პროგრამირებისთვის. შენი იდეით შეიძლება პირველი ნაბიჯის დაჩქარებაც, თუმცა რა არის დელტას გარანტირებულად მუშა მნიშვნელობა, არ ვიცი. ერთი შეხედვით, მართლაც საშუალოს+-1 უნდა იყოს სწორი.