GeOlymp Forum: Opencup GP of ICL

Opencup GP of ICL

ტურის განხილვა

წერილები: 49

17 მარტი 2013, 20:35

http://acm.math.spbu.ru:17249/~ejudge/files/opencup/oc13/gp4/nobdct-e.pdf
A და Jში რა იდეები გქონდათ მაინტერესებს.
ან Fის ავტორის ამოხსნა როგორი იყო.

წერილები: 15

tornike5 says:

17 მარტი 2013, 22:29

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