دعوت و شرکت در contest های online

[Goharshady]

[center:bff6d3698b]به نام خداوند جان و خرد کزین برتر اندیشه برنگذرد[/center:bff6d3698b]سلام
با توجه به نظرسنجی صورت گرفته در تاپیک codeforces این تاپیک ایجاد شد.
در این تاپیک می توانید contest های آنلاین را معرفی و از دیگران برای شرکت در آنها دعوت کنید. همچنین پس از پایان هر contest معرفی شده در این جا بحث و تبادل نظر در مورد آن contest و راه حل ها را خواهیم گذاشت.

برای همه آرزوی رستگاری می کنم

 

[Goharshady]

اولین contest : برای اولین بار: CodeChef August Cook-Off

[center:b08dc45f18]

[/center:b08dc45f18][center:b08dc45f18]http://www.codechef.com/[/center:b08dc45f18]

Codechef یک وب سایت هندی است. که مسابقه ی August Cook _Offآن تا ۳ روز دیگر شروع می شود. به نفرات برتر جوایز نقدی تعلق می گیرد. همچنین در این سایت امکان تمرین هم وجود دارد. من همه ی شما را به شرکت در Codechef August cook -Offدعوت می کنم.​

 

[Olympiad]

راستي چجوري بايد تو Contest ثبت نام كنيم .....؟؟؟؟!!‌من چيزي نديدم !!!؟؟؟؟؟

 

[Goharshady]

کافیه عضو codechef بشین

 

[Goharshady]

ضمنا یادم رفت بگم که ساعت شروع contest به وقت ایران می شه تقریبا ۹ شب که به مراتب بهتر از ساعت شروع codeforces است!

 

[rezashiri]

لطفا بعد از مسابقه اون دو تا سوالی که بیشترین acc رو داشتن ترجمه کنید

 

[rezashiri]

کسب رتبه 68 رو به گوهرشادی تبریک می گم

 

[SABB]

چقدر زود تموم شد. رتبه 68 رو بهتون تبریک میگم.

 

[Goharshady]

آخه این رتبه تبریک گفتن داره؟ اگه اون سوال ۴ که با اختلاف ۰.۱ ثانیه تایم می شدم رو می تونستم acc کنم الآن دهم بودم.

 

[SABB]

راه حل های من:
http://snipt.net/SABB/codechef-appetizers/
http://snipt.net/SABB/codechef-cleanup/

میشه راه حل هاتون رو هم بذارید؟

 

[rezashiri]

راه حل های من:
http://snipt.net/SABB/codechef-appetizers/
http://snipt.net/SABB/codechef-cleanup/

میشه راه حل هاتون رو هم بذارید؟

میشه تا فردا همین دو تا سوال رو ترجمه کنید؟!؟

 

[SABB]

اشکال نداره داستان هاشو ننویسم؟! آخه وسط سوالا زیادی چرت و پرت نوشته بود.
سوال اولی:
یک رشته به طول n=2^k از حروف کوچک انگلیسی داریم که در واقع یه پیغامه که یه آشپز می خواد به مهموناش بده. برای همین هم برای هر حرف شماره اش رو به صورت باینری مینویسه. از طرفی همه ی اعداد باینری ای که مینویسه k بیتی هستن و اگه نباشن خودش سمت چپ اونا چندتا صفر میذاره تا k بیتی بشن.
به یه دلایلی این اعداد باینری توسط مردم برعکس (به صورت معکوس) خونده میشن و اونوقت پیغام اشتباهی میرسه. مثلا 001 رو 100 میخونن و در نتیجه جای اون دوتا حرف رو برعکس متوجه میشن. می خوایم اون پیغام اشتباهی رو بدست بیاریم.

سوال دومی:
یه تعداد کار داریم که با شماره های 1، 2، ...، n مشخص می شن. سرآشپز و دستیارش باید این کار ها رو انجام بدن، ولی یه سری کار ها قبلا توسط آشپز ها انجام شده. اول آشپز کوچکترین اندیسی که کارش قبلا انجام نشده رو انجام میده، بعد دستیارش کوچکترین(دومین) کار رو، و به همین صورت یکی در میان...
می خواهیم بدونیم کدوم اندیس ها رو آشپز انجام میده و کدوم ها رو دستیارش.

 

[rezashiri]

اشکال نداره داستان هاشو ننویسم؟! آخه وسط سوالا زیادی چرت و پرت نوشته بود.
سوال اولی:
یک رشته به طول n=2^k از حروف کوچک انگلیسی داریم که در واقع یه پیغامه که یه آشپز می خواد به مهموناش بده. برای همین هم برای هر حرف شماره اش رو به صورت باینری مینویسه...

میشه بگی منظور از شماره هر حرف چیه؟!

مثلا توی کلمه chef شماره f برابره 4 هست؟

 

[SABB]

اشکال نداره داستان هاشو ننویسم؟! آخه وسط سوالا زیادی چرت و پرت نوشته بود.
سوال اولی:
یک رشته به طول n=2^k از حروف کوچک انگلیسی داریم که در واقع یه پیغامه که یه آشپز می خواد به مهموناش بده. برای همین هم برای هر حرف شماره اش رو به صورت باینری مینویسه...

میشه بگی منظور از شماره هر حرف چیه؟!

مثلا توی کلمه chef شماره f برابره 1 هست؟

توی chef ، شماره ی c برابر 0، شماره ی h برابر 1 ، e برابر 2 و f برابر 3 هست (از چپ به راست به صورت صعودی شماره گذاری میشن).

 

[Goharshady]

من روی این سوالها تقریبا هیچ وقتی نذاشتم .همه ی وقتم رفت روی سوال Cupcakes که مجموعه ی مستقل باید پیدا می کردیم که متاسفانه آخرش هم تایم شد. دیگه آخرهای contest دیدم دارم صفر می شم این دو تا رو هم نوشتم:

http://snipt.net/goharshady/codechef-arrange
http://snipt.net/goharshady/codechef-cleanup-1/

 

[SABB]

ببخشید میشه کدتون واسه Cupcakes رو هم بذارید؟

آخه من نمی دونم الگوریتمم درست بود نه

 

[Goharshady]

Cupcakes یک مسئله ی NP-Complete بود که احتمالا باید خیلی بهینه سازی می کردیم تا به جواب برسیم. من که هنوز acc نشده ام. کل وقت امتحانم روی همین مسئله رفت. این ۳ تا مقاله را ببینید:
http://en.wikipedia.org/wiki/Independent_set_(graph_theory)
http://en.wikipedia.org/wiki/Maximal_independent_set
http://en.wikipedia.org/wiki/Clique_problem#Finding_maximum_cliques_in_arbitrary_graphs
می دانیم که پیدا کردن یک مجموعه ی مستقل فرقی با پیدا کردن یک خوشه ندارد

 

[SABB]

ببخشید میشه cupcakes رو ترجمه کنید؟
با این الگوریتما و... که گفتید فکر کنم کلا سوالو اشتباه متوجه شده بودم و چرت و پرت نوشتم!!

 

[Goharshady]

یک گراف با n راس و m یال به شما می دهند و شما باید بگویید که مجموعه ی مستقلی به اندازه ی حداقل k دارد یا نه.

 

[rezashiri]

اینجا رو ببینید....

من که سر ازش در نیاوردم ببینید شما چیزی متوجه می شید!؟؟

البته مسابقه نیست ، مثلا یه سایتی مثل sgu....