В эту субботу, 27 октября, состоится Petr Mitrichev Contest 10, с 15:30 до 20:30 по Москве (другие часовые пояса: http://timeanddate.com/worldclock/fixedtime.html?msg=Petr+Mitrichev+Contest+10&iso=20121027T1530&p1=166&ah=5 ).
Контест будет проходить на http://codeforces.com/gyms . Приглашаются и команды, и индивидуальные участники. Сам контест будет по адресу http://codeforces.com/gym/100110 , но эта ссылка заработает только после начала контеста.
Будет 10 задач на 5 часов, некоторые попроще, большинство посложнее :) Засчитываются только решения, прошедшие все тесты (правила ACM ICPC), выигрывает тот, кто решил больше задач, а при равенстве — у кого меньше штрафное время, так что опаздывать не стоит. Во всех задачах нужно читать входные данные из файла и писать результат в файл, не читайте из stdin и не пишите в stdout! Условия будут по-английски.
Если что непонятно, спрашивайте. Пишите тоже, если что-то не так с системой — я пользуюсь codeforces.ru/gyms в первый раз.
Регистрация: http://codeforces.com/gymRegistration/100110
Начинаем через 5 минут, всем удачи!
Разбор: http://petr-mitrichev.blogspot.com/2012/10/petr-mitrichev-contest-10-solution-ideas.html
will you write problem analysis after the contest?
I don't think so :) I'll be willing to discuss the problems, but writing the formal analysis is a bit too much.
I would actually be glad to read about solution ideas from the author of the contest (Petr, in this case). I would not like 'formal analysis' too, but at least some kind of a 'scratch' of proposed solutions.
Sure, I can write the solution ideas. I just don't have time to write analysis at the level people expect here at Codeforces :)
Ready, Steady , Goooooo.............. :)
I think it deserves five stars, the problems are really hard.
I'm not familiar with the established standards for those stars, but the description says "recommended only for ACM ICPC finalists and winners of international competitions", while I'm pretty sure there are many teams who are not finalists and haven't won international competitions and can still get a decent result in my contest.
Tasks will be on English and Russian?
P.S. sorry, don't read description in gym
The tasks will be in English.
"Statements: in English"
22 hours and 30 minutes before the start of the contest.
Will this contest be rated ?
No.
Когда давно спалили ссылку на материалы Петрозаводска 2012, я успел выкачать все видео материалы, в том числе разбор автором своего контеста. Если Petr разрешит, то можно будет это видео выложить куда-нибудь...
О, а можно мне сначала посмотреть? :)
Опубликовал на ютубе и поставил ссылку из разбора, спасибо!
Excuse me, How can I find the problems of the previous Petr Mitrichev Contests?
Petr Mitrichev Contest 1: problems 306-314 from http://acm.sgu.ru/problemset.php?contest=0&volume=3
Petr Mitrichev Contest 2: problems 326-225 from http://acm.sgu.ru/problemset.php?contest=0&volume=3
Petr Mitrichev Contest 3: problems 414-422 form http://acm.sgu.ru/problemset.php?contest=0&volume=4
Petr Mitrichev Contest 4: problems 423-432 from http://acm.sgu.ru/problemset.php?contest=0&volume=4
Petr Mitrichev Contest 5: problems 497-507 from http://acm.sgu.ru/problemset.php?contest=0&volume=4 and http://acm.sgu.ru/problemset.php?contest=0&volume=5
Petr Mitrichev Contest 6: problems 508-517 from http://acm.sgu.ru/problemset.php?contest=0&volume=5
Petr Mitrichev Contests 7-9 have not appeared online (yet).
One more question, do the Petr Mitrichev Contests 7-9 exist?
Yes.
These problems are not available for public?
Petr Mitrichev Contests 7-9 have not appeared online (yet).
Do problem analisys for this contests exist?
Could you give a link?
I don't remember doing detailed analysis for those, you might be able to find some solution ideas by googling. Sorry, I don't have any links ready.
Did you write problem ideas about previous Petr Mitrichev Contests?
Is Input and Output formats are same as ordinary problems in codeforces??
Not sure if I understand the question. The input and output are text files, usually containing whitespace-separated numbers.
1 hour 40 minutes before start. Note that you can register for the contest now, but you will also be able to register during the contest itself if you forget to register now.
Also note that the website has support for forming teams from several individual accounts.
is the contest rated ??
sorry i did not read the previous comment
I would actually be glad to read about solution ideas from the author of the contest (Petr, in this case). I would not like 'formal analysis' too, but at least some kind of a 'scratch' of proposed solutions.
Yes,Ramp, I'm agree with you!
So you just copy pasted Epiq's comment?!
Why don't you make it a normal Codeforces round? I think that would attract more people :)...And it seems my teammates are all dating with girls this night so I can only participate individually:( (yes,I'm the poor guy without girlfriend)
These problems were already used in a contest before, so it's not appropriate to use them for a rated competition.
Plus, normal Codeforces rounds assume several testers, Russian problem statements, and so on :)
Good luck!
Will the solutions be public after the contest ??
Thanks Petr, really nice problem set.
Solution ideas: http://petr-mitrichev.blogspot.com/2012/10/petr-mitrichev-contest-10-solution-ideas.html
For problem B , I thought of something like this : nCk % 10^10 = nCk % (2^10 * 5^10) , We can find it's value by using chinese remaindering . Then for computing nCk % mod , we can write it as fact[n] * inverse (fact[k]) * inverse(fact[n — k). Finally I was stuck in finding no of digits in nCk , Can anybody help in it??
Will testcases be published? (What is case 22 of F?)
I'm not sure, you might be able to see the testcases now when you open your submission.
Case 22 in F is:
2 97108290405407
b=2 is tricky because all strings of short length actually have different hashes in that case — does it cause problems for your solution?
What is the intended time limit for D: 2 or 5 seconds?
2 seconds. It was intended that you notice the periodicity of the answer with respect to m, and then just submit the very quick solution that solves only small fields.
I noticed it when running with big m. But since handling this case would be more complicated, I tried to make some optimization in my dp.
But anyway, congratulations on solving it! I'm pretty sure you'd be able to fit under 2 seconds if you wanted.
A 4-star contest that the winner solves 4 of 10 problems.
Yes, that's quite strange :)
My hope was that the problems would be still interesting to solve, even if you don't solve many. I'm sorry if that was not the case.
The problems are really great. :)
Hi Petr, From your blog for problem B, Computing the answer modulo 5**10 is done by first calculating the power of 5 in (n,k) separately, and then calculating (n,k) with all powers of 5 removed from all numbers using the fact that we can now use division and thus just need to calculate factorials (skipping numbers divisible by 5) modulo 5**10, and numbers modulo 5**10 is a periodic sequence.
I could not understand how the modulo can be the same , after dividing the numbers by 5 (as you are saying powers of 5 removed). Please Help.
So we need to compute fact[n] with all powers of 5 removed. Let's denote fact_without5[n]=1*2*3*4*6*7*8*9*11*12*...*n — so we just skip all numbers divisible by 5. Then we can notice that
fact[n]=fact_without5[n]*fact_without5[n/5]*fact_without5[n/25]*...
And calculating fact_without5 can be done using the fact that the numbers begin to repeat after 5**10. Is it more clear now?
For the first part of the problem : for finding (n,k) % 2^10 : We can write it as : (n,k) % 2^10 = fact[] * inverse (fact[k] , 2^10) * inverse (fact[n — k] , 2^10)
So As the numbers in inverse might have 2 as a common factor , So inverse will not exist. So for this remove the powers of 2 from it.
Am I right ???
Yes, we handle 2 in the same way we handle 5.
Hello, how do I find the factorial for larger n? I cant understand the repeating thing, for example lets suppose the mod is 8, then as you said numbers should repeat after 8, but they dont, for instance if n = 12: 1 * 1 * 3 * 1 * 5 * 3 * 7 * 1 * 1 * 5 * 11 * 3 (I took out the 2 from the numbers). Thank you!
You should take out all multiples of 2, not all 2 factors. So for example fact_without2[12] = 1 * 3 * 5 * 7 * 1 * 3.
And fact[12] = fact_without2[12] * fact_without2[6] * fact_without2[3] (12, 12/2 and 12/4 respectively).
Humm, what about the numbers that are multiple of 2, how do I include them on the answer? (2, 4, 6, 8, 12...).
Edit: That gives the same result as 1 * 1 * 3 * 1 * 5 * 3 * 7 * 1 * 1 * 5 * 11 * 3 = 51975, and that way it produces: 1 * 3 * 5 * 7 * 11 * 1 * 3 * 5 * 3 = 51975. But that way its periodic :), got it now thank you!
By the way, there are standings for this contest held in Petrozavodsk. On that contest there was no problem G though.
Right, thanks! So problems A-F in that ranklist correspond to problems A-F today, whereas problems G-I correspond to problems H-J today.
One strange difference is the Tennis Scores problem — it's actually quite straightforward and I'm very surprised nobody got it today.
It very technical. It took us a lot of time on the contest.
I guess nobody likes long problem statements :D
Yes I really hate problems that have long statements!
Why can't I see others' code?
You can only see submissions for a problem in gym after you solve it.
A funny thing . Team's name can be a space. :)
Can I see the test cases? When I open my submissions, I can't see them.
Can you try submitting in practice mode? I've just submitted a bogus solution and I can see the testcase.
Yes, my submission was submitted in practice mode.. Maybe problem G's testcases aren't available?
I can see all testcases at the bottom of this page:
http://codeforces.com/gym/100110/submission/2454639
Maybe there's a problem with your browser?
If you have coach account (and it's turned on or you are the creator of the contest), you can see everything;
If you don't have coach account, but solved the problem, you can view the tests via FTP (ftp://taskbook.codeforces.ru, use your login/password);
If you don't have coach account, and didn't solve the problem, you cannot see anything.
Thanks for the explanation! I was able to see the cases even with coach account turned off, maybe this has to do with me being the creator of the contest.
What to do if I log in with my Google account and don't have a Codeforces password?
I find some .lab files. What should I do to open them?
/%gym_id%/release/problems/%problem_name%/tests
Excuse me, in problem B, how can I calculate the answer modulo 2^10?
your blog is blocked in CHINA... So the sol is not available :( would you please copy one into CF blog so that programmers in china can view it ?
You can use Tor or VPN. Don't be lazy.
What you advise is basically to break the law. Not fair or good, but law nontheless
I don't know much about Chinese laws, however, I don't see how it is possible that accessing Petr's blog via VPN is less legal than accessing it via asking someone to repost it to codeforces. Their laws either force ISP's to block some resources (then both ways are legal), or they forbid users to access some resources (then both ways are illegal).
If information from Petr blog will appear on some other resource there are two possible cases:
information in question is not forbidden and was blocked only because whole resource (i. e. blogpost) was blocked
information in question was actually forbidden by itself and new place would also be blocked.
In both cases I do not believe there was illegal action by ysymyth and former also is much more probable
yes of course the former; like wikipedia and facebook etc... vpn costs money and is forbiddden so it's al little troublesome...
Может в прямом эфире указывать дату создания поста, чтобы сразу было понятно, что актуально, а что — некропост? А то я прямо обрадовался, увидев анонс Petr Mitrichev Contest в эту субботу, зашел и раздосадовался, увидев, что опоздал на семь месяцев.
Вряд ли стоило бы этому радоваться, так как такой контест, скорее всего, пересекался бы с IPSC 2013
upd: напомнил так напомнил!