Dreaming:
Энэ бодлого энэ удаагийн олимпиадын 2 дахь амархан бодлого байсан. Баярхүү сайн бодсон, бүтэн бодолт. Нэг илүү юмыг ярихад өнгөрсөн хавар улсын олимпиадад энэнээс хамаагүй хүнд модны бодлогыг бодсон 2 хүүхэд яагаад энийг бодож чадсангүй вэ?
За анализдаа ороё.
Бодлогын хариу 2 тохиолдолд байж болно. Нэг нь компонент бүрийн хамгийн урт замуудын хамгийн урт нь. Модны хамгийн урт замыг диаметр гэж нэрлэдэгийг хэлж байсан. Үүнийг 2 түвшний нэвтрэлт хийгээд эсвэл, гүний нэвтрэлт хийгээд орой бүрийн хувьд хамгийн урт 2 дэд модны нийлбэрээр тодорхойлогдоно. Одоо тэгвэл эдгээр компонентуудаа холбох ирмэг нэмбэл яах мөн аль орой дээр нэмэх вэ? Бид орой бүрийн хувьд хамгийн хол орших оройг жинтэй нь хамт ганц түвшний нэвтрэлт хийгээд олж чадна. Тэгвэл компонент бүрийн хувьд хамгийн хол замыг агуулсан оройг олоод үүнийгээ жингүүдээр нь эрэмбэлэе. Үүнийг модны радиус гэж нэрлэдэг, тус бүр r1 > r2> r3> .. гэж үзье. Тэгэхээр ядаж r1+r2+L эсвэл r2+r3+L гэсэн урттай зам байж таарна. Бодлогын хариу энэ 2-н их нь байна, яагаад?
Art Class:
Heuristic search төрлийн бодлого байх. Ийм төрлийн юм судлаж байгаагүй болохоор доривтой юм хэлж чадахгүй нь IOI-д ч ийм бодлого ирж байсан удаагүй. Гэхдээ толгойд байгаа бодолт, бодлогын хариу тухайн бүсэд байгаа өнгнүүдийн давтамжуудаас тодорхойлогдох нь харагдаж байна. Тэгэхээр тэрийг эвтэйхэн тооцоолоох хэрэгтэй. DP ашиглаад 2^6 хүртлэх бүх талтай бүх хэсэгүүдэд байгаа өнгөнүүдийн давтамжуудийг тоолчиж чадна. Зургийн төрөл бүрийн хувьд тухайн өнгний давтамжуудыг ойролцоогоор тооцоолчиж болно. Түүнтэйгээ жишээд хариугаа гаргах, ийм л юм толгойд байна.
Thursday, December 12, 2013
Tuesday, October 8, 2013
USACO temtseen.
Sain baitsgaana uu.
Latin-aar bichij bgad dahiad l uuchlaarai, surguuliin computer-aas bichij baigaa bolohoor tohiruulahaas zalhuu hurchlee. 2 duulgah medee baina.
1t ni: http://www.usaco.org/ ene deer boloh temtseenuudiin bodlogiig orchuulah bolsonoo medegdej baisan. Ene heverei baigaa mun temtseenuud ireh saraas ehlene. Ene site-n talaar meddeggui humuust bichihed ene ni America-n medeelel zuin olimpiadiin tsuvral temtseen ba 11n saraas ehlen sar bur temtseen zohioj 10 ni yalagchid ni IOI-n beltgeld suuj tendeesee IOI-n bagaa burduuldeg yum. Neg yosnii manai ulsiin olimpiad gesen ug. Temtseen bur Bronze, Silver, Gold gesen 3n yanz baih ba Bronze ni eronhii medlegtei huuhduuded, Silver ni arai hundreed songodog algorithmuudiig shaardna, Gold ni hamgiin hund ni ba tuhain suragchaas mash ih turshlaga algorithm chadvar shaardna. Temtseen 5n tsagiin hugatsaatai boloh ba uursduu tsagaa tohiruulj baigaad hamgiin bolomjtoi uedee tuhain temtseenii neelttei udruuded amjij oroh yostoi shuu. Temtseenuudiin huvaari:
Nov 16-19: November Contest
Dec 14-17: December Contest
Jan 11-14: January Contest
Feb 8-11: February Contest
Mar 8-11: March Contest
April 5-8: US Open
May 23-June 1: Training Camp
July 6-13: IOI'13 in Brisbane, Australia **,
Za amjilt sain oroltsooroi, bodloguudiig orchuulah tiim ch amar ajil bish, temtseend huuhduud idevhtei oroltsohgui haragdval tegeed eronhiidoo bi orchuulahaa bolino.
2 dahi medee:
http://cerberus.delos.com:791/usacogate Ene site-g bas medeh baih, America-n huuhduudiin algorithm-n surgaltiin site geh yumuudaa. Ene site-g bi mun Mongol bolgoh orchuulah erh avsan baigaa. Zavtai uedee orchuulaad l yavna. Za tegeed amjilt husey, asuuj todruulah zuilee asuugarai.
-Bye.
Latin-aar bichij bgad dahiad l uuchlaarai, surguuliin computer-aas bichij baigaa bolohoor tohiruulahaas zalhuu hurchlee. 2 duulgah medee baina.
1t ni: http://www.usaco.org/ ene deer boloh temtseenuudiin bodlogiig orchuulah bolsonoo medegdej baisan. Ene heverei baigaa mun temtseenuud ireh saraas ehlene. Ene site-n talaar meddeggui humuust bichihed ene ni America-n medeelel zuin olimpiadiin tsuvral temtseen ba 11n saraas ehlen sar bur temtseen zohioj 10 ni yalagchid ni IOI-n beltgeld suuj tendeesee IOI-n bagaa burduuldeg yum. Neg yosnii manai ulsiin olimpiad gesen ug. Temtseen bur Bronze, Silver, Gold gesen 3n yanz baih ba Bronze ni eronhii medlegtei huuhduuded, Silver ni arai hundreed songodog algorithmuudiig shaardna, Gold ni hamgiin hund ni ba tuhain suragchaas mash ih turshlaga algorithm chadvar shaardna. Temtseen 5n tsagiin hugatsaatai boloh ba uursduu tsagaa tohiruulj baigaad hamgiin bolomjtoi uedee tuhain temtseenii neelttei udruuded amjij oroh yostoi shuu. Temtseenuudiin huvaari:
Nov 16-19: November Contest
Dec 14-17: December Contest
Jan 11-14: January Contest
Feb 8-11: February Contest
Mar 8-11: March Contest
April 5-8: US Open
May 23-June 1: Training Camp
July 6-13: IOI'13 in Brisbane, Australia **,
Za amjilt sain oroltsooroi, bodloguudiig orchuulah tiim ch amar ajil bish, temtseend huuhduud idevhtei oroltsohgui haragdval tegeed eronhiidoo bi orchuulahaa bolino.
2 dahi medee:
http://cerberus.delos.com:791/usacogate Ene site-g bas medeh baih, America-n huuhduudiin algorithm-n surgaltiin site geh yumuudaa. Ene site-g bi mun Mongol bolgoh orchuulah erh avsan baigaa. Zavtai uedee orchuulaad l yavna. Za tegeed amjilt husey, asuuj todruulah zuilee asuugarai.
-Bye.
Tuesday, July 9, 2013
IOI 2008 Island source code
Omnoh poston deer bichsen analyze-n daguu bichsen source-g postolloo. Latin-aar bichij bgad uuchlaarai, oor arga alga kk. Yag sonirhoj tsag gargaj suuj bga huuhded, asuuval, iluu, dutuu zuiluudiig tailbarlaj zaaj ogno. Tiimees source-nd ymr ch tailbar hiihgui.
#include <cstdio>
#include <cstdlib>
#define MaxN 500010
#define MaxM 1000020
#define LL long long
using namespace std;
int N, M, Last[MaxN], Next[MaxN], Pre[MaxM];
int spoint, Q[MaxM], Other[MaxM], Opp[MaxM], tNext[MaxM];
LL Ans, Tot, Rec[MaxM], Dist[MaxM], Cost[MaxM], F[MaxN];
char V[MaxN] = {0}, Col[MaxN] = {0};
void Gf1(int Now, int Fa) {
int y, k, m;
for (V[Now] = 1, y = Last[Now]; y != 0; y = Pre[y]) {
k = Other[y];
if (!V[k]) {
tNext[Now] = y;
Gf1(k, Opp[y]);
} else if(y != Fa && spoint == -1) {
m = Now; tNext[Now] = y; spoint = Now;
do {
Col[m] = 1;
Next[m] = tNext[m];
m = Other[Next[m]];
} while (m != Now);
}
}
}
void Gf2(int Now, int Fa) {
int y, k; LL m, m1, m2;
for (m = m1 = m2 = 0, y = Last[Now]; y != 0; y = Pre[y]) {
k = Other[y];
if (y != Fa && !Col[k]) {
Gf2(k, Opp[y]);
m = F[k]+Cost[y];
if (m > m1) {
m2 = m1;
m1 = m;
} else if (m > m2) m2 = m;
}
}
F[Now] = m1;
if (Ans < m1+m2)
Ans = m1+m2;
}
int main() {
LL v1, v2, Len;
int i, k, x, t, h, Now;
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
for (scanf("%d", &N), k = 0, i = 1; i <= N;i ++) {
scanf("%d %lld",&x, &Len);
Other[++k] = i; Cost[k] = Len; Opp[k] = k+1; Pre[k] = Last[x]; Last[x] = k;
Other[++k] = x; Cost[k] = Len; Opp[k] = k-1; Pre[k] = Last[i]; Last[i] = k;
}
for (Tot = 0, k = 1; k <= N; k++) if (!V[k]) {
spoint = -1; Gf1(k, -1); Now = spoint;
Ans = 0; M = 0; t = 0; h = 0;
do {
M++;
Gf2(Now,-1);
Now = Other[Next[Now]];
} while (Now!=spoint);
for (Dist[1] = 0, i = 1; i < M+M ; i++) {
Dist[i+1] = Dist[i] + Cost[Next[Now]];
Rec[i] = F[Now];
v1 = Dist[i]+Rec[i];
v2 = -Dist[i]+Rec[i];
while (i-Q[h] >= M)
h++;
if (h > 0 && Ans < v1-Dist[Q[h]]+Rec[Q[h]])
Ans = v1 - Dist[Q[h]] + Rec[Q[h]];
while (t > 0 && t >= h && v2 > Rec[Q[t]]-Dist[Q[t]])
t--;
Now = Other[Next[Now]]; Q[++t] = i;
}
Tot += Ans;
}
printf("%lld\n", Tot);
return 0;
}
Friday, May 31, 2013
Trie өгөгдөлийн бүтэц, IOI 2008 Type Printer бодлогын бодолт, IOI 2008 Islands бодлогын анализ.
За сайн байцгаана уу,
Бодлогын өгүүлбэрийг ЭНД дарж Монголоор уншина уу.
Trie:
Энэ нь бусад модтой адил төрлийн өгөгдөлийн бүтэц. Хоёртын хайлтын мод нь модны орой бүр 2 хүүтэй байдаг бол Траэй нь орой бүр тухайн бодлогоосоо шалтгаалаад хэдэн ч хүү-оройтой байж болно. Бидний бодлогын хувьд жижиг латин цагаан толгойн үсэгнүүд байж болох тул орой бүр 26-н хүүтэй. Траэй модны үндэс нь ганцаараа хоосон байна. Доор зургаар дэлгэрэнгүй тайлбарлая.
TREE
TRIE
ALL
ALSO
ALGO
ASSOC
Эдгээр үгнүүд хэрхэн Траэй модонд нэмэгдсэн байгааг харж байгаа байх. Траэй модонд үг нэмэх, хасах, хайх үйлдэл бүгд шугаман буюу O(N) байхыг хялбархан харж болно.
Бодлогоруугаа эргээд оръё. Бидний зорилго бүх үгийг хэвлэх, хэвлэхдээ хамгийн цөөн үйлдлээр. Мөн хамгийн сүүлд хэвлэсэн үгний дараа устгах үйлдэл хийлгүй шууд програм зогсох ёстой. Тэгвэл бидэнд гарч ирэх асуудлууд:
үсэг хэвлэх машин дээр тавина гэдэг юу гэсэн үг вэ?
хэвлэх машин дээрх үсэгнүүдийг хэвлэнэ гэдэг маань юу гэсэн үг вэ?
хэвлэх машинаас үсэг устгах нь юу гэсэн үг вэ?
Эдгээр асуултуудын хариултыг Траэй модны үндсэн үйлдэлүүд л хариулчихна. Модондоо гүний нэвтрэлт хийе. Нэвтрэлт хийн тухайн түвшинээс нэг түвшин доошлоно гэдэг нь хэвлэх машин дээр тухайн үсгийг тавьж байна, гүний нэвтрэлт буцалтаа хийх буюу тухайн түвшингийн дээр байрлах эцэг орой руу очино гэдэг нь хэвлэх машинаас үсэг устгахтай адил '-' команд. Харин үсэгүүдийг хэвлэнэ гэдэг нь нэг бүтэн үг олсон эсвэл модны навч дээр очсон тохиолдолд 'P' команд биелэгдэнэ. Бидний гол асуудал хамгийн цөөн үйлдэлээр бүх үгийг хэвлэх. Траэй модондоо гүний нэвтрэлт хийгээд, хэвлээд хамгийн сүүлд хэвлэгдсэн үгний дараа буцаад устгах шаардлага байхгүй.
Тэгвэл хамгийн сүүлд ямар үгийг хэвлэх ёстой вэ? Хариулт мэдээж хамгийн урт үгийг. Хамгийн урт үгийг хамгийн сүүлд хэвлэсэн л бол өмнөх үгнүүдийг ямар ч дарааллаар хэвлэсэн бодлогын хариуг өөрчилж чадахгүй. Яагаад? Энэ нь биднарт хамгийн урт үгнээс бусад бүх үгнүүдийг санаа зоволтгүй гүний нэвтрэлт хийгээд хэвлэх боломж олгоно.
Бид мод дээр үйлдэл хийж байгаа, хамгийн урт үгэнд орж байгаа үсэгнүүдээс бусад үсэг бүгд яг 2 удаа ашиглагдана, хэвлэх машин дээр өрөх мөн хэвлэх машинаас устгах. Тэгвэл одоо гарч ирэх асуудал хэрхэн хамгийн урт үгээ Траэй модноос ялгаж хамгийн сүүлд хэвлэх вэ?
Гүний нэвтрэлт хийгээд хамгийн урт үгээ олж байгаад хамгийн урт үгэнд орж байгаа оройнуудыг тэмдэглэчихэж болно. Тэгээд Траэй хэвлэх үйлдэлдээ нэмэлт ганц нөхцөл нэмээд, энэ нөхцөл нь мэдээж тэмдэглэгдээгүй орой байх. Хамгийн урт үгийг бүтэн модондоо гүний нэвтрэлт хийснээс, өгөгдөлөө уншихдаа хамгийн урт үгийг олж байгаад мөн бүх үгнүүд модонд тэмдэглэгдсэний дараа хайлт хийж тэмдэглэсэн нь хамаагүй хурдан. Яагаад?
Үг нэмэхдээ анхаарах зүйл бол ямар нэгэн бүтэн үг нэмсэн л бол тухайн үгний сүүлийн үсгийг бүтэн үг эсвэл навч гэдэгийг тэмдэглэх ёстой. Ингэснээр бид хэвлэх командаа төвөггүйхэн хийж чадна. Жишээ нь доорх өгөгдлийг бодоод үзээрэй.
2
aabc
aabcde
Энэ үед хариу нь:
8
a
a
b
c
P
d
e
P
Мөн энэ жишээнээс би яагаад шууд дан ганц навч гээд хэлчихээгүй харах байх. C++ дээрх кодыг тавьлаа, гэхдээ энэ удаад өгөгдөлийн бүтэц, санах ойтой харьцаж байгаа тул арай доод түвшний код байх болно, гэхдээ хурдхан шиг аль болох учирыг нь олж сурах хэрэгтэй.
Арлууд бодлогын Монгол өгүүлбэрийг ЭНД дарж уншина уу.
Бидэнд чиглэлгүй жинтэй граф комфонентууд өгөгдсөн. Компонент бүр хамгийн ихдээ ганц цикл агуулна. Тэгвэл компонент бүрийн диаметрүүдийн нийлбэрийг ол гэсэн бодлого.
Бодлого энгийн хоёр тохиолдолтой. Комфонент цикл агуулсан, агуулаагүй.
Цикл агуулаагүй комфонент нь мод байна. Модны диаметрийг олохдоо дурын А оройноос нэвтрэлт хийн, гүний, түвшний аль нь ч болно, хамгийн хол орших оройг В гэе, В оройгоос дахин нэвтрэлт хийн хамгийн хол С орой дээр ирсэн гэж үзвел сүүлийн С-ээс В хүртлэх жин нь тухайн модны диаметр болно.
Цикл агуулсан үед:
Тухайн N оройтой компонент яг N ширхэг ирмэгтэй байна гэсэн үг, яагаад? ямар нэгэн ирмэгийг хасая, N-1 ирмэгтэй мод үүсгэн, энэ модны диаметрийг дээрх аргаар олж болно O(N)-д. Тэгвэл бүх ирмэгийг хасаж үзээд хагийн урт диаметртэй модыг сонгох замаар бодвол бодолт O(N^2) болно. Энэ бодолт 40% тэст давна.
Арай хурдан бодолт олох гэж үзье.
Тухайн компонент дахь цикл нь С урттай мөн V1, V2, V3,...,Vc гэсэн оройнуудтай байг.
Тэгвэл тухайн цикл-д харьялагдаж байгаа орой бүрийг ямар нэгэн мондын үндэс болгоё. Гэхдээ анхаарах зүйл энэ үндэс нь тухайн цикл-д агуулагдаж байгаа аль ч оройг өөрийн хүү болгон авах ёсгүй. Тэгвэл зарим тохиолдолд зөвхөн ганцхан оройтой, үндэстэй, мод үүсэж болно. Дээрх жишээнд V3, V4, V6, V7-оос бусад нь бүгд ганцхан үндэстэй мод болох нь. Бид эдгээр моднуудын уртыг олчиж чадна, энэ удаад хоёр нэвтрэлт хийх хэрэггүй, яагаад гэвэл зөвхөн Vi-дээр энэ модны орой байгаа учир бид энэ оройгоос хамгийн хол орших оройн хоорондахь жинг л сонирхож байгаа, үүнийг модны өндөр ч гэж нэрлэж болно, энэ өндөрийг Ki гэе, Vi дээр оройтой модны өндөр. Яг ийм компоненттэй үед бодлогын хариу маань ямар нэгэн хоёр модны жингүүдийн мөн тухайн хоёр модны, энэ хоёр модны үндэс нь цикл дээр байраа, үндэснүүдийн хоорондах зайн нийлбэрийг максимумчилна.
Одоо тэгвэл тухайн хоёр модны үндэсний хоорондахь зай хэрхэн гарж болохыг харъя.
Vi, Vj ( i < j ) гэе. Vi-ээс Vj-рүү хоёр янзаар очиж болно.
1: Vi, Vi+1, Vi+2, .. , Vj-1, Vj.
2: Vi, Vi-1, Vi-2, .. , Vc, Vc-1, .. , Vj+1, Vj. Яагаад?
Wi-ээр Vi-ээс Vi+1-р оройн хоорондахь жинг тэмдэглэвэл дээрх хоёр замын жин маань:
1: Wi + Wi1 + , .., Wj-1,
2: Wi-1 + Wi-2 + , .., Wc-1 + ,.., Wj = Wj + Wj+1 + .. + Wc + .. + Wi-1.
Тухайн циклийхаа жинг Wc гэвэл дээрх хоёр замын жингийн нийлбэр Wc байна. Яагаад?. Мөн цикл дээрх дурын хоёр оройн хоорондахь жин нь циклийхаа жинг хэсэгчилж байгааг харж байгаа байх. Si-ээр Vi хүртлэх жингүүдийн нийлбэрийг дараах байдлаар тодорхойлоё. S1 = 0, Si = S(i-1) + Wi. Тэгвэл дээрх хоёр нийлбэр маань дараах нийлбэртэй тэнцүү:
(1) = Sj - Si.
(2) = Wc - (Sj-Si). Энд мэдээж циклийн оройнууд дээр ярьж байгаа ба i < j байна.
Тэгвэл бид дараах хариуг л олох гээд байгаа юм: max{Ki+Kj+max(Sj‐Si,S‐(Sj‐Si))} ( i < j ).
Үүнийг бүх хосуудаас максимумыг олох замаар үзвэл O(C^2) бодолт болох ба кодоо хэрхэн цэвэх бичсэнээс шалтгаалт нийт онооны 60-80%-г авч чадна. Бүтэн бодолт O(C)-д хийх ёстой, үүнийг бэлтгэл хийж байгаа хүүхдүүд, мөн сонирхон бодож байгаа хүмүүст өөрсөд нь үлдээе.
Бодлогын өгүүлбэрийг ЭНД дарж Монголоор уншина уу.
Trie:
Энэ нь бусад модтой адил төрлийн өгөгдөлийн бүтэц. Хоёртын хайлтын мод нь модны орой бүр 2 хүүтэй байдаг бол Траэй нь орой бүр тухайн бодлогоосоо шалтгаалаад хэдэн ч хүү-оройтой байж болно. Бидний бодлогын хувьд жижиг латин цагаан толгойн үсэгнүүд байж болох тул орой бүр 26-н хүүтэй. Траэй модны үндэс нь ганцаараа хоосон байна. Доор зургаар дэлгэрэнгүй тайлбарлая.
TREE
TRIE
ALL
ALSO
ALGO
ASSOC
Эдгээр үгнүүд хэрхэн Траэй модонд нэмэгдсэн байгааг харж байгаа байх. Траэй модонд үг нэмэх, хасах, хайх үйлдэл бүгд шугаман буюу O(N) байхыг хялбархан харж болно.
Бодлогоруугаа эргээд оръё. Бидний зорилго бүх үгийг хэвлэх, хэвлэхдээ хамгийн цөөн үйлдлээр. Мөн хамгийн сүүлд хэвлэсэн үгний дараа устгах үйлдэл хийлгүй шууд програм зогсох ёстой. Тэгвэл бидэнд гарч ирэх асуудлууд:
үсэг хэвлэх машин дээр тавина гэдэг юу гэсэн үг вэ?
хэвлэх машин дээрх үсэгнүүдийг хэвлэнэ гэдэг маань юу гэсэн үг вэ?
хэвлэх машинаас үсэг устгах нь юу гэсэн үг вэ?
Эдгээр асуултуудын хариултыг Траэй модны үндсэн үйлдэлүүд л хариулчихна. Модондоо гүний нэвтрэлт хийе. Нэвтрэлт хийн тухайн түвшинээс нэг түвшин доошлоно гэдэг нь хэвлэх машин дээр тухайн үсгийг тавьж байна, гүний нэвтрэлт буцалтаа хийх буюу тухайн түвшингийн дээр байрлах эцэг орой руу очино гэдэг нь хэвлэх машинаас үсэг устгахтай адил '-' команд. Харин үсэгүүдийг хэвлэнэ гэдэг нь нэг бүтэн үг олсон эсвэл модны навч дээр очсон тохиолдолд 'P' команд биелэгдэнэ. Бидний гол асуудал хамгийн цөөн үйлдэлээр бүх үгийг хэвлэх. Траэй модондоо гүний нэвтрэлт хийгээд, хэвлээд хамгийн сүүлд хэвлэгдсэн үгний дараа буцаад устгах шаардлага байхгүй.
Тэгвэл хамгийн сүүлд ямар үгийг хэвлэх ёстой вэ? Хариулт мэдээж хамгийн урт үгийг. Хамгийн урт үгийг хамгийн сүүлд хэвлэсэн л бол өмнөх үгнүүдийг ямар ч дарааллаар хэвлэсэн бодлогын хариуг өөрчилж чадахгүй. Яагаад? Энэ нь биднарт хамгийн урт үгнээс бусад бүх үгнүүдийг санаа зоволтгүй гүний нэвтрэлт хийгээд хэвлэх боломж олгоно.
Бид мод дээр үйлдэл хийж байгаа, хамгийн урт үгэнд орж байгаа үсэгнүүдээс бусад үсэг бүгд яг 2 удаа ашиглагдана, хэвлэх машин дээр өрөх мөн хэвлэх машинаас устгах. Тэгвэл одоо гарч ирэх асуудал хэрхэн хамгийн урт үгээ Траэй модноос ялгаж хамгийн сүүлд хэвлэх вэ?
Гүний нэвтрэлт хийгээд хамгийн урт үгээ олж байгаад хамгийн урт үгэнд орж байгаа оройнуудыг тэмдэглэчихэж болно. Тэгээд Траэй хэвлэх үйлдэлдээ нэмэлт ганц нөхцөл нэмээд, энэ нөхцөл нь мэдээж тэмдэглэгдээгүй орой байх. Хамгийн урт үгийг бүтэн модондоо гүний нэвтрэлт хийснээс, өгөгдөлөө уншихдаа хамгийн урт үгийг олж байгаад мөн бүх үгнүүд модонд тэмдэглэгдсэний дараа хайлт хийж тэмдэглэсэн нь хамаагүй хурдан. Яагаад?
Үг нэмэхдээ анхаарах зүйл бол ямар нэгэн бүтэн үг нэмсэн л бол тухайн үгний сүүлийн үсгийг бүтэн үг эсвэл навч гэдэгийг тэмдэглэх ёстой. Ингэснээр бид хэвлэх командаа төвөггүйхэн хийж чадна. Жишээ нь доорх өгөгдлийг бодоод үзээрэй.
2
aabc
aabcde
Энэ үед хариу нь:
8
a
a
b
c
P
d
e
P
Мөн энэ жишээнээс би яагаад шууд дан ганц навч гээд хэлчихээгүй харах байх. C++ дээрх кодыг тавьлаа, гэхдээ энэ удаад өгөгдөлийн бүтэц, санах ойтой харьцаж байгаа тул арай доод түвшний код байх болно, гэхдээ хурдхан шиг аль болох учирыг нь олж сурах хэрэгтэй.
//Trie
//IOI 2008 Type Printer.
//by Baska.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <cmath>
#include <map>
#include <sstream>
#include <functional>
#include <numeric>
#define mp make_pair
#define pb push_back
using namespace std;
long long toint(string s) { istringstream in(s); long long x; in>>x; return x; }
template<class T> string tostring(T x) { ostringstream out; out<<x; return out.str();}
inline int convertIn(char ch){ return ch-'a'; }
inline char convertOut(int v){ return v+'a'; }
int total;
struct trie{
bool isLast;
bool isLeaf;
trie *next[26];
trie(){
for(int i=0; i<26; i++)
next[i] = NULL;
isLast = 0;
isLeaf = 0;
}
};
inline void insert(trie* root, char *str, int len){
for(int k, i=0; i<len; i++){
k = convertIn(str[i]);
if(root->next[k]==NULL){
root->next[k] = new trie();
total += 2;
}
root = root->next[k];
}
root->isLeaf = 1;
}
inline void printTrie(trie *root){
for(int i=0; i<26; i++){
if(root->next[i]!=NULL&&!root->next[i]->isLast){
printf("%c\n", convertOut(i));
if(root->next[i]->isLeaf)
printf("P\n");
printTrie(root->next[i]);
printf("-\n");
}
}
}
inline void searchAndMark(trie *root, char *word){
for(int i=0, len = strlen(word); i<len; i++){
int k = convertIn(word[i]);
root->next[k]->isLast = 1;
root = root->next[k];
}
}
int main(int argc, char *argv[]){
int n;
char longestWord[22];
scanf("%d", &n);
total = n;
trie *root = new trie();
while(n--){
char word[22];
scanf("%s", word);
if(strlen(word)>strlen(longestWord))
strcpy(longestWord, word);
insert(root, word, strlen(word));
}
searchAndMark(root, longestWord);
printf("%d\n", total-strlen(longestWord));
printTrie(root);
for(int i=0, len = strlen(longestWord); i<len; i++){
printf("%c\n", longestWord[i]);
int k = convertIn(longestWord[i]);
printTrie(root->next[k]);
if(root->next[k]->isLeaf)
printf("P\n");
root = root->next[k];
}
return 0;
}
Арлууд бодлогын Монгол өгүүлбэрийг ЭНД дарж уншина уу.
Бидэнд чиглэлгүй жинтэй граф комфонентууд өгөгдсөн. Компонент бүр хамгийн ихдээ ганц цикл агуулна. Тэгвэл компонент бүрийн диаметрүүдийн нийлбэрийг ол гэсэн бодлого.
Бодлого энгийн хоёр тохиолдолтой. Комфонент цикл агуулсан, агуулаагүй.
Цикл агуулаагүй комфонент нь мод байна. Модны диаметрийг олохдоо дурын А оройноос нэвтрэлт хийн, гүний, түвшний аль нь ч болно, хамгийн хол орших оройг В гэе, В оройгоос дахин нэвтрэлт хийн хамгийн хол С орой дээр ирсэн гэж үзвел сүүлийн С-ээс В хүртлэх жин нь тухайн модны диаметр болно.
Цикл агуулсан үед:
Тухайн N оройтой компонент яг N ширхэг ирмэгтэй байна гэсэн үг, яагаад? ямар нэгэн ирмэгийг хасая, N-1 ирмэгтэй мод үүсгэн, энэ модны диаметрийг дээрх аргаар олж болно O(N)-д. Тэгвэл бүх ирмэгийг хасаж үзээд хагийн урт диаметртэй модыг сонгох замаар бодвол бодолт O(N^2) болно. Энэ бодолт 40% тэст давна.
Арай хурдан бодолт олох гэж үзье.
Тухайн компонент дахь цикл нь С урттай мөн V1, V2, V3,...,Vc гэсэн оройнуудтай байг.
Тэгвэл тухайн цикл-д харьялагдаж байгаа орой бүрийг ямар нэгэн мондын үндэс болгоё. Гэхдээ анхаарах зүйл энэ үндэс нь тухайн цикл-д агуулагдаж байгаа аль ч оройг өөрийн хүү болгон авах ёсгүй. Тэгвэл зарим тохиолдолд зөвхөн ганцхан оройтой, үндэстэй, мод үүсэж болно. Дээрх жишээнд V3, V4, V6, V7-оос бусад нь бүгд ганцхан үндэстэй мод болох нь. Бид эдгээр моднуудын уртыг олчиж чадна, энэ удаад хоёр нэвтрэлт хийх хэрэггүй, яагаад гэвэл зөвхөн Vi-дээр энэ модны орой байгаа учир бид энэ оройгоос хамгийн хол орших оройн хоорондахь жинг л сонирхож байгаа, үүнийг модны өндөр ч гэж нэрлэж болно, энэ өндөрийг Ki гэе, Vi дээр оройтой модны өндөр. Яг ийм компоненттэй үед бодлогын хариу маань ямар нэгэн хоёр модны жингүүдийн мөн тухайн хоёр модны, энэ хоёр модны үндэс нь цикл дээр байраа, үндэснүүдийн хоорондах зайн нийлбэрийг максимумчилна.
Одоо тэгвэл тухайн хоёр модны үндэсний хоорондахь зай хэрхэн гарж болохыг харъя.
Vi, Vj ( i < j ) гэе. Vi-ээс Vj-рүү хоёр янзаар очиж болно.
1: Vi, Vi+1, Vi+2, .. , Vj-1, Vj.
2: Vi, Vi-1, Vi-2, .. , Vc, Vc-1, .. , Vj+1, Vj. Яагаад?
Wi-ээр Vi-ээс Vi+1-р оройн хоорондахь жинг тэмдэглэвэл дээрх хоёр замын жин маань:
1: Wi + Wi1 + , .., Wj-1,
2: Wi-1 + Wi-2 + , .., Wc-1 + ,.., Wj = Wj + Wj+1 + .. + Wc + .. + Wi-1.
Тухайн циклийхаа жинг Wc гэвэл дээрх хоёр замын жингийн нийлбэр Wc байна. Яагаад?. Мөн цикл дээрх дурын хоёр оройн хоорондахь жин нь циклийхаа жинг хэсэгчилж байгааг харж байгаа байх. Si-ээр Vi хүртлэх жингүүдийн нийлбэрийг дараах байдлаар тодорхойлоё. S1 = 0, Si = S(i-1) + Wi. Тэгвэл дээрх хоёр нийлбэр маань дараах нийлбэртэй тэнцүү:
(1) = Sj - Si.
(2) = Wc - (Sj-Si). Энд мэдээж циклийн оройнууд дээр ярьж байгаа ба i < j байна.
Тэгвэл бид дараах хариуг л олох гээд байгаа юм: max{Ki+Kj+max(Sj‐Si,S‐(Sj‐Si))} ( i < j ).
Үүнийг бүх хосуудаас максимумыг олох замаар үзвэл O(C^2) бодолт болох ба кодоо хэрхэн цэвэх бичсэнээс шалтгаалт нийт онооны 60-80%-г авч чадна. Бүтэн бодолт O(C)-д хийх ёстой, үүнийг бэлтгэл хийж байгаа хүүхдүүд, мөн сонирхон бодож байгаа хүмүүст өөрсөд нь үлдээе.
Sunday, May 26, 2013
Тэмцээн KB-3
За сайн байцгаана уу,
Тэмцээнээ Монголын цагаар 6-н сарын 15-ны орой буюу энэ хагас сайн өдрийн орой 9-н цагаас 5-н цагийн хугацаатай 6-н бодлоготой зохиогдоно. Өөр улс, хотод байгаа хүмүүс ЭНД дарж цагаа тодруулна уу. Бодлогууд маш сонирхолтой бодлогууд байгаа. Бүгд идвэхтэй оролцоорой, ялангуяа энэ жил олон улсад явах 4-н сурагч заавал ороорой. Тэмцээн болох хаягийг 5дахь өдөр өгнөө, мэдээж хакерранк дээрээ хийнэ.
За тур баяртай.
UPDATE
POSTOO dahin unshina uu kk.
UPDATE
Тэмцээн дараах хаяган дээр болно.
https://www.hackerrank.com/kb3
Тэмцээнээ Монголын цагаар 6-н сарын 15-ны орой буюу энэ хагас сайн өдрийн орой 9-н цагаас 5-н цагийн хугацаатай 6-н бодлоготой зохиогдоно. Өөр улс, хотод байгаа хүмүүс ЭНД дарж цагаа тодруулна уу. Бодлогууд маш сонирхолтой бодлогууд байгаа. Бүгд идвэхтэй оролцоорой, ялангуяа энэ жил олон улсад явах 4-н сурагч заавал ороорой. Тэмцээн болох хаягийг 5дахь өдөр өгнөө, мэдээж хакерранк дээрээ хийнэ.
За тур баяртай.
UPDATE
POSTOO dahin unshina uu kk.
UPDATE
Тэмцээн дараах хаяган дээр болно.
https://www.hackerrank.com/kb3
Thursday, April 25, 2013
Тэмцээн KB-3, iOS хөгжүүлэгч бэлтгэж ажилд авах.
За сайн байцгаана уу.
5-н сарын сүүлээр КВ-3, Khongor and Baska, ээлжит тэмцээнээ зохиохоор болсон ба цаг өдөр хоногийг хэсэг хугацааны дараа бүр тодруулж бичнээ, www.hackerrank.com дээр тэмцээн болдогоороо болно. Энэ удаагийн тэмцээн дараах онцлогтой хийнэ. Миний хувьд би зун 7-н сард Монголруугаа тур хугацаагаар буцах ба зорилго маань iOS app хөгжүүлэгч нэгэн компанид ажилтан бэлтгэж өгөх, өөрөө мэдээж амрах юм.
iOS гэж юу вэ?
iOS нь та бидний сайн мэдэх Apple iPhone, iPad, iPod touch зэрэг бүтээгдэхүүнүүдийн үйлдлийн систем ба товчхоноор эдгээр төхөөрөмжүүд дээр аппликашн, тоглоом хөгжүүлдэг болох юм.
Надад одоогоор 3-4н хүн хэрэгтэй байгаа ба тэмцээнд оролцсон хүмүүсээс өөрсдөө хэрвээ хүсвэл надтай холбогдоод харилцаж шалгаруулалтанд оролцож болно. Хэрвээ сонгогдвол компаниас Macbook, шаардлагатай аккаунт, төхөөрөмжүүдээр хангаж мөн сургалтын явцад багахан цалин өгнө. Ерөнхийдөө энэ бэлтгэх явц маань 3-аас 4-н 7 хоног үргэжлээд, цаашаагаа шууд бүтээгдэхүүн гаргаад жинхэнээр ажиллаад явах юм. Гол нь энэ энгийн нэг СУРГАЛТ биш цаашдаа ажиллах хүн хайж байгаа шүү.
Миний хувийн бодлоор багаасаа математикаар яюсан эсвэл ядаж алгоритм, програмчлалын туршлагатай толгойгоо ажиллуулж сурсан хүнд шинэ хэл, онол сурахад асуудалгүй хурдан сурчих ёстой гэсэн бодолтой байдаг учраас сонирхсон хүмүүс санаа зоволтгүй надтай холбогдоорой.
Миний Е-мэйл хаяг baasanbatp@gmail.com, сонирхсон хүмүүс холбогдоод мөн цааш нь энэ зарыг түгээж өгнө үү.
Баярлалаа.
5-н сарын сүүлээр КВ-3, Khongor and Baska, ээлжит тэмцээнээ зохиохоор болсон ба цаг өдөр хоногийг хэсэг хугацааны дараа бүр тодруулж бичнээ, www.hackerrank.com дээр тэмцээн болдогоороо болно. Энэ удаагийн тэмцээн дараах онцлогтой хийнэ. Миний хувьд би зун 7-н сард Монголруугаа тур хугацаагаар буцах ба зорилго маань iOS app хөгжүүлэгч нэгэн компанид ажилтан бэлтгэж өгөх, өөрөө мэдээж амрах юм.
iOS гэж юу вэ?
iOS нь та бидний сайн мэдэх Apple iPhone, iPad, iPod touch зэрэг бүтээгдэхүүнүүдийн үйлдлийн систем ба товчхоноор эдгээр төхөөрөмжүүд дээр аппликашн, тоглоом хөгжүүлдэг болох юм.
Надад одоогоор 3-4н хүн хэрэгтэй байгаа ба тэмцээнд оролцсон хүмүүсээс өөрсдөө хэрвээ хүсвэл надтай холбогдоод харилцаж шалгаруулалтанд оролцож болно. Хэрвээ сонгогдвол компаниас Macbook, шаардлагатай аккаунт, төхөөрөмжүүдээр хангаж мөн сургалтын явцад багахан цалин өгнө. Ерөнхийдөө энэ бэлтгэх явц маань 3-аас 4-н 7 хоног үргэжлээд, цаашаагаа шууд бүтээгдэхүүн гаргаад жинхэнээр ажиллаад явах юм. Гол нь энэ энгийн нэг СУРГАЛТ биш цаашдаа ажиллах хүн хайж байгаа шүү.
Миний хувийн бодлоор багаасаа математикаар яюсан эсвэл ядаж алгоритм, програмчлалын туршлагатай толгойгоо ажиллуулж сурсан хүнд шинэ хэл, онол сурахад асуудалгүй хурдан сурчих ёстой гэсэн бодолтой байдаг учраас сонирхсон хүмүүс санаа зоволтгүй надтай холбогдоорой.
Миний Е-мэйл хаяг baasanbatp@gmail.com, сонирхсон хүмүүс холбогдоод мөн цааш нь энэ зарыг түгээж өгнө үү.
Баярлалаа.
Tuesday, April 9, 2013
MNPC2013
МУИС, Математик компъютерийн сургууль дээр 5 дахь удаагаа зохион байгуулагдсан Үндэсний програмчлалын тэмцээнд амжилттай орж эхний 3 байр эзэлсэн МУИС-МТС 1, МУИС-МТС 2, МУИС-МКС 1 багуудад баяр хүргэе.
Мөн HackerRank дээр зохиогдсон онлайн тэмцээнд амжилттай оролцсон нөхдөд баяр хүргэе ээ.
Энэ бодлогыг илүү хялбар бодож болох ба дараалсан цагаан хавтангуудын тоог тоолъё. ...##.#..## байвал 3 1 2 гэсэн үг. Эндээс манай бодлого Nim game -рүү шилжиж байгаа ба Nim game-д тоонуудын XOR нь 0 байвал 2-р тоглогч, бусад бүх тохиолдолд 1-р тоглогч ялдаг.
Миний хувьд иймэрхүү зүй тогтол харах тоглоомын бодлогуудтай нэлээд олон таарч байсан. Хамгийн сүүлийн Topcoder SRM дээр хүртэл энэ төрлийн бодлого байсан.
Динамик програмчлалаар бодъё. f(k)-р k урттай бодлогын нөхцлийг хангадаг аялалын тоог тэмдэглэвэл хариу f(m) байх нь ойлгомжтой.
N=20 үед боломжит нэгэн хариуг харъя.
1 2 4 8 16 1 11 1 2 4 8 20
Дээрх хариунаас харахад манай аялал нь бие биеэсээ үл хамаарах хэд хэдэн аялалаас тогтож байна. Ногоон нь аялалын эхлэл буюу дурын хот, улаан нь төгсгөл буюу том хот (улаан болон ногоон өнгө давхцаж болно). Улаан болон ногоон өнгө хоорондохыг дэд аялал гэж үзвэл дэд аялал хамгийн ихдээ log2(N)+1 урттай байна. Учир нь ямар нэгэн тооноос эхлээд дор хаяж хоёр дахин ихэснэ.
Буцаад динамик програмчлал руугаа оръё. Бид нар f(k)-г олохыг оролдож байгаа. Дарааллын k-р гишүүн улаан өнгөтэй байх нь илт (аялалын төгсгөл буюу том хот). Тэгвэл түүнд хамгийн ойр орших улаан өнгөтэй гишүүнийг j гэж үзье. Дээр дурдсанаар энэ хоёрын хоорондох зай хамгийн ихдээ log(N) байна. Тэгвэл f(j)-д байгаа бүх хариуны ард k-j урттай дэд аялалыг залгахад k урттай ялгаатай аялалууд үүснэ. Үүнийг томъёолвол f(k)=Sum(f(j)*[k-j урттай дэд аялалын тоо]) {j=k-logN .. k-1} болно. Хэрвээ бид дурын k урттай дэд аялалын тоог олж чаддаг бол бодлого маань ямар ч гэсэн шийдэгдлээ гэсэн үг. (Мэдээж 10^18 үед амжихгүй)
g(i,j)-р i урттай сүүлийн буюу i-р гишүүний утга нь j-с хэтэрдэггүй бөгөөд гишүүн бүр нь өмнөх гишүүнээсээ дор хаяж 2 дахин их байдаг тоон дарааллын тоог тэмдэглэвэл g(i,j)=g(i,j-1)+[i урттай сүүлийн гишүүний утга нь яг j байдаг тоон дарааллын тоо]. [] нд бичсэн утга нь g(i-1,j/2) той тэнцүү гэдгийг хялбархан харж болно. g(i,j)=g(i,j-1)+g(i-1,j/2) харьцагаар бид g-г O(logN*N)-д байгуулж чадна. g-г ашиглан k урттай дэд аялалын тоог g(k,N)-g(k,N/2) гэж олж болно.
Тэгвэл f(k)=Sum(f(j)*(g(k-j,N)-g(k-j,N/2)){j=k-logN .. k-1} болох ба g-г өмнө байгуулчихсан гэж үзвэл бид f(M)-г O(M*logN)-д олж чадах нь ээ :). M = 1018 үед яагаад ч амжихгүй :(.
N=10^5 үед f(k) нь хамгийн ихдээ өмнөх 20 гишүүнээсээ хамаарна. Тэгэхээр бид f(0) .. f(19) ашиглаад f(20)-г, f(1)..f(20) ашиглаад f(21)-г олж чадна гэсэн үг. Харьцаа нь шугаман учраас бид үүнийг матриц ашиглан бодож болно. [f(i),f(i+1),...,f(i+19)]*X=[f(i+1),f(i+2),...,f(i+20)] байдаг X матриц нь бүх i-н хувьд тогтмол байх учраас анхны буюу [f(0),f(1),...,f(19)] матрицыг X-н M-19 зэргээр үржүүлэхэд [f(M-19),f(M-18),...,f(M)] матриц үүсэх ба сүүлийн матрицын 20 дахь гишүүн нь бидний хайж буй хариу юм. Одоо бодлогын хугацааг үнэлвэл g матрицыг олон тестээс хамаарахгүйгээр нэг удаа O(NlogN)-д байгуулна. Матрицын хэмжээг тогтмол logN-р авснаас тогтмол 20-р авсан нь кодчилоход хялбар байна. Нэг тестийг O(20^3*logM)-д бодох ба эндээс нийт хугацаа нь O(NlogN + T*20^3*logM) болж хангалттай амжина.
Мөн HackerRank дээр зохиогдсон онлайн тэмцээнд амжилттай оролцсон нөхдөд баяр хүргэе ээ.
Нийлбэр олох
Эхний K гишүүний нийлбэрийг S гэж үзвэл дахиад нэг баруун тийш шилжихэд S+Ak-A0 болж өөрчлөгдөнө. Энэ мэтчилэн нийлбэрийг O(1)-д олж чадах учраас бодлого O(N)-д бодогдоно.Сансарын нисгэгч
Өгүүлбэр жаахан ойлгомжгүй байсан уу даа. Би бол 1-р гарагаас бусад гараг тус бүр рүү хүрэх зайг олоод тэр зай нь F-с хэтрэхгүй, бас радиустаа багтаж байна уу гэдгийг шалгасан.Тэгш өнцөгт
Бодлого нь i*j≤n ба i≤j байдаг хэдэн хос байгааг олохтой ижил. i болон j-н аль нэгээр давтаад нөгөөхийг нь тоолоод явахад болно (O(N)). Эсвэл хоёулангаар нь давтахад ч болно, энэ тохиолдолд хугацааны үнэлгээ O(NlogN) орчим байна.Тоглоом
Тоглоомын бодлого бодоход хүнд юм шиг боловч ерөнхий санааг нь олчихсон хойно энгийн Динамик програмчлалын бодлого байдаг. Хавтангуудын урт 20-с хэтрэхгүй учир нийт 2^20 ширхэг ялгаатай тоглоомын төлөв байж болно. Хар хавтанг 0, цагаан хавтанг 1 гэвэл 20 битийн тоогоор дүрслэж чадах ба үүнийгээ бид 10-тын тооллын системийн mask тоо гэж үзье. f(mask)-г уг төлөвт 1-р тоглогч эхлэж нүүхэд хождог бол 1 үгүй бол 0 гэж үзье. f(mask_1)=0 байдаг дор хаяж ганц mask_1 төлөв рүү mask-с хүрч чаддаг байвал f(mask)=1, тийм mask_1 төлөв олдохгүй бол f(mask)=0 байна. Ингээд манай бодлого энгийн Динамик програмчлалын бодлоготой ижилхэн.Энэ бодлогыг илүү хялбар бодож болох ба дараалсан цагаан хавтангуудын тоог тоолъё. ...##.#..## байвал 3 1 2 гэсэн үг. Эндээс манай бодлого Nim game -рүү шилжиж байгаа ба Nim game-д тоонуудын XOR нь 0 байвал 2-р тоглогч, бусад бүх тохиолдолд 1-р тоглогч ялдаг.
Шагай
Дээрх тоглоом бодлогод дурдсан үндсэн санаа буюу динамик програмчлал ашиглаад эхний нэлээд хэдэн (N,M) хосуудын утгыг харвал ямар нэгэн N тооны хувьд 2-р тоглогч хождог байх яг ганц M гэсэн хос олдох нь харагдана. Уг зүй тогтлоор аль тоглогч хожихыг хялбархан мэдэж болно.Миний хувьд иймэрхүү зүй тогтол харах тоглоомын бодлогуудтай нэлээд олон таарч байсан. Хамгийн сүүлийн Topcoder SRM дээр хүртэл энэ төрлийн бодлого байсан.
Дахиад л анхны тоо
Нэгжийн оронд 1, аравтын оронд 10 mod P, зуутын оронд 100 mod P, мянгатын оронд 1000 mod P гэх мэт хариу гарна.Урт дараалал
Динамик програмчлалын бодлого. Өсдөг буурдаг тохиодлоо тусад нь бодоход болно. f(x,y)-р аль нэг цэгээс эхлээд x,y цэг дээр дуусдаг хамгийн урт дарааллыг тэмдэглэвэл f(x,y) = MAX(1, MAX(f(x', y') + 1 {бүх хөрш x', y' хувьд})) байна.Хамгаалалт
Багана болон мөр тус бүрийн хувьд хөрш тэрэгнүүдийн хамгийн хол зайг олоод үржихэд хариу гарна. Захын нөхцлүүдийг бас шалгаарай.Аялагч
Тэмцээнд миний дэвшүүлсэн бодлого хэхэ.Динамик програмчлалаар бодъё. f(k)-р k урттай бодлогын нөхцлийг хангадаг аялалын тоог тэмдэглэвэл хариу f(m) байх нь ойлгомжтой.
N=20 үед боломжит нэгэн хариуг харъя.
1 2 4 8 16 1 11 1 2 4 8 20
Дээрх хариунаас харахад манай аялал нь бие биеэсээ үл хамаарах хэд хэдэн аялалаас тогтож байна. Ногоон нь аялалын эхлэл буюу дурын хот, улаан нь төгсгөл буюу том хот (улаан болон ногоон өнгө давхцаж болно). Улаан болон ногоон өнгө хоорондохыг дэд аялал гэж үзвэл дэд аялал хамгийн ихдээ log2(N)+1 урттай байна. Учир нь ямар нэгэн тооноос эхлээд дор хаяж хоёр дахин ихэснэ.
Буцаад динамик програмчлал руугаа оръё. Бид нар f(k)-г олохыг оролдож байгаа. Дарааллын k-р гишүүн улаан өнгөтэй байх нь илт (аялалын төгсгөл буюу том хот). Тэгвэл түүнд хамгийн ойр орших улаан өнгөтэй гишүүнийг j гэж үзье. Дээр дурдсанаар энэ хоёрын хоорондох зай хамгийн ихдээ log(N) байна. Тэгвэл f(j)-д байгаа бүх хариуны ард k-j урттай дэд аялалыг залгахад k урттай ялгаатай аялалууд үүснэ. Үүнийг томъёолвол f(k)=Sum(f(j)*[k-j урттай дэд аялалын тоо]) {j=k-logN .. k-1} болно. Хэрвээ бид дурын k урттай дэд аялалын тоог олж чаддаг бол бодлого маань ямар ч гэсэн шийдэгдлээ гэсэн үг. (Мэдээж 10^18 үед амжихгүй)
g(i,j)-р i урттай сүүлийн буюу i-р гишүүний утга нь j-с хэтэрдэггүй бөгөөд гишүүн бүр нь өмнөх гишүүнээсээ дор хаяж 2 дахин их байдаг тоон дарааллын тоог тэмдэглэвэл g(i,j)=g(i,j-1)+[i урттай сүүлийн гишүүний утга нь яг j байдаг тоон дарааллын тоо]. [] нд бичсэн утга нь g(i-1,j/2) той тэнцүү гэдгийг хялбархан харж болно. g(i,j)=g(i,j-1)+g(i-1,j/2) харьцагаар бид g-г O(logN*N)-д байгуулж чадна. g-г ашиглан k урттай дэд аялалын тоог g(k,N)-g(k,N/2) гэж олж болно.
Тэгвэл f(k)=Sum(f(j)*(g(k-j,N)-g(k-j,N/2)){j=k-logN .. k-1} болох ба g-г өмнө байгуулчихсан гэж үзвэл бид f(M)-г O(M*logN)-д олж чадах нь ээ :). M = 1018 үед яагаад ч амжихгүй :(.
N=10^5 үед f(k) нь хамгийн ихдээ өмнөх 20 гишүүнээсээ хамаарна. Тэгэхээр бид f(0) .. f(19) ашиглаад f(20)-г, f(1)..f(20) ашиглаад f(21)-г олж чадна гэсэн үг. Харьцаа нь шугаман учраас бид үүнийг матриц ашиглан бодож болно. [f(i),f(i+1),...,f(i+19)]*X=[f(i+1),f(i+2),...,f(i+20)] байдаг X матриц нь бүх i-н хувьд тогтмол байх учраас анхны буюу [f(0),f(1),...,f(19)] матрицыг X-н M-19 зэргээр үржүүлэхэд [f(M-19),f(M-18),...,f(M)] матриц үүсэх ба сүүлийн матрицын 20 дахь гишүүн нь бидний хайж буй хариу юм. Одоо бодлогын хугацааг үнэлвэл g матрицыг олон тестээс хамаарахгүйгээр нэг удаа O(NlogN)-д байгуулна. Матрицын хэмжээг тогтмол logN-р авснаас тогтмол 20-р авсан нь кодчилоход хялбар байна. Нэг тестийг O(20^3*logM)-д бодох ба эндээс нийт хугацаа нь O(NlogN + T*20^3*logM) болж хангалттай амжина.
Wednesday, March 27, 2013
KB2 Дүн болон Бодлогуудын Анализ
За юуны өмнө оролцсон бүх 33 оролцогчиддоо баярлалаа. Энэ удаагийн тэмцээн маань hackerrank.com дээр болсноороо онцлогтой байлаа. Бодлогуудын хувьд Хонгор 2 бодлого, 27 мөн Хачин Улс, Баасанбат миний бие Нэвтрэлт, Бэлэг, Хамгийн богино зам гэсэн 3-н бодлого тус тус оруулав.
Тэмцээний дүнг толилуулахад дараах байдалтай байна. Эхний гурван байранд орсон Хасан, 102662( хэн бэ?), Наранбаяр нарт баяр хүргэе. Нээрээ тоон нэртэй хүмүүс нэрээ мэдэгдвэл сайн байна шүү.
Дараа дараагийхаа тэмцээнийг мөн Хонгор бид 2 хамтарч ХакерРанк дээрээ хийнэ. Энэ жил Олон Улсын Мэдээлэл Зүйн Олимпиадад явна гэж бодож байгаа хүүхдүүд бэлтгэлээ сайн хийгээрэйдээ гэж хэлээд тус тусыхаа бодлогуудын анализыг сонирхуулъя.
Бэлэг
Хэрэв хөнгөлөлтийн карт байхгүй байсан бол бодолт хамгийн бага Z+U-г сонгох замаар бодогдоно. Хөнгөлөлтийн картыг ямар бэлгэндээр хэрэглэх вэ гэдэг нь асуудал. Нийт 1000-н бэлэг байгаа учираас хөнгөлөлтийн картыг бүх бэлэг дээр ашиглаж үзээд дээрх GREEDY санаагаар бусад бэлгээ сонгоод явж болно. Энэ бодолт O(N^2) учир хангалттай амжина. Дасгал болгох үүднээс энэ алгоритмаа цааш нь хөгжүүлээд O(N*logN) болгох асуудлыг уншигчид үлдээе.
Нэвтрэлт
Энэ бодлогыг бодох магадгүй хамгийн амархан бодолт Рекурс байх. Боломжит бүх илэрхийллүүдыг, замуудыг, шалгана. Рекурсын дуудалт болгон дээр нээлттэй хаалтуудын тоо '(', хаалттай хаалтуудын тоо ')' -г тоолоод явна. Гэхдээ Рекурс хийх дараалал нь хаалттай хаалт таарах л юм бол нээлттэй хаалтыг тоолж дуусаад хаалттай хаалтыг тоолж эхлэнэ. Ямар нэгэн зам шалгаж дуусна гэдэг маань хэрэв нээлттай хаалтны тоо, хаалттай хаалтны тоотой тэнцэх үед л дуусах юм. Өөр нэмж болох сайжруулалт нь нээлттэй хаалтнуудыг тоолцон байхад мэдээж үүсэж болох илэрхийллийн урт нь 2*(нээлттэй хаалтны тоо) байх ба энэ тоо маань бидний өмнө олсон хариунаас их байвал л бид шалгаж болох юм, эсрэг тохиолдолд угийн бага урттай илэрхийллийг байгаа эсэхийг шалгах нь илүү үйлдэл билээ.
Хамгийн богино зам
Энэ бодлого ойлгомжтой дурын бүх хоёр хотуудын хоорондахь богино замаас хамгийн уртыг нь олох байсан. Үүнийг графын Диаметр гэж нэрлэдэг ба мод биш бол үндсэн 2 алгоритм байгаа. Floyd Warshall O(N^3), мөн бүх хотуудаас Дижкстра хийх O(N^2*LogN). Сүүлийн алгоритм дээр Heap өгөгдлийн бүтэцийн тусламжтай хийдэг билээ. Энэ удаад уг нь 2 дахь алгоритмаар хийлгэх санаатай бодлогоо тавьсан боловч зарим Floyd бичсэн оролцогчидын бодолт давж байна лээ :), баяр хүргэе :).
Хачин улс
Ерөнхийдөө DFS хийгээд шалгаад явж болно. Гэхдээ илүү хялбар бодолт нь орой болгон руу яг нэг ирмэг чиглэсэн эсэхийг шалгах юм. Үүнийг хялбархан батлаж болно.
27
Энэ бодлого нь хялбархан динамик програмчлалын бодлого юм. N маань илүү том байж болох байсан ч 10^12 гэж өгсөн нь төөрөгдүүлэх бус олон төрлийн бодолт харахыг хүссэнд оршино. f(A,B,C)-р A оронтой, 27-д хуваагдахад B үлдэгдэл өгдөг, N-н эхний A оронгоос C зайтай хичнээн тоо байгааг тэмдэглэвэл манай бодлогын хариу SUM(f(length(N),0,C)) {c=0..K} байх болно.
Динамик програмчлалын бодлогууд дээр ямар нэгэн төлвийн утгыг олохдоо түүнээс ялгаатай өөр төлвүүдийн утгыг ашиглаж олдог (нийлбэр, ялгавар, min, max гэх мэт). Жишээ нь фибоначийн тоог олохдоо f(n) = f(n-1) + f(n-2) гэж олдог шүү дээ. Үүний оронд ямар нэгэн олдсон байгаа утга нь өөр ямар төлвүүдэд ашиглагдахаа мэдэж байгаа гэж үзээд f(n+2) += f(n); f(n+1) += f(n); гэж бичиж болно.
Уг бодлогыг бичихэд сүүлийн арга нь арай илүү тохиромжтой. Бид ямар нэгэн A, B, C-н хувьд f(A,B,C)-н утгыг мэдэж байгаа гэж үзээд уг төлөвт багтах тооны ард X цифрийг залгаж бичвэл дараагийн төлөв нь (A+1,(B*10+X)%27,C+|X-dA+1|) болно. Энэ хамаарлаас бид дараах кодыг бичиж чадна.
Тэмцээний дүнг толилуулахад дараах байдалтай байна. Эхний гурван байранд орсон Хасан, 102662( хэн бэ?), Наранбаяр нарт баяр хүргэе. Нээрээ тоон нэртэй хүмүүс нэрээ мэдэгдвэл сайн байна шүү.
Дараа дараагийхаа тэмцээнийг мөн Хонгор бид 2 хамтарч ХакерРанк дээрээ хийнэ. Энэ жил Олон Улсын Мэдээлэл Зүйн Олимпиадад явна гэж бодож байгаа хүүхдүүд бэлтгэлээ сайн хийгээрэйдээ гэж хэлээд тус тусыхаа бодлогуудын анализыг сонирхуулъя.
Бэлэг
Хэрэв хөнгөлөлтийн карт байхгүй байсан бол бодолт хамгийн бага Z+U-г сонгох замаар бодогдоно. Хөнгөлөлтийн картыг ямар бэлгэндээр хэрэглэх вэ гэдэг нь асуудал. Нийт 1000-н бэлэг байгаа учираас хөнгөлөлтийн картыг бүх бэлэг дээр ашиглаж үзээд дээрх GREEDY санаагаар бусад бэлгээ сонгоод явж болно. Энэ бодолт O(N^2) учир хангалттай амжина. Дасгал болгох үүднээс энэ алгоритмаа цааш нь хөгжүүлээд O(N*logN) болгох асуудлыг уншигчид үлдээе.
Нэвтрэлт
Энэ бодлогыг бодох магадгүй хамгийн амархан бодолт Рекурс байх. Боломжит бүх илэрхийллүүдыг, замуудыг, шалгана. Рекурсын дуудалт болгон дээр нээлттэй хаалтуудын тоо '(', хаалттай хаалтуудын тоо ')' -г тоолоод явна. Гэхдээ Рекурс хийх дараалал нь хаалттай хаалт таарах л юм бол нээлттэй хаалтыг тоолж дуусаад хаалттай хаалтыг тоолж эхлэнэ. Ямар нэгэн зам шалгаж дуусна гэдэг маань хэрэв нээлттай хаалтны тоо, хаалттай хаалтны тоотой тэнцэх үед л дуусах юм. Өөр нэмж болох сайжруулалт нь нээлттэй хаалтнуудыг тоолцон байхад мэдээж үүсэж болох илэрхийллийн урт нь 2*(нээлттэй хаалтны тоо) байх ба энэ тоо маань бидний өмнө олсон хариунаас их байвал л бид шалгаж болох юм, эсрэг тохиолдолд угийн бага урттай илэрхийллийг байгаа эсэхийг шалгах нь илүү үйлдэл билээ.
Хамгийн богино зам
Энэ бодлого ойлгомжтой дурын бүх хоёр хотуудын хоорондахь богино замаас хамгийн уртыг нь олох байсан. Үүнийг графын Диаметр гэж нэрлэдэг ба мод биш бол үндсэн 2 алгоритм байгаа. Floyd Warshall O(N^3), мөн бүх хотуудаас Дижкстра хийх O(N^2*LogN). Сүүлийн алгоритм дээр Heap өгөгдлийн бүтэцийн тусламжтай хийдэг билээ. Энэ удаад уг нь 2 дахь алгоритмаар хийлгэх санаатай бодлогоо тавьсан боловч зарим Floyd бичсэн оролцогчидын бодолт давж байна лээ :), баяр хүргэе :).
Хачин улс
Ерөнхийдөө DFS хийгээд шалгаад явж болно. Гэхдээ илүү хялбар бодолт нь орой болгон руу яг нэг ирмэг чиглэсэн эсэхийг шалгах юм. Үүнийг хялбархан батлаж болно.
27
Энэ бодлого нь хялбархан динамик програмчлалын бодлого юм. N маань илүү том байж болох байсан ч 10^12 гэж өгсөн нь төөрөгдүүлэх бус олон төрлийн бодолт харахыг хүссэнд оршино. f(A,B,C)-р A оронтой, 27-д хуваагдахад B үлдэгдэл өгдөг, N-н эхний A оронгоос C зайтай хичнээн тоо байгааг тэмдэглэвэл манай бодлогын хариу SUM(f(length(N),0,C)) {c=0..K} байх болно.
Динамик програмчлалын бодлогууд дээр ямар нэгэн төлвийн утгыг олохдоо түүнээс ялгаатай өөр төлвүүдийн утгыг ашиглаж олдог (нийлбэр, ялгавар, min, max гэх мэт). Жишээ нь фибоначийн тоог олохдоо f(n) = f(n-1) + f(n-2) гэж олдог шүү дээ. Үүний оронд ямар нэгэн олдсон байгаа утга нь өөр ямар төлвүүдэд ашиглагдахаа мэдэж байгаа гэж үзээд f(n+2) += f(n); f(n+1) += f(n); гэж бичиж болно.
Уг бодлогыг бичихэд сүүлийн арга нь арай илүү тохиромжтой. Бид ямар нэгэн A, B, C-н хувьд f(A,B,C)-н утгыг мэдэж байгаа гэж үзээд уг төлөвт багтах тооны ард X цифрийг залгаж бичвэл дараагийн төлөв нь (A+1,(B*10+X)%27,C+|X-dA+1|) болно. Энэ хамаарлаас бид дараах кодыг бичиж чадна.
long long dp[13][27][120];
int main() {
int T;
scanf("%d", &T);
while (T--) {
string s;
int k;
cin >> s >> k;
memset(dp, 0, sizeof(dp));
dp[0][0][0] = 1;
for (int a = 0; a < s.size(); a++)
for (int b = 0; b < 27; b++)
for (int c = 0; c <= k; c++) {
if (a == 1 && b == 0) continue;
for (int x = 0; x < 10; x++)
dp[a + 1][(b * 10 + x) % 27][c + ABS(x - (s[a] - '0'))] += dp[a][b][c];
}
long long res = 0;
for (int i = 0; i <= k; i++)
res += dp[s.size()][0][i];
cout << res << endl;
}
return 0;
}
Monday, March 25, 2013
Wednesday, February 20, 2013
Тэмцээн - March
Сайн байцгаана уу.
Монголын цагаар энэ 3-н сарын 24-ны бүтэн сайны өглөө 10-н цагаас ээлжит тэмцээнээ зохиохоор товлолоо. Энэ удаагийн тэмцээнийг Хонгортой хамтарч хийхээр болсон, санаачлага гаргасанд баярлалаа кк. Бодлогууд аль болох бүх төрлөөс оруулахыг бодно. Өөр хот улсад байгаа хүмүүс ЭНД дарж цагийг харна уу. Тэмцээн www.spoj.pl дээрээ болно, дөхүүлж байгаад тэмцээний талаар дахин дэлгэрэнгүй пост оруулнаа.
UPDATE::
Uuchlaarai, temtseeniig todorhoigui hugatsaagaar hoishluullaa. 4n sariin iheer hiinee, gehdee hiiheesee omno yadaj 7 honogiin omno zaraa tavinaa. Dahiad uuchlal husey.
Монголын цагаар энэ 3-н сарын 24-ны бүтэн сайны өглөө 10-н цагаас ээлжит тэмцээнээ зохиохоор товлолоо. Энэ удаагийн тэмцээнийг Хонгортой хамтарч хийхээр болсон, санаачлага гаргасанд баярлалаа кк. Бодлогууд аль болох бүх төрлөөс оруулахыг бодно. Өөр хот улсад байгаа хүмүүс ЭНД дарж цагийг харна уу. Тэмцээн www.spoj.pl дээрээ болно, дөхүүлж байгаад тэмцээний талаар дахин дэлгэрэнгүй пост оруулнаа.
UPDATE::
Uuchlaarai, temtseeniig todorhoigui hugatsaagaar hoishluullaa. 4n sariin iheer hiinee, gehdee hiiheesee omno yadaj 7 honogiin omno zaraa tavinaa. Dahiad uuchlal husey.
Subscribe to:
Comments (Atom)