Tuesday, May 1, 2012

Бидний гаргасан амжилтууд (Team SMCS1)

Саяхан Улсын програмчлалын 22-р олимпиад Монгол Улсын Их Сургуулийн Мэдээллийн Технологийн Сургууль дээр амжилттай явагдаж өнгөрснийг та бүхэн мэдэж байгаа байх. Энэ удаад гэхдээ үүнийг бичих гэсэнгүй. SMCS1 гэдэг баг 4 жил болж нэг бүтэн үе өнгөрч байгаа болохоор та бүхэнтэй дурсамжаа хуваалцая гэсэн юм.

2008-2009 он
Би энэ сургуульд 2008 онд 16 настайдаа элсэн орсон. Ингээд сургуульд ороод хамгийн анх танилцсан хүн бол Багаболд багш. Тухайн үед coder.mn дээр бодлого боддог байсан болохоор магадгүй багш минь намайг анзаарч харсан байх. Гэхдээ одоо бодоход тэр үед манай улсын түвшин хамаагүй доогуур байжээ :). Ингээд энэ хүн сургуулиасаа сонирхлоороо нэгдсэн оюутнуудыг цуглуулан манай анхны баг бүрдсэн юм. Ангийн найз болох Мөнх-Очир, мөн дээд курсын ах Хасан нар юм. Ингээд л бид 3-н хамтарсан бэлтгэл эхлэсэн юм. Тухайн үед coder.mn, spoj.pl/CSMS сайтууд хамгийн алдартай нь байлаа. Энэ сайтуудын тэмцээн уралдаан, бодлогыг чадах чинээгээрээ оролдож B@Ts, Irmuun ах нараасаа ч их юм сурсан даа. Мөн үүгээр зогсохгүй багшийнхаа зөвлөснөөр олон улсын бодлогын томоохон архив UVa сайт дээр эрчимтэй бэлтгэл хийж эхлэсэн юм. Тэр үед хичээл номоо ч анхааралгүй үнэхээр их боддог байсан, дэндүү дуртай байсан гэх юм уу даа. Бид бие рүү шөнө 2, 3 цаг гэхэд утасдаж сэрээгээд хамтдаа Yahoo Messenger дээр conference үүсгэж байгаад 5 цагийн тэмцээнд ороод өглөөнөө буцаад унтдаг байлаа :D.
Ингээд бэлтгэлийн үр дүнгээ шалгах хамгийн эхний тэмцээн нь Улсын програмчлалын 19-р олимпиад байсан юм. Уг олимпиадад санасныг бодвол тааруухан оролцсон. Би мөнгөн медал, Мөнх-Очир хүрэл медал авсан юм. Энэ жил бол миний хамгийн эхний азгүйтэл байсан :P, pascal хэлний санах ойгоос болж 1 бодлогоо 0-уулсан юм хэхэ. Багийн нийлбэр дүнгээр КТМС-н багтай тэнцэж медалийн чанараар КТМС түрүүлсэн.
Дараагийн тэмцээн нь үндэсний програмчлалын анхны олимпиад байлаа. Энэ олимпиад бүх хүнд цоо шинэ байсан, 3 хүн хамтдаа 1 компъютер дээр сууж боддог. Ингээд энэ тэмцээнд МТС-н багтай оноо тэнцэж хугацаагаараа ялагдан 2-р байранд орлоо. Гэхдээ намар Шанхай хотноо зохиогдох Азийн бүсийн тэмцээнд оролцох эрхээ авсан юм.

2009-2010 он
Ингээд 2009 оны намар Хасан, Мөнх-Очир бид 3 Багаболд багшийнхаа хамтаар Азийн бүсийн 34-р олимпиадад оролцохоор явсан. Бид Монгол улсаас анх удаа хүрэл медал хүртжээ. Энэ бол дөнгөж эхлэж байсан бидний хувьд гайхалтай амжилт байсан юм.
Ингээд дараагийн оюутны бүсийн програмчлалын олимпиадад явахад Хасан ах маань 4-р курс байсан тул дараагийн гишүүнээ сонгохоор болж Алмабек манай багийн гишүүн боллоо. Алмабек маань бидэнтэй 1-р курсээс л цуг явж, цуг бэлтгэл хийсэн их хөдөлмөрч байсан. Гэвч улсын олимпиадад Хасан ахынхаа хамтаар орох нь ойлгомжтой :).
Улсын програмчлалын 20-р олимпиадад Бид гайхалтай амжилт үзүүлж 1, 2-р байрыг хол тасархай эзлэсэн юм. Би алтан медаль, Хасан мөнгөн медаль (3-р байрнаас тасархай байсан санагдаж байна). Ингээд нийлбэр дүнгээр МКС маань түрүүлж шилжин явах цомыг хүртлээ.
Програмчлалын үндэсний 2-р олимпиадад Хонгор, Мөнх-Очир, Алмабек нарын бүрэлдэхүүнтэй SMCS1 баг маань илт давуу ялалт байгуулан 1-р байр эзэлж намар БНХАУ-н Тянжин хотноо зохиогдсон тэмцээнд оролцох эрхтэй болсон юм.

2010-2011 он
Мөн 2010 оны намар бид багшийнхаа хамтаар Азийн бүсийн 35-р олимпиадад оролцож өмнөх жилийн амжилтаа давтан хүрэл медалийн эзэд боллоо. Гэхдээ бидэнд энэ амжилт чамлалттай санагдсан юм.
Ингээд мөн л Алака маань 4-р курс болсон тул дараагийн гишүүнээ хайж Баскатайгаа нэгдсэн юм. Баска бид 2 coder.mn дээр цуг бодлого боддог их сургуульд орохоос ч өмнө бие биенээ таньдаг байсан.
Улсын програмчлалын 21-р олимпиадад Алмабектэй цуг орсон юм. Энэ олимпиадад манайх дундаж амжилт үзүүлэн Мөнх-Очир бид 2 мөнгөн медалийн эзэд болж МТС цомын эзэд болсон. Энэ олимпиад бас л асуудалтай болсон хэхэ, тэр тухай post хийж байсан. Гэхдээ тэр нь би түрүүлэх байсан гэсэн үг биш л дээ, Өсөхбаатарыг би хувьдаа их үнэлдэг.
Програмчалын үндэсний 3-р олимпиадад Хонгор, Мөнх-Очир, Баска нар орсон юм. Хамгийн гайхалтай нь Хасан ах маань нэгэнт сургуулиа төгсөж ажилд ороод уг олимпиадад комиссын гишүүн болж ажилласан юм :). Бид энэ тэмцээнд мөн л гайхалтай ялалт байгуулан Далианд оролцох эрх авсан.

2011-2012 он
Сая намар буюу 9 сард Баска, ЛМО бид 3 Азиийн бүсийн 36-р олимпиадад оролцож үнэхээр гайхалтай оролцон мөнгөн медалийн эзэд болсон юм. Одоогоор манай багаас өөр баг ямар нэгэн медал аваагүй байна :).
Ингээд Баска маань Америк сурахаар явж, Мөнх-Очир бид 2 төгсөх курс болсон учраас програмчлалын үндэсний 4-р олимпиадад оролцоогүй юм.
Улсын програмчлалын 22-р олимпиад саяхан болж өнгөрснийг та бүхэн мэдэж байгаа байх. Мөнх-Очирын маань хувьд эхний өдөр ялихгүй алдаа гаргаж хамаг оноого алдсан ч удаах өдөр нь гайхалтай оролцон 150 оноо авснаар мөнгөн медалийн эзэн болсон юм.
Харин миний хувьд эхний өдөр түрүүлсэн. Гэвч бас л нэгэн азгүйтэл ч юм уу нийлбэр дүнгээр мөнгөн медал авсан юм. Энэ жил түрүүлэхийг их хүсч байлаа, угаасаа цаанаасаа л болдоггүй юм болдоггүй юм шиг байна. Тэр өдөр миний гаргасан авирт зарим хүн дургүйцэж магадгүй, гэхдээ над шиг 2 удаа түрүүлчихээд 2-т орно гэдэг хэцүү л болов уу.

Ингээд гаргасан амжилтуудаа жагсааж бичвэл:

Э.Хонгор:
Програмчлалын үндэсний олимпиадын 2 алт, 1 мөнгөн медал.
Улсын програмчлалын олимпиадын 1 алт, 3 мөнгөн медал.
Азийн бүсийн олимпиадын 1 мөнгөн, 2 хүрэл медал.
ТопКодер-н 2011 оны нээлттэй тэмцээний шилдэг 350 оролцогчийн нэг.

Б.Хасан:
Програмчлалын үндэсний олимпиадын 1 мөнгөн медал.
Улсын програмчлалын олимпиадын 1 мөнгөн медал.
Азийн бүсийн олимпиадын 1 хүрэл медал.

Л.Мөнх-Очир:
Програмчлалын үндэсний олимпиадын 2 алт, 1 мөнгөн медал.
Улсын програмчлалын олимпиадын 2 мөнгө, 1 хүрэл медал.
Азийн бүсийн олимпиадын 1 мөнгө, 2 хүрэл медал.

Н.Алмабек:
Програмчлалын үндэсний олимпиадын 1 алтан медал.
Азийн бүсийн олимпиадын 1 хүрэл медал.

П.Баасанбат:
Програмчлалын үндэсний олимпиадын 1 алтан медал.
Азийн бүсийн олимпиадын 1 мөнгөн медал.

Одоо бид:
Б.Хасан, Л.Мөнх-Очир, Э.Хонгор нар Мобиком корпорацид програмистаар хамт ажиллаж байна.
Н.Алмабек GrapeCity компанид програмистаар ажиллаж байна.
П.Баасанбат Америкт суралцаж байна.


Ингээд харахад бид чамлахааргүй их амжилтыг гаргажээ. Энэ хүртэл надтай хамт байсан Хасан ахдаа, ЛМОдоо, Баскадаа, Алакадаа бүгдэнд нь баярлалаа. ХАмгийн их баярлалаа гэж хэлэх хүн маань Багаболд багш юм. Энэ хүн байгаагүй бол өдийд энэ их амжилт байхгүй байх байсан. МКС-н маань амжилтын буухиа тасрахгүй гэдэгт итгэж байна.

Friday, September 30, 2011

ACM ICPC Regional Dalian 2011

9 сарын 23-25ны хооронд БНХАУ-н Далиан хотноо ACM ICPC бүсийн тэмцээн амжилттай болж өнгөрлөө. Уг тэмцээнд Хонгор, Мөнх-Очир, Баасанбат нарын бүрэлдэхүүнтэй S.M.C.S баг Монгол улсаа (блогоо :P) төлөөлөн оролцоод ирлээ. Манай баг 2009 онд Монгол улсын анхны хүрэл медал, 2010 онд амжилтаа бататган дахин хүрэл медал хүртээд байсан билээ.

9.23:

Бид Бээжин хотоос 12 цаг галт тэргээр явсаар 9.23-ны өглөө Далиан хотод ирлээ. Ингээд тэндээсээ шууд бүртгэлдээ очиж тэмцээний билэгдэл болох футболкоо авцгаалаа. Уг өдрөө тэр хавиараа жаахан танилцсан байдалтай л өнгөрүүллээ.

9.24:

Энэ өдөр бол дасгал тэмцээний өдөр. Дасгал тэмцээний гол зорилго нь систем болон компьютер, эдитор гэх зүйлүүдтэйгээ танилцах зорилготой өдөр юм. Гэхдээ уг өдөр сайн орвол сэтгэл зүйн хувьд дээшлэх байх гэж бодож байлаа. Гэтэл санаснаас хамаагүй тааруу орлоо :(.

9.25:

Жинхэнэ тэмцээний өдөр. Өмнөх дасгал дээр сайн ороогүй учир жаахан эмээж байсан. За тэмцээн эхэллээ.
A-J хүртэл дугаарлагдсан 10 бодлого. Олон бодлогоо хувааж аваад уншиж байх хооронд эхний баг D бодлого дээр AC авлаа. Хамт уншихад үнэхээр хялбархан simulation төрлийн бодлого байсан. Кодоо бичээд submit хийлээ, хариу ирээгүй байхад буруу гэдгээ шууд мэдэв - freopen :). Тэнэг froepen-оо хаагаад явуултал мэдээж AC кк.
Дараагийн бодлогоо хайж байтал E бодлогыг бас л өөр баг AC авчихлаа. Жаахан бодсоны эцэст DP бодолтыг олов. Бичээд явуултал AC. Board хартал 16 хавьцаа явж байна, бөөн баяр .....
Хялбар бодлого хайж нэлээд л удлаа. Гэтэл I бодлогыг E-с ч олон хүн бодсон байх юм. Нэг л барьцгүй эвгүй бодлого байв. Тэгээд G бодлогыг уншихад болмоор санагдаад нэлээд хурдан санаа олохыг оролдсон, эцэст нь санаагаа ч оллоо. Гэхдээ бодлогууд хугацааны хязгаарлалтууд тодорхойгүй болохоор TLE авахаас айж байсан ч бичихээр шийдээд бичлээ. Жишээ тестүүдийг давж байна, өөрсдөө үүсгэсэн tricky тестүүдийг ч давж байна. Submit хийлээ, AC :).
Бодлого хайсаар, I дээр гацсаар. Гэтэл C бодлогыг 2 баг бодсон мөртлөө болмоор санагдаад бодоод бичлээ. Нэлээд удсаны эцэст submit хийхэд WA, бид нэг л юм орхиод байгаа бололтой.
Сүүлийн 1 цаг эхэллээ, 2 цаг зүгээр суучихлаа, байдал эвгүй болж эхэлж байна ккк. Одоо манай эцсийн боломж I гэдгийг мэдэж байсан. I бодлогыг бодоход манайд хэрэгтэй байсан ганц зүйл нь 1^4+2^4+..+n^4 -г O(1)-д олдог томъёо. квадрат зэрэг, куб зэргийг мэдэж байсан ч 4 зэргийг мэддэггүй шүү. Томъёог нь гаргах гэж үзээд ч чадсангүй. n<=10^8 байсан болохоор нэг удаа precomputation хийчихвэл O(1)-д олж чадна. Гэхдээ л memory-д багтсангүй, TLE ч авлаа. 8 минут үлджээ, эцсийн эцсийн эцсийн арга гээд үзлээ. 1..10^8 хүртэл бүх утга биш харин 0-р төгссөн тоонуудыг нь хадгалчихвал ямар ч тоог ихдээ O(10) үйлдэл хийгээд олж чадна. Энэ бодолтоо Submit хийгээд 295 дахь минутанд AC. Хэзээ ч бодлого бодоод ингэж их баярлаж байсангүй кк. Дүнгийн хурал: Манайх мөнгө эсвэл хүрэл медал авах нь ойлгомжтой байсан. Хүрэл медалуудыг дуудсаар, манайх дуудагдсангүй :). Мөнгөн медал дээр S.M.C.S багийг дуудлаа. Ингээд анхны мөнгөн медалыг МУИС-МКС-н S.M.C.S баг хүртлээ.



Friday, September 9, 2011

Тэмцээн - 1

Юуны өмнө тэмцээнд оролцсон хүмүүст баярлалаа. Бас эхний байруудад орсон idiot, tvvv, Adya 3т баяр хүргэе.
Одооноос кодер дээрх тэмцээнүүдийг Тэмцээн тэд гэж нэрлэнээ. хэхэ, гадны сайтуудыг л дагаж байнадаа. Тэмцээний цагийг бас иймэрхүү орой хийвэл яаж байна саналаа үлдээгэрэй. Бодлогуудын хувьд бас л гадны сайтуудаас бодсон бодлогуудаас ишлэж зохиосон, тэстүүдэд бас их цаг гаргаж TRICKY тэстүүд их оруулсан. Ингээд бодлогын анализ хийе.
Эргэлт
Энэ хамгийн амархан бодлого байсан байх. Мөрийн дагуу хэд эргэх баганы дагуу хэд эргэхийг бодож үзсэн бол хариу: min(n*2-2, m*2-1)
35
Мэдээж цөөн сав хэрэглэхийн тулд аль болох 5-н сав ашиглах хэрэгтэй. Хэрэв N тоо 5-д хуваагдахгүй бол ядаж нэг удаа 3-н сав ашиглаж ёстой.
Бага тоо
Шууд хүчээр тоог 1-ээр ихэсгээд бодлогын шаардлагыг хангах тоог гаргаж авж болно. Хэрэв саяас илүү удаа 1-ээр нэмэгдүүлэх үйлдэл хийсэн бол шийдгүй юм. Өөр нэгэн бодолт өгөгдсөн тоон оронгийн тоонуудыг бүх боломжоор сэлгэж бодлогын хариуг гаргаж болно. N<=999999 учир бид хамгийн ихдээ 6! үйлдэл хийгдэх юм.

Тэгш өнцөгт

Энэ бодлогын өгүүлбэрийг их буруу бичсэнүү, хүмүүс ойлгох гэж цагаа их алдсан байх. Энэ бодлого нь codeforces.com дээр бүх боломжийг шалгахаар бодож болохоор өгөгдсөн ба та эндээс харж болно. Харин би хязгаарлалтыг сая болгож бүх боломжийг шалгах боломжгүй болгосон юм. Миний бодолт бол динамик програмчлал ашиглах ба left[i]-ээр тухайн i-р тэгш өнцөгтийн зүүн талд орших түүнтэй хөрш бөгөөд дараалсан мөн өөрөөс нь бага буюу тэнцүү урттай тэгш өнцөгтийн тоог тэмдэглэнэ. Үүнтэй адилаар right[i]-ээр i-аар хайрцагны баруун талд орших түүнтэй хөрш бөгөөд дараалсан мөн өөрөөс нь бага буюу тэнцүү өндөртэй тэгш өнцөгтүүдийн тоог тэмдэглэв. Тэгвэл хариу max(left[i]+right[i]) (i=1..n). Бодолт O(N)

Тэгийн тоо

Факториалын сүүлийн 0-үүдийн тоог яаж олдог хүмүүс бол бодох л байсан бодлого. Бодлогын хариунд тооцогдож болох үржвэрийн тэгүүдийн тоо нь min(fac2, fac5) юм. Энд fac2, fac5 нь 2 болон 5ууд тус бүр хэдэн удаа үржвэрт байгааг илэрхийлнэ. Энэ нь бидэнд бодлогыхоо хариуг гаргаж авахад заавал бүх тоог үржүүлэхээс зайлсхийх боломжийг олгох юм. Одоо бодлогоо динамик програмчлал ашиглан хоёр өөр маршрут гаргаж авна. Нэг нь үржвэрт хамгийн бага 2 орсон, нөгөө нь мэдээж хамгийн бага 5 орсон. Тэгвэл хариу нь уг 2 маршрутын бага нь болно. Бодолтыг O(N^2)-аар шийднэ.

Mario on Box
Энэ бодлогыг одоохондоо бичихгүйгээр шийдлээ.

Monday, June 20, 2011

Модтой тоглоё 6

IOI2010-n 2dahi odoriin Traffic Congestion bodlogiig bodloo. tgj bgad nemelt tailbar hiinee. Source-g ni tavichii.
//Task: IOI2010_2_2
//by Dunno
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
static int N,P[1000000],S[1000000],D[1000000];
int n;
vector<int> v[1000000];
int prev[1000000];
int col[1000000];
int sum;
int *p;

int go(int x) {
int ans = p[x];
int m = 0;
for (int i = 0; i < (int) v[x].size(); i++) {
int u = v[x][i];
if (u == prev[x])
continue;
prev[u] = x;
int tmp = go(u);
m = max(m, tmp);
ans += tmp;
}
m = max(m, sum - ans);
col[x] = m;
return ans;
}

int LocateCentre(int n, int *p, int *s, int *d) {
::n = n;
::p = p;
sum = accumulate(p, p + n, 0);
for(int i=0; i<n; i++){
v[s[i]].push_back(d[i]);
v[d[i]].push_back(s[i]);
}

prev[0] = -1;
go(0);
int id = 0;
int best = col[0];
for (int i = 1; i < n; i++) {
if (col[i] < best) {
best = col[i];
id = i;
}
}

return id;
}
int main(){
int i;
freopen("grader.in","r",stdin);
freopen("grader.out","w",stdout);
scanf("%d",&N);
for (i=0;i<N;i++) scanf("%d",&P[i]);
for (i=0;i<N-1;i++) scanf("%d%d",&S[i],&D[i]);
int r = LocateCentre(N,P,S,D);
printf("%d\n",r);
return 0;
}

let me know about errors, if any

Thursday, April 28, 2011

Програмчлалын улсын 21-р олимпиадын бодлогууд

2-р өдрийн 1-р бодлого.

Гурвалжинг судлая

Хугацааны хязгаарлалт: 2 сек

Координатын эх О-цэгийн баруун талд (эерэг талд) ОХ-тэнхлэг дээр бүхэл координаттай С цэг тэмдэглэв. Ингэхэд О цэгээс с-зайтай, С-цэгээс а-зайтай эерэг хагас (ОХ-тэнхлэгээс дээш) хавтгайд орших цор ганц В-цэг олдоно. Үүний дараа та дараах 2 даалгаварыг гүйцэтгэ.

1-рт нь:
ОВ-хэрчим дээр С1, С2, ... , Ск гэсэн ялгаатай цэгүүдийг ОС1, ОС2, ... , ОСк хэрчмүүдийн урт бүхэл тоо байхаар тэмдэглэв. Дараа нь мөн ОС-хэрчим дээр В1, В2, ... , Вm гэсэн ялгаатай цэгүүдийг OB1, OB2, ... , OBm хэрчмүүдийн урт бүхэл тоо байхаар тэмдэглэв. Эцэст нь BC хэрчим дээр A1, A2, ... , An гэсэн ялгаатай цэгүүдийг BA1, BA2, ... , BAn хэрчмүүдийн урт бүхэл тоо байхаар тэмдэглэв.

1-р даалгавар:
CCi, OAj, BBt хэрчмүүд нэг цэгт огтлолцдог байх бүх (i,j,t) гурвалуудыг ол. (1 <= i <= k, 1 <= j <= n, 1 <= t <= m)

2-рт нь:
1-р даалгавраа гүйцэтгэсний дараа, О-цэгээс зүүн талд (сөрөг талд) ОХ-тэнхлэг дээр D1, D2, ... , Dp гэсэн ялгаатай цэгүүдийг OD1, OD2, ... , ODp хэрчмийн урт бүхэл байхаар авав.

2-р даалгавар:
Ci, Aj, Dt цэгүүд нэг шулуун дээр оршдог байх бүх (i,j,t) гурвалуудыг ол. (1 <= i <= k, 1 <= j <= n, 1 <= t <= p)

Оролт (tr.in)
Оролтын файл 10 мөрөөс тогтоно.
Эхний мөрөнд С цэгийн координат болох "b" гэсэн 10000-аас хэтрэхгүй натурал тоо байна.
2-р мөрөнд B-цэгийг олоход хэрэглэх "c" ба "a" гэсэн 2 натурал тоо хоосон зайгаар тусгаарлагдан өгөгдөнө.
Эдгээр тоонууд мөн 10000-аас хэтрэхгүй. (2 < a,b,c <= 10000)
3-р мөрөнд k-гэсэн натурал тоо байна. (k <= 150)
Дараагийн мөрөнд OC1, OC2, ... , OCk хэрчмүүдийн уртыг илэрхийлэх c1, c2, ... , ck гэсэн ялгаатай натурал тоонууд хоосон зайгаар тусгаарлагдан байрлана. (ci < c, i=1..k)
5-р мөрөнд m гэсэн натурал тоо байна. (m <= 150)
Дараагийн мөрөнд OB1, OB2, ... , OBm хэрчмүүдийн уртыг илэрхийлэх b1, b2, ... , bm гэсэн ялгаатай натурал тоонууд хоосон зайгаар тусгаарлагдан байрлана. (bi < b, i=1..m)
7-р мөрөнд n гэсэн натурал тоо байна. (n <= 150)
Дараагийн мөрөнд BA1, BA2, ... , BAn хэрчмүүдийн уртыг илэрхийлэх a1, a2, ... , an гэсэн ялгаатай натурал тоонууд хоосон зайгаар тусгаарлагдан байрлана. (ai < a, i=1..n)
9-р мөрөнд p-гэсэн натурал тоо байна. (p <= 150)
Эцсийн мөрөнд OD1, OD2, ... , ODp хэрчмүүдийн уртыг илэрхийлэх d1, d2, ... , dp гэсэн 10000-аас хэтрэхгүй ялгаатай натурал тоонууд хоосон зайгаар тусгаарлагдан байрлана.

Гаралт (tr.out)
Мөр бүрт 1-р даалгаврын хариу болох (i, j, t) гурвалуудыг илэрхийлэх i, j, t гэсэн 3 тоо хоосон зайгаар тусгаарлагдан байрлана. Тус гурвалуудыг хэвлэхдээ i-гийн координатаар өсөхөөр эрэмбэлж гаргана, хэрэв i-нь тэнцүү бол i-координатаар нь өсөхөөр эрэмбэлж гаргана. Жишээ нь: (1,3,2) (2,2,3) (2,3,1) гэсэн дарааллаар хэвлэнэ.
1-р даалгаврын бүх хариуг хэвлэж дууссаны дараа "PART 2" гэсэн тэмдэгт мөр хэвлэнэ. (1-р даалгавар нэг ч хариугүй байсан ч PART 2 гэж хэвлэнэ)
Үүний араас мөр бүрт 2-р даалгаварын хариу болох (i,j,t) гурвалуудыг илэрхийлэх i,j,t гэсэн 3 тоо хоосон зайгаар тусгаарлагдан байрлана. Тус гурвалуудаа хэвлэх дараалал нь өмнөхтэй адил байна.

Жишээ оролт
8
10 12
2
1 5
3
1 5 4
2
7 6
3
2 4 1000

Жишээ гаралт
2 2 3
PART 2

Тайлбар
CC2 = 5, OA2 = 6, BB3 = 4 хэрчмүүд нэг цэгт огтлолцох тул 2 2 3 гэж гаргана.
Ci, Aj, Dt цэгүүд дунд нэг шулуун дээр орших гурвал олдохгүй байна.

Tuesday, April 26, 2011

Улсын програмчлалын 21-р олимпиадын дүн

Өнгөрсөн амралтын өдрүүдээр буюу 4 сарын 23-24 өдрүүдэд Улсын Програмчлалын 21-р олимпиад КТМС дээр зохиогдож дүнгээ гаргалаа. Ингээд нийлбэр дүнгээр

1. Өсөхбаатар МУИС-МТС - 240
2. Хонгор МУИС-МКС - 210
3. Мөнх-Очир МУИС-МКС - 200
4. Чинбат КТМС - 195
5. Амар КТМС - 185
6. Амгаланбаатар КТМС - 185

Багийн дүнгээр МУИС-МТС 1-р баг түрүүлж шилжин явах цомын эзэд боллоо. Амжилттай оролцсон хүмүүстээ баяр хүргэе!

Monday, April 25, 2011

Програмчлалын Улсын 21-р олимпиадын алдаа

Энэ удаад олимпиадын дүнг танилцуулахаас өмнө алдаануудыг бичихээр шийдлээ.

Эхний өдөр:
Ороод суухад лабораторын компьютерийн бэлтгэл ажил муу байсан. Жишээлбэл анх ороод суухад Deep Freeze програмыг унтраагаагүй байсан, үүнийг мэдэж байсан туршлагатай оюутнууд л хаалгасан. Эндээс үүдэж гарсан хамгийн муу үр дүн нь Дархан хотоос зорьж ирсэн Мөнхбаатарын эхний өдрийн бүх Source устсан. Бид бодолтоо тулгасан ба Мөнхбаатар дор хаяж 130 оноо авах байсан. Энэ бол КтМС-н цэвэр хариуцлагагүй байдал.
Ингээд эхний өдрийн дүн гарахад миний оноо 145 байсан ба 150 авна гэдэгтээ маш итгэлтэй байсан. Өргөдөл бичиж ороод би өөрөө тестийн алдааг олж илрүүлээд комисс хүлээн зөвшөөрч 4 хүүхэд 5 оноо нэмж авсан. Ороогүй байсан бол тэмцээний дүнд том өөрчлөлт орох байсан.

Хоёр дах өдөр:
Мөнхбаатарын бодолтыг сэргээж чадсангүй, ингээд тэдний хариуцлагагүй байдлаас болж бүхэл бүтэн 130 оноо алдаж байр эзлэх ямар ч найдваргүй болсон. Дүн гарлаа, уг нь дор хаяж 100 оноо авна гэсэн итгэлтэй байсан би 40 15 5 оноо авсан байв. 40 оноог бол би хүлээн зөвшөөрнө, 15-г ойлгож болно, 5 оноог огт ойлгосонгүй. Тэд өргөдөл хүлээн авах боломж өгөлгүй хүчээр бүх өргөмжлөлүүдийг бэлдээд бараг хүчээр дүнгийн хурал эхлүүлэв. 15 оноо авсан бодлого тест хэтэрхий сул байснаас Brute Force буюу хамгийн арга барсан аргаар бодсон хүмүүс 50 авч гайхал төрүүлэв.

Тэмцээний дараа Мөнх-Очир бид 2 миний 5 авсан буюу "tr" бодлогын бодолтыг зөв гэдэгт итгэлтэй байсан тул тестүүдийг аваад шалгаж үзтэл ихэнх тест бодлогын нөхцлийг хангаагүй буюу Гурвалжны тэнцэтгэл биш хангахааргүй өгөгдсөн байв. Мэдээж гурвалжин үүсэхгүй бол ямар хариу хэвлэх вэ дээ? Гэтэл зохиогч болон Өсөхбаатар-н бодолтууд хаанаас ч юм хариу олж хэвлээд тэдгээр нь таарсан. Би гурвалжны тэнцэтгэл биш нөхцлийг хангахгүй бол юу ч хэвлэхгүй гэдгийг кодондоо бичсэн. Энэ бодлогоны тест буруу байсан нь хамгийн том алдаа, хэрвээ энэ алдаа байгаагүй бол Би 1-рт байрт орж багаараа дахин цом хүртэх байлаа. Тэд өргөдөл хүлээж авах ёстой байсан, хэрэв хүлээж авсан бол би тэр алдааг дорхноо илрүүлж бүгдийг өөрчлөх байсан.

Бүх юм дууссан болохоор дараа жилийнхдээ л сайн бэлдэе дээ :)

Гэхдээ бид ижилхэн л оролцогчид учраас Өсөхбаатарт баяр хүргэе!

Wednesday, April 13, 2011

MNPC 2011 - SMCS багийн тэмдэглэл

Би (SMCS - Э.Хонгор) энд багийнхаа MNPC 2011-т хэрхэн оролцсон тухай бичихээр шийдлээ. Юуны өмнө MNPC 2011 нь Мөнх-Очир бид хоёрын хувьд оролцох боломжтой сүүлийн жил байсан болохоор амжилттай оролцохыг хүсч байсан ба санасандаа хүртэл оролцсондоо таатай байна. Мөн багийн уламжлал ёсоор дахин нэг гишүүн маань солигдсон билээ :p. Багийн шинэ гишүүн маань уг блог-н идэвхтэй админ болох Баасанбат юм. Тэмцээний үеэр олон бодлого байсан болохоор хэн яг ямар бодлого оролдож уншсаныг мартчихаж, багийн ажиллагаа байсан гэж ойлгоорой :).

За ингээд тэмцээнээ эхэлье :). Тэмцээн эхлэв 10 бодлого ирлээ. Бодлогыг хувааж аваад уншив аа, тэгтэл J бодлого N тооны эрэмбээрээ голын тоог ол гэнэ. Шууд STL-н sort ашиглаж бичээд явуултал TLE. N<=10^6 бас multicase 10 ширхэг байсан болохоор амжсангүй. Ингээд шууд хаяад A бодлогыг хартал өгөгдсөн тоонуудын нийлбэрийг ол гэнэ. Ингээд явуулаад 6 дахь минутанд AC. Тэгтэл манайхаас өмнө 2 баг AC авсан байв, J-г хэрэггүй оролдлоо :p. C бодлого N-с хэтрэхгүй хуваарьтай бүх зөв энгийн бутархайг эрэмбэлж гаргах бодлого байв, N жижигхэн байсан болохоор шууд бичээд AC (11 минут). Ингээд тэмцээний дүнг хартал маш бага хугацааны зөрүүгээр нэгт орлоо. Амархан бодлого олохын тулд бүх бодлогыг уншиж их цаг авав, тэгээд I бодлогыг уншиж дуусахад жаахан нуугдмал Bipartite Matching байсныг олоод шууд бичээд AC (41 минут). Дүнгээ хартал бас л тэнцчихсэн, хугацаагаараа арай бага болохоор 1т. Board-с ажиглаад B бодлого хялбар байж магадгүй санагдаад B-г Мөнх-Очиртой цуг жаахан бодсоны эцэст шууд томъёог олоод AC авав (64 минут). Дараагийн бодлого - F, уг бодлого өгүүлбэрээ ойлгосны дараа жижигсэн DP байсныг олов, бичиж байх зуураа дүн хартал дахиад л тэнцчихлээ, MTC-н 1-р багтай үнэхээр ширүүн өрсөлдөж байна даа, ингээд F-ээ дуусгаад AC(75 минут). Ингээд 5 бодлоготой болоод 1 оноогоор холдсон ч удалгүй өрсөлдөгч баг маань 5 бодлоготой болж тэнцэв. Бодлогуудаа уншсаар л, амархан бодогдчих бодлого олдолгүй удав. E бодлого MIS 2D(Maximum Interval Sum) -г олох бодлого, Мөнх-Очиртой хамтраад бичиж байтал арай жаахан удаж магадгүй санагдаад дуусгалгүй өөр бодлого харав. Тэгээд Баасанбатын уншиж байсан H-г DP + BFS гэдгийг харлаа. Маш урт өгүүлбэртэй бодлого байсан болохоор Баска-н тусламжтай хурдан ойлгоод бичив. Bug гарсан болохоор гурвуулаа нийлж тестлэж засаад явуулав. Алдаж магадгүй гэсэн айдастай байсан ч AC авлаа (154 минут). Яг энэ үед манайх 7 оноотой өрсөлдөгч 5 оноотой байсан болохоор жаахан тайвширлаа. Юмаа идэх нь идээд усаа уух нь уугаад бие засах нь заслаа. Ороод иртэл нөгөө баг 6 болчихжээ, яарахгүй бол болохгүй нь. Одоо бодох дутуу гурван бодлого нь D, G, J. J бодлогыг яг баталгаатай бодох арга олоогүй ч эцсийн арга гээд нэг арга олчихсон. D бодлогыг анх хараад ямар ч санаа олсонгүй. Brute Force бичээд жижиг тохиолдлоос зүй тогтлыг олов. Гурвуулаа нийлж байгаад томъёо гаргаад явуултал WA. Итгэлгүй байсан болохоор орхив. Тэмцээний дүнд өөрчлөлт ороогүй байсан болохоор өрсөлдөгч баг манайхыг ялахын тулд дор хаяж 2 бодлого нэмж бодох ёстой ба цаг бага үлдсэн байсан болохоор тайван байлаа, гэхдээ хамаагүй тайвширч болохгүйгээ мэдэж байсан болохоор J-г эцсийн аргаараа үзээд AC авав (228 минут). Одоо л тайвширч болохоор боллоо, гэхдээ D-г эцсээ хүртэл оролдсоор байв. Ингээд манай баг дахин түрүүлж хошой аварга боллоо. Бодлогын анализ дээр зохиогч D-н бодолтоо тайлбарлатал томъёо нь яг таарж байсан ба бодолтоо тулгатал маш жижигхэн алдаа байсан ба манай бодолт зөв болж rejudge хийхэд AC авав (208 минут). Ингээд 9 оноотой гэсэн үг, гэхдээ бусад багуудын аль нь ч бодож чадаагүй болохоор ялгаагүй гэж үзээд манай баг 8 оноотой үлдэхээр шийдсэн.

Бодлого Оролдлого Минут
A 1 6
C 1 11
I 1 41
B 1 64
F 1 75
H 1 154
E 1 170
D 1 203
J 6 228

Багийнхандаа баяр хүргэе!

P.S: Удахгүй бүх бодлогын өгүүлбэрийг оруулах болно.

Монголын Үндэсний Програмчлалын III Олимпиад

Монголын их дээд сургуулуудын оюутнуудын багуудын хооронд зохион байгуулагддаг Үндэсний Програмчлалын олимпиад 4.9-нд гурав дахь удаагаа амжилттай болж өндөрлөлөө. Тэмцээний дүнгээс дурдвал

1. МУИС - МКС 1-р баг - 8 оноо
Бүрэлдэхүүн : Хонгор, Мөнх-Очир, Баасанбат
2. МУИС - МТС 1-р баг - 6 оноо
Бүрэлдэхүүн : Өсөхбаатар, Жамсрандорж, Мөнхжаргал
3. МУИС - МТС 2-р баг - 6 оноо
Бүрэлдэхүүн : Хуягбаатар, Чинболд, Дөлгөөн
4. ШУТИС - КТМС 1-р баг - 4 оноо
Бүрэлдэхүүн : Амар, Адъяа, Гансүх
5. МУИС - МКС 2-р баг - 4 оноо
Бүрэлдэхүүн : Ганбат, Гончигдорж, Дөлгөөн
6. ШУТИС - КТМС 2-р баг - 4 оноо
Бүрэлдэхүүн : Баярмагнай, Чинбат, ?

Thursday, February 24, 2011

Чигчийхэн ба Чимэд ах

Тавил:
Online-Judge системд оролтын өгөгдлүүд тэст бүр дээр ижилхэн 1 байхад, гаралтын өгөгдлүүдийг тэст бүр дээр ялгаатай буюу 1-ээс N (тэстүүдийн тоо, N < 9) хүртэлх тоонууд байхаар хэвлэ. Цааш унших