I will be hosting Petr Mitrichev Contest 10 this Saturday (October 27) between 15:30 and 20:30 Moscow time (other timezones: http://timeanddate.com/worldclock/fixedtime.html?msg=Petr+Mitrichev+Contest+10&iso=20121027T1530&p1=166&ah=5 ).

The contest will be held at http://codeforces.com/gyms . Both teams and individual participants can join. The contest itself will be at http://codeforces.com/gym/100110 , but this link will be accessible only after the start of the contest.

There will be 10 problems of varying difficulty (most are quite difficult) for 5 hours. Your solution needs to be correct on all test cases to be accepted (the standard ACM ICPC rules). People will be ranked by the number of solved problems, and by total penalty time in case they're tied on solved problems, so don't be late! :) Note that in each problem you need to read the input from a file and write the output to another file — so don't read from stdin and don't write to stdout! Problem statements will be in English.

Feel free to ask any questions that you might have, and also please tell if there are any issues with the contest system — it's the first time I'm using codeforces.com/gyms .

Registration: http://codeforces.com/gymRegistration/100110

5 minutes before start, good luck everyone!

Solution ideas: 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.

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

multiplesof 2, not all 2factors. 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...