lab
https://youtu.be/qSLhdqIpyts?si=UkLig_CY92ITNgm9
باز خداروشکر ما تنها دلقک هایی نیستیم که از این محتواها میزاریم یوتیوب
ولی روتین ساختن برا تایمی که دانشگاه میری خیلی ساده تره. چیزایی وجود داره که مجبوری خودت و درگیرش کنی و اگه یکم خل باشی میتونی ازش لذت ببری. در مقابلش وقتی قراره کل وقتتو خودت پر کنی کار سخت تر میشه. حس پوچی میاد سراغت و حس میکنی داری زندگیتو تباه میکنی. ولی بحث فقط دانشگاه نیست (میدونم یه عده ازش متنفرن) درکل وقتی تسکی وجود داره که باید انجامش بدی و تکلیفت مشخصه خیلی احساس بهتری داری تا وقتی که همه چیز نامشخصه
👍12
اینکه میگن پایتون کامیونیتی بزرگ و فعالی داره واقعن اینطوریه.
یک انجمنی رسمی تو زیر دامنه خود python.org هست که توش کلی چیزای مختلف از جمله پیشنهاد برای ایده های جدید، بحث های توسعه دهنده های خود پایتون و یا سوال های فنی رو میشه دید.
https://discuss.python.org/
خیلی میتونه مفید باشه و چیز میز جدید یادتون بده.
یک انجمنی رسمی تو زیر دامنه خود python.org هست که توش کلی چیزای مختلف از جمله پیشنهاد برای ایده های جدید، بحث های توسعه دهنده های خود پایتون و یا سوال های فنی رو میشه دید.
https://discuss.python.org/
خیلی میتونه مفید باشه و چیز میز جدید یادتون بده.
یچیزی که سر حل کردن مسئله ها گاهی وقتا میرفتم رومخم این بود که اگه داخل حلقه تکرار تغیری رو متغیر حلقه اعمال کنیم رفتار حلقه عوض میشه یا نه؟ چون خیلی وقتا این حرکتو زدم ولی هیچوقت نرفتم چک کنم ببینم چه اتفاقی میفته. جالبه که داخل پایتون و سی پلاس پلاس رفتار ها متفاوته. داخل پایتون متغیر حلقه موقتی مقدارش عوض میشه و روی رفتار حلقه تاثیری نمیزاره ولی داخل سی پلاس پلاس دقیقن برعکس. اینشکلی که: خروجی این
با این
فرق داره.
for i in range(10):
i += 1
print(i)
با این
// Includes
#include <bits/stdc++.h>
using namespace std;
// Main function
int main() {
for (int i = 0; i < 10; i++) {
i++;
cout << i << '\n';
}
return 0;
}
فرق داره.
تو بعضی مسائل الگوریتمی، مخصوصاً جاهایی که با حالتهای مختلف و انتخابهای ممکن سر و کار داریم، یه تابع هست که خیلی پرکاربرده به اسم MEX.
mex یعنی Minimum EXcluded
یعنی کوچکترین عدد غیرمنفی که توی مجموعه نیست.
تابع mex از صفر شروع میکنه و میگرده دنبال اولین عددی که تو مجموعه نیست. همون رو برمیگردونه.
تو پایتون میشه اینجوری نوشت:
فرض کن یه بازی داریم با این قانون:
> یه بازیکن تو نوبتش میتونه از یه عدد n فقط 1 یا 2 واحد کم کنه. کسی که نتونه بازی کنه، میبازه.
حالا میخوایم با استفاده از mex تشخیص بدیم کدوم وضعیتها برد هستن و کدوم باخت.
خروجی چیزی مثل این میشه:
به کمک mex تونستیم با یک کد ساده وضعیت هر حالت رو مشخص کنیم. و با استفاده از lru_cache کاری کردیم که بار محاسباتی زیاد نشه و مقدارها ذخیره شن.
mex یعنی Minimum EXcluded
یعنی کوچکترین عدد غیرمنفی که توی مجموعه نیست.
s = {0, 1, 2, 4}
# عدد 3 توی مجموعه نیست، پس:
# mex(s) = 3تابع mex از صفر شروع میکنه و میگرده دنبال اولین عددی که تو مجموعه نیست. همون رو برمیگردونه.
تو پایتون میشه اینجوری نوشت:
def mex(s):
i = 0
while i in s:
i += 1
return i
فرض کن یه بازی داریم با این قانون:
> یه بازیکن تو نوبتش میتونه از یه عدد n فقط 1 یا 2 واحد کم کنه. کسی که نتونه بازی کنه، میبازه.
حالا میخوایم با استفاده از mex تشخیص بدیم کدوم وضعیتها برد هستن و کدوم باخت.
from functools import lru_cache
def mex(s):
i = 0
while i in s:
i += 1
return i
@lru_cache(maxsize=None)
def win_state(n):
if n == 0:
return 0
s = set()
for move in [1, 2]:
if n - move >= 0:
s.add(win_state(n - move))
return mex(s)
for i in range(10):
print(f"n = {i} → state = {win_state(i)}")
خروجی چیزی مثل این میشه:
n = 0 → 0 (بازنده)
n = 1 → 1 (برنده)
n = 2 → 2 (برنده)
n = 3 → 0 (بازنده)
n = 4 → 1 (برنده)
...
به کمک mex تونستیم با یک کد ساده وضعیت هر حالت رو مشخص کنیم. و با استفاده از lru_cache کاری کردیم که بار محاسباتی زیاد نشه و مقدارها ذخیره شن.
🔥1
Forwarded from AMIRHOSΣIN
این lru دقیقا توی حافظه cache نمیره، یه map درست میکنه که اون جا ذخیره میکنه ، توی تابع هایی که تعداد بازگشتشون کم هست کاربردی هست ، مثلا تا ۵۰۰ تا بازگشت ولی بیشتر بشه مثلا ۱۰۰۰۰۰ باید استک تابع بازگشتی را دستکاری کنی تا بزاره بزرگتر بگیری ، بعد تازه این جا نمیتونی کدت را با pypy اجرا کنی باید با python اجرا کنی بعد تازه این دستکاری استک خودش باعث مموری لیمیت میشه
حافظه cache توی کامپیوتر محدود هست یه چیزی حدود ۲۰ مگ و با حدود ۵۰۰۰ تا تابع بازگشتی این مقدار پر میشه به خاطره این lru توی ram ذخیره میکنه و این که خودت پیاده سازی کنی خیلی وقت ها بهینه تر میشه
البته ما توی پایتون به دلیل hash کردن مقدار ها برای اعداد بزرگ احتمال این که توی set یا dict برای اعداد بزرگ collision اتفاق میافته و زمان پیدا کردن از o(1) به o(n) میرسه
به خاطره همین توی بعضی از تست کیس ها این قدر اعداد تکراری میدن که این شکلی نمیتونی ازشون استفاده کنی
حافظه cache توی کامپیوتر محدود هست یه چیزی حدود ۲۰ مگ و با حدود ۵۰۰۰ تا تابع بازگشتی این مقدار پر میشه به خاطره این lru توی ram ذخیره میکنه و این که خودت پیاده سازی کنی خیلی وقت ها بهینه تر میشه
البته ما توی پایتون به دلیل hash کردن مقدار ها برای اعداد بزرگ احتمال این که توی set یا dict برای اعداد بزرگ collision اتفاق میافته و زمان پیدا کردن از o(1) به o(n) میرسه
به خاطره همین توی بعضی از تست کیس ها این قدر اعداد تکراری میدن که این شکلی نمیتونی ازشون استفاده کنی
lab
این lru دقیقا توی حافظه cache نمیره، یه map درست میکنه که اون جا ذخیره میکنه ، توی تابع هایی که تعداد بازگشتشون کم هست کاربردی هست ، مثلا تا ۵۰۰ تا بازگشت ولی بیشتر بشه مثلا ۱۰۰۰۰۰ باید استک تابع بازگشتی را دستکاری کنی تا بزاره بزرگتر بگیری ، بعد تازه این…
البته که منظور از cache اون حافظه که بین رم و سی پی یو قرار گرفته نیست. فقط یک اصطلاحه که نتایج ذخیره میشه و همون کاره memoization انجام میشه.
👌1
Forwarded from Fight Club
این سواله , سوال جالبی بود داشتم حلش میکردم
هر دفعه که تلاش میکردم حلش کنم به مشکل میخوردم و این هم به خاطره ساختار زبان پایتون بوده
یه تابع dfs داشتم توش که هر دفعه فقط دو بار خودش را فراخوانی میکرد , یکم بهینش کردم که فقط 1 بار خودش را فراخوانی کنه
و میشه گفته که به صورت خطی بود در حد O(n)
اما یه مشکلی وجود داشت این بود که تابع های بازگشتی توی پایتون نهایتا 998 بار میتونه به صورت بازگشتی خودش را فراخوانه و اگر بیشتر بشه stack overflow میکنه
خوب به صورت دستی با دستور
استک مورد نیاز برای حل این سوال را بهش دادم
اما یه مشکلی بازم وجود داشت , دیگه نمیشد از pypy استفاده کنم
حالا باید از python 3.10 استفاده میکردم که سرعتش فوق العاده از pypy کمتره و با خطای time limit مواجه میشد
خوب حالا گیر افتاده بودیم بین اوور فلو کردن استک و از یه طرف هم با تایم لیمیت برخورد میکردم
به ذهنم رسید که Stack تابع بازگشتی را که توی سیستم عامل ایجاد میشه را خودم پیاده سازی کنم
و از pypy استفاده کنم که سرعت بیشتری داره
این کار را کردم و جواب داد
هر دفعه که تلاش میکردم حلش کنم به مشکل میخوردم و این هم به خاطره ساختار زبان پایتون بوده
یه تابع dfs داشتم توش که هر دفعه فقط دو بار خودش را فراخوانی میکرد , یکم بهینش کردم که فقط 1 بار خودش را فراخوانی کنه
و میشه گفته که به صورت خطی بود در حد O(n)
اما یه مشکلی وجود داشت این بود که تابع های بازگشتی توی پایتون نهایتا 998 بار میتونه به صورت بازگشتی خودش را فراخوانه و اگر بیشتر بشه stack overflow میکنه
خوب به صورت دستی با دستور
sys.setrecursionlimit(10**5)
استک مورد نیاز برای حل این سوال را بهش دادم
اما یه مشکلی بازم وجود داشت , دیگه نمیشد از pypy استفاده کنم
حالا باید از python 3.10 استفاده میکردم که سرعتش فوق العاده از pypy کمتره و با خطای time limit مواجه میشد
خوب حالا گیر افتاده بودیم بین اوور فلو کردن استک و از یه طرف هم با تایم لیمیت برخورد میکردم
به ذهنم رسید که Stack تابع بازگشتی را که توی سیستم عامل ایجاد میشه را خودم پیاده سازی کنم
و از pypy استفاده کنم که سرعت بیشتری داره
این کار را کردم و جواب داد
Forwarded from Fight Club
from collections import deque , Counter
from math import ceil, floor, log2 , sqrt ,lcm
import sys
from itertools import combinations ,permutations
import bisect
mapINT = lambda: map(int, sys.stdin.readline().strip().split())
INT = lambda: int(sys.stdin.readline().strip())
LIST = lambda : list(mapINT())
# sys.setrecursionlimit(10**5)
line = []
visit = set()
n, m = mapINT()
graph = [[] for _ in range(n+1)]
def dfs(start):
global line, graph, visit
stack = [start]
while stack:
node = stack.pop()
if len(graph[node]) == 2:
a = graph[node][1]
if a not in visit and len(graph[a]) == 2:
visit.add(a)
line.append(a)
stack.append(a)
continue
a = graph[node][0]
if a not in visit and len(graph[a]) == 2:
visit.add(a)
line.append(a)
stack.append(a)
def solve():
global graph
for _ in range(m):
v, u = mapINT()
graph[v].append(u)
graph[u].append(v)
for i in range(n+1):
if len(graph[i])!=2:
graph[i] = []
else:
graph[i] = sorted(graph[i])
cnt= 0
ans =set()
for i in range(n+1):
line.clear()
if (len(graph[i])==2 and i not in visit):
line.append(i)
visit.add(i)
dfs(i)
if len(line)>2:
if line[-1] in graph[line[0]]:
cnt+=1
print(cnt)
t = 1
# t = INT()
for i in range(t):solve()
اینم کد پایتونش
🔥3