A. Boshliqlik Syndromi 

Bu masalada birinchi topishimiz kerak bo'lgan narsa, qanday holatda bo'yashning imkoni yo'q, ya'ni "IMPOSSIBLE". 

Javob: Har qanday holatda bo'yashning imkoni bor. 

Isbotlash uchun har doim shartlarni qanoatlantiradigan qilib bo'yash usulini keltirishimiz mumkin: Bizga berilgan maydonni shaxmat doskasi kabi oq va qora kataklarga ajratib chiqaylik. Shunda oq katakka faqat 'A' yoki 'B' ni joylashtiramiz, qora katakka 'C' yoki 'D'ni. Shu yo'sinda biz hech qaysi yonma-yon kataklar bir xil rangga bo'yalmasligini ta'minlasak bo'ladi. 

Oq katakka qaysi harfni tanlaymiz: Agar ranglar jadvalida shu katakda 'A' turgan bo'lsa biz 'B' ga bo'yaymiz, aks holda 'A' ga.

Qora katakka bo'yash ham xuddi shu yo'l bilan amalga oshiriladi.

Vaqt murakkabligi: \(O(nm)\)

Python

n, m = map(int,input().split())

ans = ["" for i in range(n)]

for i in range(n):
    s = input()
    for j in range(m):
        if (i + j) % 2:
            if s[j] == 'A':
                ans[i] += 'B'
            else:
                ans[i] += 'A'
        else:
            if s[j] == 'C':
                ans[i] += 'D'
            else:
                ans[i] += 'C'

print("\n".join(ans))

B. Passportlar 

Oddiy \(O(n^2)\) yechim: har bir shahardan dfs algoritmi chaqiriladi va maximum ishlatilgan yo'l topilib, javobga qo'shib ketiladi.

Bu yechimni optimizatsiya qilishimiz kerak. Buning uchun bizga DSU (Disjoint Set Union) strukturasi yordam beradi. 

Birinchi bo'lib shaharlardagi barcha yo'llarni yo'q deb tasavvur qilamiz. Har bir yo'lni uzunligi bo'yicha kamaymaslik tartibida saralab, ulab ketamiz.  DSU bizga har bir ulangan shaharlar to'plamidagi shaharlarning sonini topishda yordam beradi. 

Endi biz yo'lni ulayotganda u yo'l eng uzuni hisoblangan juftliklar sonini topaylik. \(sz[a]\) -  \(a\) shaharning to'plamidagi shaharlar sonini saqlab tursin. Shunda uzunligi  \(w\) ga teng bo'lgan\(u\) va \(v\) shahar o'rtasidagi yo'lni ulayotganimizda bizga kerakli juftliklar soni \(sz[u]*sz[v]\)ga teng. Umumiy javobimizga esa \(sz[u]*sz[v]*w\) ni qo'shib ketamiz.

Vaqt murakkabligi, tartiblash bo'lganligi uchun, \(O(n\log n)\)

Python

n = int(input())

parent = [i for i in range(n + 1)]
sz = [1 for i in range(n + 1)]

def find_set(i):
    if i == parent[i]:
        return i
    parent[i] = find_set(parent[i])
    return parent[i]

edges = []

for i in range(n - 1):
    a, b, w = map(int,input().split())
    edges.append([w, a, b])

edges.sort()
ans = 0
for [w, a, b] in edges:
    a = find_set(a)
    b = find_set(b)
    ans += sz[a] * sz[b] * w
    parent[b] = a
    sz[a] += sz[b]

print(ans)

C. Renessansdagi birinchi kun 

Bu masalada ichimlikning gazli va gazsiz ekanligining ahamiyati yo'q. Umumiy ichimlik turlari soni \((n + m)\) ta. \((n + m)\) ta ichimlikdan esa \((n+m)^2\) xil usulda 2 ta ichimlik tanlab olishimiz mumkin.

Vaqt murakkabligi: \(O(1)\)

Python

n, m = map(int,input().split())
print((n + m) ** 2)

D. AYOQSH

Faqatgina bir turdagi (Ibr) AYOQSH ning eng yaqin filialini topish quyidagicha bo'ladi: 

mn_A = min(D % A, A - (D % A))

Endi boshqa turdagi AYOQSH lar uchun ham xuddi shunday topib chiqamiz, va ulardan eng yaqin masofasini chiqarib, eng yaqinlari bir nechta bo'lsa "Istaganingizni tanlashingiz mumkin!" yozuvini chop etamiz.

Vaqt murakkabligi, har bir test uchun: \(O(1)\)

Python

t = int(input())
for i in range(t):
	A, B, C, D = map(int,input().split())

	mn_A = min(D % A, A - (D % A))
	mn_B = min(D % B, B - (D % B))
	mn_C = min(D % C, C - (D % C))

	mn = min(mn_A, mn_B, mn_C)
	cnt = 0
	for x in [mn_A, mn_B, mn_C]:
		if x == mn:
			cnt += 1
	if cnt > 1:
		print(mn, "Istaganingizni tanlashingiz mumkin!")
	else:
	 	print(mn)

E. Nurlar Soni 

Bu masalada \(1\) va \(n\) oralig'ida bo'lgan barcha \((i, j)\) juftliklardan \(EKUB(i,j) = 1\) bo'lganlar sonini topishimiz kerak. Umumiylikni yo'qotmagan holda, biz quyidagi juftliklar sonini sanasak bo'ladi:

hamma butun \(i, j\) \((1 <= i < j <= n)\) uchun \(EKUB(i, j) = 1\) lar sonini \(cnt\) deb belgilaylik. Shunda bizning javob \(cnt * 2 + 3\) ga teng. Chunki agar \(EKUB(i, j) = 1\) bo'lsa \(EKUB(j, i) = 1\) bo'ladi. Shuning uchun sanoq \(1\) ga oshiriladi. Qolgan \(3\) ta holat esa \((0, 1)\), \((1, 0)\) va \((1, 1)\) nuqtalarga yo'naltirilgan o'qlar.

Shunda biz har bir \(j\) uchun undan kichik, o'zaro tub bo'lgan sonlarning nechtaligini topishimiz kerak. Buni tez hisoblash uchun Euler's totient function

dan foydalansak bo'ladi. Uni tez hisoblash usulini havoladan o'rganib olishingiz mumkin.

Har bir \(j\) uchun \(phi(j)\) ni hisoblashga \(sqrt(j)\) vaqt ketad. Shunda umumiy vaqt murakkabligi: \(O(n \sqrt n)\)

Python

def phi(n):
  start = n
  i = 2
  while i * i <= n:
    if n % i == 0:
      while n % i == 0:
        n //= i
      start -= start // i
    i += 1
    
  if n > 1:
    start -= start // n
  return start

n = int(input())
ans = 0
for i in range(2, n + 1):
  ans += phi(i)
print(ans * 2 + 3)