Долдугаар сарын тэмцээн (coder.mn)

Энэ удаагийн тэмцээн нь шагналтай байснаараа онцлог байв. Нэлээд их оролдсоны эцэст ямар ч байсан бүх бодлогыг бодож чадлаа. Миний хувьд хүндээс нь эрэмбэлвэл Будалт, Зам, Гурвалжин тоолох, Фибоначийн эхлэл, Дундаж тоо, Дуртай цифр байх болно. Ингээд өөрийн бодолтуудаас хуваалцъя.

Дуртай цифр

Шууд буюу удаан бодолт нь 1..N хүртэл тоог 2-тын тооллын системд задлаад 1 битийг тоолох.
#include
using namespace std;
int main(){
int n,res=0;
scanf("%d",&n);
for (int i=1;i<=n;i++) res+=__builtin_popcount(i); printf("%d\n",res); return 0; }
Хурдан бодолт. 1..N тоог 2-тын тооллын системд задлаад доош цувуулан бичсэн гэж ?зээд K-р баганад байгаа 1 битийг тоолох.

#include
using namespace std;
int main()
{
int res=0,n;
scanf("%d",&n);
n++;
for (int k=1;k<=n;k*=2){ res+=n/(k*2)*k; int x=n%(k*2); if (x>k) res+=x-k;
}
printf("%d\n",res);
return 0;
}

Дундаж тоо

Оролтын тоонуудыг өсөхөөр эрэмбэлье. Одоо i-р тоог дундаж тоо болох эсэхийг шалгая, өөрөөр хэлбэл a(x)+a(y)=2*a(i) байх x,y олдох эсэх. Хэрэв a(i)=a(i-1) бол i-р тоо дундаж тоо мөн, эсрэг тохиолдолд x <= i ба i < y байх x,y-г хайх хэрэгтэй. Үүний тулд x,y-г ойртуулах аргаар олъё.
int x=1,y=n; // hamgiin baga boloh ih index
while(x<=i&&i<y){ if (a[x]+a[y]==2*a[i]) { /* i-r too dundaj too mon*/ } else if (a[x]+a[y]<2*a[i]) x++; else y--; }
Фибоначийн эхлэл

Эхлээд аливаа тооны эхний 9 цифрийг яаж олохыг сонирхъё. L=log10(N) гэе. floor(L)+1 нь N-н оронгийн тоог заана. Тэгэхээр хэрвээ өгөгдсөн тоог 10^(floor(L)+1) -д хуваавал тооны эхний цифр нь яг таслалын ард ирнэ. Гарсан тоог 10^9-р үржвэл эхний 9 орон нь таслалын өмнө ирэх ба уг тоог floor хийхэд бидний хариу гарна. Тэгэхээр N/10^(floor(L)+1)*10^9 буюу N*10^(8-floor(L))ба N=10^L гэдгийг орлуулвал 10^(L-floor(L)+8) болж хялбарчлагдна. Харин үндсэн бодлогын хувьд уг санааг хэрэгжүүлэхийн хувьд L=log10(Fib(N)) олох хэрэгтэй. Fib(n)~(phi^n)/sqrt(5) (phi=1.61...) байдгийг санавал L=n*log10(phi)-log10(sqrt(5)) болж өмнөх томъёонд орлуулан хариуг олох боломжтой. Нарийвчлалын алдаанаас болгоомжил.

Зам

Манай бодлого өгөгдсөн графыг холбоост эсэхийг шалгах бодлого биш юм. Учир нь хоёр оройн хувьд аль нэг зам нь байж болно гэсэн учраас. Ямар нэгэн u оройн хувьд бүх u,v хос дээрх нөхцлийг хангахын тулд u-с хүрч болдог, u-руу хүрдэг бүх оройн нэгдэл нь нийт оройтой тэнцүү байх явдал юм. u-с хүрч болдог бүх оройг нэг удаа DFS эсвэл BFS ашиглан олж болно. Харин u-рүү хүрдэг оройг олохын тулд өгөгдсөн графаас яг эсрэг чиглэлтэй ирмэгүүдээс тогтох граф дээр u-с DFS эсвэл BFS хийн олж болно. Ингээд бүх u оройн хувьд биелж байвал bolno үгүй бол bolokhgui юм. Гэвч энэ бодолт муу тохиолдолд O(E*V) учир амжихгүй. Сайжруулахын тулд өгөгдсөн графын бүх SCC (Strongly Connected Component)-г Tarjan-н алгоритм ашиглан олъя. Ижил SCC-д агуулагдах бүх хос орой бодлогын нөхцлийг хангана. Иймд хоёр өөр SCC-д агуулагддаг хос оройнуудын хувьд бодлогыг бодох хэрэгтэй. SCC-р оройгоо хийсэн шинэ граф байгуулъя. 2 SCC-г ямар үед холбогдсон гэж үзэх вэ? Анхны граф-д уг 2 SCC-н ядаж нэг орой хоорондоо холбогдсон бол энэ 2 SCC-г холбогдсон гэж үзнэ. Одоо шинэ граф дээр анхны бодлогыг бодох нь ижилхэн. Гэвч ямар ашигтай вэ? Шинэ граф хамгийн муу тохиолдолд ахны графтай ижилхэн тооны оройтой байж болно. Хамгийн чухал сайжруулалт нь уг граф циклгүй, чиглэлгүй граф юм. Иймд V удаа DFS хийхийн оронд динамик програмчлал ашиглан бүх оройн хувьд өөрөөс нь хүрч болдог, өөр рүү нь хүрдэг оройн тоог O(E) хугацаанд олж болно. Энэ алгоритмыг зөв бичсэн бол хугацаа O(E) байх ёстой учраас хангалттай амжина.

Будалт

Эхлээд жижигхэн бодолт хийгээд зүй тогтлыг олж чадсан. Сонирхолтой байлгах үүднээс бичилгүй үлдээе.

Гурвалжин тоолох

Ямар нэг оройг бэхлэж аваад уг орой дээр тэгш өнцөг нь байх хичнээн гурвалжин байхыг олъё. Уг оройг C гэж үзвэл ABC гурвалжин тэгш өнцөгт гурвалжин байхын тулд AC,BC векторын скаляр үржвэр 0 байх ёстой. Иймээс AC вектортой тэгш өнцөг үүсгэх BC векторыг O(logN)-д олж чадсанаар анхны бодлогыг O(N^2logN) хугацаанд бодож чадна.