დამთავრდა ჯეოლიმპის მეორე ეპიზოდი.

შედეგები/აპსოლვინგი ამ ლინკზე შეგიძლიათ იხილოთ.

თუ რაიმე გაინტერესებთ შეკითხვები შეგიძლიათ აქ დასვათ ;)

მეოთხე ამოცანა დინამიურით იხსნება?

giorgi123: კი, დინამიურია. თუმცა რამოდენიმე უცნაური ამოხსნა დავინახეთ, მაგალითად varlevani-ს, რომელიც როგორც ჩანს რაღაც სხვა იდეას იყენებს. შეიძლება მოგვიყვებიან.

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

ვულოცავ ჯიმის, მგონი პირველ პირველ ადგილს აქ.

@Quick

დინამიურით ვაკეთებ, მხოლოდ - [i,j] ნაწილი არის თუ არა 1,2,...,j-i+1 რიცხვების გადანაცვლება - მაგას ჰეშირებით ვიგებ.

@giorgi123
იდეა ასეთია:
ელემენტში ითვლი , , ..., ელემენტების j ცალ ნაწილად დაყოფების რაოდენობას.

მიიღება -ების ჯამი, სადაც , , ..., არის რიცხვების გადანაცვლება.
საბოლოო პასუხია


მეც ვულოცავ ჯიმის გამარჯვებას!

@varlevani
sps

რას გულისხმობთ დინამიურში

დინამიურში ის იგულისხმება, რომ -ს მნიშვნელობას ვითვლით წინა ბიჯზე მიღებული -ების მნიშვნელობებიდან.

ვუერთდები მილოცვას. ყოჩაღ ჯიმი!

მე-4 ამოცანაში ის ვერ გავიგე - მეორე რიცხვი რატოა მოცემულია, ეგ ცალსახად არ განისაზღვრება მოცემული მიმდევრობიდან?

მე-5 როგორ ამოხსნეს ვინც გაატარა?

მე-4-ში კი განისაზღვრება, მაგრამ მაგას მხოლოდ მაჭავარიანი მიხვდა (ყოველ შემთხვევაში მხოლოდ მაგან გამოიყენა).

მე-5-ში 2 ამოხსნა იყო პრეპროცესინგში ფესვიდან ყოველ წვერომდე რასების რაოდენობის დათვლა და შემდეგ O(logN + K) დროში პასუხი ყოველ შეკითხვაზე, 1 კი პრეპროცესინგის დროს იმახსოვრებდა წვეროდან მის 2^i მშობლებამდე შეხვედრილი რასების ბიტმასკს და შეკითხვებს logN * K/32 დროში პასუხობდა.