ვაპირებდი იგივე მეკითხა მარა მეგონა უეჭველი იქნებათქო :დ

ეს წითელი წრფე ორ ნაწილად გაყოფს წერტილთა სიმრავლეს . ვთქვათ პირველ ჯგუფში არის A ცალი , მეორეში B ცალი (A+B=N).

წითელი წრფე გადაკვეთს ზუსტად A*B ლურჯ მონაკვეთს , რადგან თითოეულ ჯგუფში გავლებულ ლურჯ მონაკვეთს არ კვეთს წითელი წრფე , ხოლო განსხვავებულ ჯგუფში თუა ამ მონაკვეთის ბოლოები მაშინ კვეთს.

სულ გაივლება N*(N-1)/2 ლურჯ იმონაკვეთი.
მასჰინ A*B=N*(N-1)/4
4*A*B=(A+B)*(A+B-1)
4*A*B=A^2+B^2+2*A*B-A-B
A^2+B^2-2*A*B-A-B=0
(A-B)^2=A+B=N
ანუ N გამოვიდა (A-B)ს კვადრატი .
რდგ :))

https://geolymp.org/thread/view/47 აჰა დინამიურ პროგრამირებაზე ლინკები აქ წერია.

http://codeforces.com/blog/entry/325

J გვქონდა ჩვენ იდეა , თუმცა დაწერა ვერ მოვასწარით . თავიდან ყველა პალინდრომს დაითვლი o(N) დროში და მერე თვისთიდ პალინდრომის ცენტრს გადაარჩევ, პოზიციას და რომელ სტრინგისაა იმასაც . და მაგ ცენტრიდან უკვე გათვლილი გაქ მაქსიმუმ რა სიგრძეზეა მარჯვნივ და მარცხნივ ტოლი ქვესტრინგები იმავე სტრინგში. და როცა უკვე ტოლია არაა უნდა გადახვიდე მეორე სტრინგზე და ორობითად უნდა გადაარჩიო რა სიგრძის ქვესტრინგია ტოლი ზემოთა სტრინგში დაწყებული რაგაც პოზიციიდან მარცხნივ და ქვედაში დაწყებული საიდანგაც მარჯვნივ . შემოწმებას ხეშირებით დაწერ და NlogN გამოდის დრო.

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

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

ტოპკოდერზე მე-20 ზე რო გადავედით , საქართველოს არ დაკლებია ქულები , სხვებმა მოიმატეს და იმიტომ გადაგვასწრეს.

წითელ–შავ ხეებზე როა მე–5 ამოცანა , მოკლედ ვერ მეტყვით ამოხსნას ან იდეას როგორ იხსნება ?

დინამიური ამოცანები სპოჯზე
http://problemclassifier.appspot.com/index.jsp?search=dp&usr=

მადლობა

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

ხო ეგრე მაქ

კი მანძულაშვილი ვარ , LCA წერის დროსაც მეწერა , მასივი მქონდა პატარა და 1 შემოწმება მაკლდა და არ გადიოდა.

ცოტნე შენი ხინკალიც ამოიხსნა :)