SRM 589

Анх удаа Hard бодлого бодож үзлээ, том амжилт.

Бодлогуудын оноо 250-450-900 байсан. Тийм болохоор энэ удаад 250-900-450 гэсэн тактикыг сонгосон. Энэ нь 250-г бодоод 900-г оролдож үзнэ, цаг дуусахад 30 минут хүртэл ямар нэг санаа олж чадахгүй бол 450-аа бодох юм.
250:
50-с хэтрэхгүй урттай тэмдэгт мөр өгөгдсөн. Та цагаан толгойн үсгүүдээс X,Y 2 үсэг сонгон авч тэмдэгт мөрд байгаа бүх X үсгийг Y-р солих боломжтой (заавал бүх X-г солих ёстой). Ийм үйлдэл гүйцэтгэхэд хэдэн үсэг өөрчлөгдсөнтэй тэнцүү нэгж хугацаа зарцуулна. Ийм замаар өгөгдсөн тэмдэгт мөрийг хамгийн бага хугацаанд палиндром болго.
DP хэрэглэх гэхээр нэг л эвгүй харагдаад болсонгүй. Тэгэхээр нь нэг greedy алгоритм бичтэл жишээгээ давж байна, нэлээд ч удчихлаа шүү.
900:
N (N<=300) урттай зөвхөн 01-с бүтэх S тэмдэгт мөр, мөн M тоо өгөгдсөн. Хэрвээ ямар нэгэн тэмдэгт мөрийн N-M урттай prefix нь түүний N-M урттай suffix-тай ижил байвал уг мөрийг "эргэдэг" мөр гэе. Та дараах 2 үйлдлийг гүйцэтгэж чадна.

• Аль нэг байрлал дах битийг өөрчилөх (1 байвал 0, 0 байвал 1)
• Тэмдэгт мөрийн эхний k*M битийг өөрчилөх (k хэд ч байж болно)

Таны даалгавар бол хамгийн цөөн үйлдлээр өгөгдсөн тэмдэгт мөрийг "эргэдэг" мөр болгож хувиргах юм.
Лемма: Тэмдэгт мөр нь "эргэдэг" байх зайлшгүй бөгөөд хүрэлцээтэй нөхцөл нь 0<=i<M байх бүх i-н хувьд S(i)=S(i+M)=S(i+2M)=S(i+3M)=... байх юм. Үүнийг батлах хэцүү биш.

Өөр нэг анзаарах зүйл нь үйлдлүүдийн дарааллыг өөрчилөхөд хариу ижил байна. Тиймээс бид эхлээд зөвхөн нэг төрлийн үйлдлийг хийгээд дараа нь нөгөө төрлийн үйлдлийг хийж болно.
S=101100001101, M=3 гэсэн жишээг авч үзье. Тэмдэгт мөрийг 0-с эхлэн дугаарлавал S0=S3=S6=S9, S1=S4=S7=S10, S2=S5=S8=S11 нөхцлийг хангах хэрэгтэй. Тэгвэл ижил бүлгийг баганын дагуу бичвэл:
|S0 |S1 |S2 |
|S3 |S4 |S5 |
|S6 |S7 |S8 |
|S9 |S10|S11|

буюу
|1|0|1|
|1|0|0|
|0|0|1|
|1|0|1|

Тэгэхээр манай бодлого нь бүх баганыг дан 1 эсвэл дан 0 болгох бодлого юм. Бид матрицын дурын элемэнтийг өөрчилөх болон эхний k мөрийг бүгдийг өөрчилөх үйлдлүүдийг гүйцэтгэж чадна.
Эхний k мөрийг өөрчилөх үйлдэлгүйгээр: Энэ тохиолдолд бодлого маш хялбар. Бид баганы бүрийн хувьд дан 1 болгох эсвэл дан 0 болгохын аль ашигтайг сонгоод хариуг олно. O(N)
Эхний k мөрийг өөрчилөх үйлдэлтэй: K үйлдэл гэдгээр эхний k мөрийг солих үйлдлийг тэмдэглэе. Тэгвэл оновчтой хариунд гүйцэтгэгдэж байгаа K үйлдлүүдийг бүхэл тоон олонлогоор илэрхийлж болно {1,2,3}, {1,1} гэх мэт. Гэхдээ ижил K үйлдлийг хоёр буюу түүнээс дээш удаа гүйцэтгэх нь ямар ч хэрэггүй. Тиймээс боломжит K үйлдлүүдийн олонлог нь хамгийн ихдээ 2^{мөрийн тоо} ширхэг байна. мөрийн тоо нь ceil(N/M). Ямар K үйлдэл хийхээ мэдэж байгаа тохиолдолд уг үйлдлүүдээ гүйцэтгээд бодлого маань дээрх хэлбэр рүү шилжинэ. Бид энэ аргаар бодлогыг O(2^N/M*N) хугацаанд бодож чадна. N/M <=18 үед хангалттай амжих ч M=1 үед N/M нь 300 байх боломжтой. N/M>18 үед өөр алгоритмаар бодно.
N/M>18 буюу M <= 17: Бид энэ хязгаарлалтанд бодчихвол бодлого маань дуусчихлаа л гэсэн үг. Энэ удаад M буюу нэг мөрөн дэх элемэнтийн тоо нь цөөхөн байгааг анзаарсан байх. Эцсийн хариу болох тэмдэгт нэг мөрөөс л хамаарна, учир нь бүх мөрүүд хоорондоо ижилхэн байх ёстой. Эндээс бид бүх 2^M боломжийг үүсгээд S-г уг тэмдэгт мөр рүү хувиргах хамгийн богино үйлдлийг Динамик програмчлал ашиглан бодож болно. Үүнийг мөн O(2^M*N) хугацаанд бодож чадна. Энэ удаад Динамик програмчлалыг бичилгүй орхиё.
Дээрх бүгд нийлээд өгөгдсөн бодлогыг хамгийн муу тохиолдолд O(2^sqrt(N)N)-д бодож чадна.
Бас л урт бодолт байлаа тийм үү? Div-1 Hard аа гэж.

After system testing phase:

Эхний бодлого маань уначихсан, хэрэв давсан бол нэлээд дээгүүр бичигдэх байлаа. Ямар ч байсан rating өсөөд 2025 боллоо.