GeOlymp

GeOlymp ფორუმი

თემიდან: TCO 2012

წერილები: 83

tsotne says:

11 მაისი 2012, 12:47

ანუ ჩვენ ვერ მივიღებთ მონაწილეობას ხო? ის პარალელური რაუნდი ჩვენთვის არ იქნება როგორც მივხვდი...

თემიდან: Feedback

წერილები: 83

tsotne says:

11 მაისი 2012, 12:18

მეორე გვერდზე როცა გადადის, მერე უმნიშვნელო "პრობლემები" ჩნდება. ნუ უბრალოდ მოუხერხებელია. მაგალითად: როცა თემაში შედიხარ, არ გაქვს საშუალება პირველის გარდა სხვა გვერდზე შეხვიდე გარედან. ანუ ჯერ პირველ გვერდზე შედიხარ და მერე გადადიხარ სხვა გვერდებზე. როცა პოსტს აქვეყნებ, გადაყავხარ თემის პირველ გვერდზე, არადა როგორც წესი ბოლო გვერდი უნდა გიჩვენოს, სადაც დაპოსტე ის ადგილი. სხვა გვერდზე ჩამოსასვლელად აუცილებელია საიტის ბოლოში ჩახვიდე და იქიდან გადართო. კარგი იქნება თუ გვერდების შესაცვლელი თავშიც დაემატება.

კიდევ ერთი: ჩასწორების დროს არ გვაქვს არანაირი ღილაკები (სურათის, ლინკის, კოდის, ლატექსის ჩასმის და ა.შ.)

თემიდან: TCO 2012

წერილები: 83

tsotne says:

11 მაისი 2012, 12:14

ხვალ არის TCO Algorithm Round 2B. მაინტერესებს შეგვიძლია თუ არა მონაწილეობა მივიღოთ იმათ, ვინც არ ვარ გადასული არ რაუნდში. და თუ შესაძლებელია, მაშინ მაინტერესებს ქულებზე თუ აისახება.

თემიდან: Interviewstreet

წერილები: 83

tsotne says:

11 მაისი 2012, 12:09

ვიცოდი მაგ საიტის არსებობა მაგრამ არ შევსულვარ არასდროს :) ახლა Quora Classifier-ს ვაკეთებ, მაგრამ 0 ქულას მიწერს რომ ვაგზავნი :შ :დ

თემიდან: ხარისხების ჯამების დათვლა

წერილები: 83

tsotne says:

10 მაისი 2012, 0:04

უფრო მეტსაც დავწერ თუ საჭირო გახდა, მაგრამ ეჭვი მეპარება ესეც ვინმემ რომ წაიკითხოს :)

თემიდან: GeOlymp 2010-2011 Episodes

წერილები: 83

tsotne says:

8 მაისი 2012, 19:47

ჰო რა თქმა უნდა სწორი ხარ, ეგრეა. არ აღვნიშნე უბრალოდ. მეტიც, 1000000009-ის მაგივრად სხვა მარტივი რიცხვებისთვისაა ეს მხოლოდ სწორი. არამარტივებისთვის არ მუშაობს.

თემიდან: ფორმულის მიღება

წერილები: 83

tsotne says:

8 მაისი 2012, 16:20

@scientist1642
ზურა, აი გაინტერესებდა და ეს თემა შეამოწმე, დაგაინტერესებს ალბათ ;)

თემიდან: ხარისხების ჯამების დათვლა

წერილები: 83

tsotne says:

8 მაისი 2012, 14:23

ამ თემის შექმნა შთამაგონა ზურა ისაკაძის (@scientist1642) თემამ. ძალიან ბევრი ასეთი ჯამების დათვლა საბოლოოდ დადის შემდეგი ფორმულის სწრაფად დათვლაზე:
$f(n,k)=1^k+2^k+...+n^k$
მე პირადად არ გამომიყენებია k>3 შემთხვევებში ფორმულა, თუმცა ამ თემაში ვისაუბრებ თუ როგორ შეიძლება ამ ფორმულების მიღება. პროგრამულად, ნებისმიერი f(n,1), f(n,2), ... , f(n,k)-სთვის პრეკალკულაციას ჭირდება O(k^3) დრო და O(k^2) მეხსიერება, და შემდეგ f(n,k) ითვლება O(k) დროში. თუმცა, უბრალოდ საინტერესოა, სუფთა თეორიაში, ქაღალდზე, როგორ გამოვიყვანოთ ეს ფორმულები. ცნობისათვის,
$f(n,1)=\frac{n*(n+1)}{2}$
$f(n,2)=\frac{n*(n+1)*(2n+1)}{6}$
$f(n,3)=(\frac{n*(n+1)}{2})^2$
(სხვათა შორის, შეამჩნევდით, რომ f(n,3)=f(n,1)^2. ძალიან საინტერესო ტოლობაა, სკოლის ასაკში შეიძლება შეგხვედრიათ და ამოგიხსნიათ კიდეც).

მაშ ასე, დავიწყოთ დამტკიცება! მოდით განვიხილოთ რისი ტოლია $n^k-(n-1)^k$ .

$n^k-(n-1)^k=n^{k-1}+n^{k-2}*(n-1)+n^{k-3}*(n-1)^2+...+n*(n-1)^{k-2}+(n-1)^{k-1}=\sum_{i=0}^{k-1} (n^{k-1-i}*(n-1)^i)=\sum_{i=0}^{k-1} (n^{k-1}-C_{i}^{1}*n^{k-2}+C_{i}^{2}*n^{k-3}-...+(-1)^i*n^{k-1-i})=k*n^{k-1}-(C_{1}^{1}+C_{2}^1+...+C_{k-1}^{1})*n^{k-2}+(C_{2}^{2}+C{3}^{2}+...+C_{k-1}^2)*n^{k-3}-...+(-1)^{k-1}=\sum_{i=0}^{k-1}((-1)^i*(C_i^i+C_{i+1}^i+...+C_{k-1}^i)*n^{k-1-i})$

ახლა გამოვიყენებთ ფორმულას
$C_i^i+C_{i+1}^i+...+C_{k-1}^i=C_k^{i+1}$
და მივიღებთ, რომ
$n^k-(n-1)^k=\sum_{i=0}^{k-1}((-1)^i*C_k^{i+1}*n^{k-1-i})$

ეს ყველაფერი კაია, მაგრამ გაგიჩნდებათ კითხვა, აქედან სასარგებლოს რას ვღებულობთ ჩვენი ამოცანისთვის :D

მოდით დავითვალოთ რისი ტოლია n^(k+1).

$n^{k+1}=(n^{k+1}-(n-1)^{k+1})+((n-1)^{k+1}-(n-2)^{k+1})+...+(1^{k+1}-0^{k+1})=\sum_{i=0}^{k}((-1)^i*C_{k+1}^{i+1}*n^{k-i})+\sum_{i=0}^{k}((-1)^i*C_{k+1}^{i+1}*(n-1)^{k-i})+...+\sum_{i=0}^{k}((-1)^i*C_{k+1}^{i+1}*1^{k-i})=\sum_{i=0}^{k}((-1)^i*C_{k+1}^{i+1}*(n^{k-i}+(n-1)^{k-i}+...+1^{k-i}))=\sum_{i=0}^{k}((-1)^i*C_{k+1}^{i+1}*f(n,k-i))=(k+1)*f(n,k)+\sum_{i=1}^{k}((-1)^i*C_{k+1}^{i+1}*f(n,k-i))$

ახლა გამოვთვალოთ f(n,k).

რადგანაც
$n^{k+1}=(k+1)*f(n,k)+\sum_{i=1}^{k}((-1)^i*C_{k+1}^{i+1}*f(n,k-i))$
ამიტომ

$f(n,k)=\frac{n^{k+1}-\sum_{i=1}^{k}((-1)^i*C_{k+1}^{i+1}*f(n,k-i))}{k+1}$

შევნიშნოთ, რომ განტოლების მარჯვენა მხარეს ყოველი f(n,x) ფუნქციაში, x<k. მეტიც, ჩვენ ვიყენებთ მხოლოდ f(n,1), f(n,2), f(n,3), ... , f(n,k-1). ამიტომ დავიწყოთ იქიდან, რომ f(n,0)=1^0+2^0+...+n^0=n. და k-ს ზრდის მიხედვით ავყვეთ. მივიღებთ ფუნქციას ყველა k-სთვის :)

ვისაც ეს ფორმულა ურჩხული გგონიათ, ძალიან ცდებით. მოდით გამოვიანგარიშოთ f(n,1), f(n,2), f(n,3). საინტერესო იქნება f(n,4)-ის მნიშვნელობის გამოთვლა, რომელიც მეც არ ვიცი ჯერჯერობით, თუმცა დაპოსტვის შემდეგ მეცოდინება :)

$f(n,1)=\frac{n^{2}-\sum_{i=1}^{1}((-1)^i*C_{2}^{i+1}*f(n,1-i))}{2}=\frac{n^{2}+C_{2}^{2}*f(n,0))}{2}=\frac{n^{2}+n}{2}=\frac{n*(n+1)}{2}$

$f(n,2)=\frac{n^{3}-\sum_{i=1}^{2}((-1)^i*C_{3}^{i+1}*f(n,2-i))}{3}=\frac{n^{3}+C_3^2*f(n,1)-C_3^3*f(n,0)}{3}=\frac{n^{3}+3*\frac{n^2+n}{2}-n}{3}=\frac{2*n^{3}+3*n^2+3*n-2*n}{6}=\frac{n*(2*n^{2}+3*n+1)}{6}=\frac{n(n+1)(2n+1)}{6}$

$f(n,3)=\frac{n^{4}-\sum_{i=1}^{3}((-1)^i*C_{4}^{i+1}*f(n,3-i))}{4}=\frac{n^{4}+C_4^2*f(n,2)-C_4^3*f(n,1)+C_4^4*f(n,0)}{4}=\frac{n^{4}+6*\frac{n(n+1)(2n+1)}{6}-4*\frac{n*(n+1)}{2}+n}{4}=\frac{n^{4}+n(n+1)(2n+1)-2n(n+1)+n}{4}=\frac{n(n^3+(n+1)(2n+1)-2(n+1)+1)}{4}=\frac{n(n+1)((n^2-n+1)+(2n+1)-2)}{4}=\frac{n(n+1)*n(n+1)}{4}=(\frac{n(n+1)}{2})^2$

საინტერესოა რა იქნება f(n,4)-ის ფორმულა :)

აჰა! ვიწვალე და გამოვთვალე :)

$f(n,4)=\frac{n^5-\sum_{i=1}^4((-1)^i*C_5^{i+1}*f(n,4-i))}{5}=\frac{n^5+C_5^2*f(n,3)-C_5^3*f(n,2)+C_5^4*f(n,1)-C_5^5*f(n,0)}{5}=\frac{n^5+10*\frac{n^2(n+1)^2}{4}-10*\frac{n(n+1)(2n+1)}{6}+5*\frac{n*(n+1)}{2}-n}{5}=\frac{n^5+15n^2(n+1)^2-10n(n+1)(2n+1)+15n*(n+1)-6n}{30}=\frac{n(6(n^4-1)+15n(n+1)^2-10(n+1)(2n+1)+15(n+1))}{30}=\frac{n(n+1)(6(n-1)(n^2+1)+15n(n+1)-10(2n+1)+15)}{30}=\frac{n(n+1)(6n^3+9n^2+n-1)}{30}=\frac{n(n+1)(2n+1)(3n^2+3n-1)}{30}$

პროგრამულად ამის გაკეთებას თქვენვე მოგანდობთ ;)

თემიდან: GeOlymp 2010-2011 Episodes

წერილები: 83

tsotne says:

8 მაისი 2012, 0:00

არაფერს :) თუ რაიმე დაგჭირდება კიდევ იკითხე ;)

თემიდან: GeOlymp 2010-2011 Episodes

წერილები: 83

tsotne says:

7 მაისი 2012, 15:45

@gskhirtladze03

რა თქმა უნდა, როცა ნაშთებს ინახავ, გაყოფის ოპერაცია არასწორ პასუხს გვაძლევს. ნაშთებზე შესაძლებელია უპრობლემოდ ჩავატაროთ დანარჩენი (მიმატება, გამოკლება, გამრავლება, ახარისხება) ოპერაციები. გაყოფის დროს შემდეგნაირად ვიქცევით.

ვთქვათ გვინდა ვიპოვოთ $A/B(mod P)$ (P მარტივია. 1000000009-ც მარტივია) ვიქცევით შემდეგნაირად.

ფერმას მცირე თეორემის თანახმად $B^{P-1}\equiv 1(modP)$ , ამიტომ $A/B\equiv A/B*B^{P-1}\equiv A*B^{P-2}(mod P)$
ე.ი. გაყოფის ოპერაცია ჩავანაცვლეთ გამრავლების და ახარისხების ოპერაციით: $A/B\equiv A*B^{P-2}(mod P)$

თემიდან: Google Code Jam 2012

წერილები: 83

tsotne says:

7 მაისი 2012, 12:31

კი რა თქმა უნდა მიფიქრია, მაგრამ random-ით ქვესიმრავლეების დაგენერირება ვეღარ მოვიფიქრე :D

თემიდან: Google Code Jam 2012

წერილები: 83

tsotne says:

5 მაისი 2012, 23:51

მშვენიერი ამოხსნაა :)

meet-in-the-middle არ ვიცი, მარა ეს კარგია :დ რატომღაც არ დავფიქრებულვარ რომ ძაან ბევრი ჯამები გამეორდებოდა...

საინტერესოა თუ არსებობს ამოხსნები რომლებიც მხოლოდ წამებს ანდომებენ პასუხის პოვნას :?

თემიდან: Google Code Jam 2012

წერილები: 83

tsotne says:

5 მაისი 2012, 23:03

კარგი ამოცანები იყო :) მარა დაღლილი ვიყავი ძაან (vekua cup...) და დიდხანს მოვუნდი... ელდარ, მესამე როგორ გააკეთე? გილოცავ მაგარი შედეგია ძაან ;)

თემიდან: ფორმულის მიღება

წერილები: 83

tsotne says:

3 მაისი 2012, 12:01

nikaj - ლაიქი შენს პოსტს :)

თემიდან: ფორმულის მიღება

წერილები: 83

tsotne says:

1 მაისი 2012, 12:16

ნუ დამჭირვებია და გამომიყვანია. რამე პრობლემაა?

თემიდან: CodeForces Round #117 (Div. 2)

წერილები: 83

tsotne says:

29 აპრილი 2012, 11:36

მისმინე, თუ გაქვს პირველი ტიპის "1 2" და მეორე ტიპის "1 2" ბლოკი. არ შეგიძლია ერთმანეთის გვერდით დადგა ორი ცალი პირველი ტიპის ან ორი ცალი მეორე ტიპის ბლოკები ("1 2"->"2 1" არ შეიძლება). მაგრამ თუ აიღებ პირველს პირველი ტიპისას და მეორეს მეორე ტიპისას მაშინ შეიძლება მიდგმა ანუ "1 2"-ს მიედგმება "2 1". კვადრატი არაფერ შუაშია. უბრალოდ, არ შეიძლება ერთმანეთის გვერდით დააყენო ერთიდაიგივე ტიპის ორი ბლოკი.

თემიდან: სკანირებული ტექსტის ამოცნობა

წერილები: 83

tsotne says:

26 აპრილი 2012, 13:20

ახლაც ატარებენ ეგენი მემგონი, CodeForces-ზე :)

თემიდან: TopCoder SRM 541

წერილები: 83

tsotne says:

26 აპრილი 2012, 13:14

ხო ჯიმი ვნახე ჩელენჯებში რაებიც გიჩალიჩია :D საღოლ :)

ნიკა, მთავარში ვის გულისხმობ? :?

თემიდან: სკანირებული ტექსტის ამოცნობა

წერილები: 83