Petr's blog

Petr Mitrichev Contest 10 — this Saturday!
By Petr, 11 years ago, In English

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

  • Vote: I like it
  • +103
  • Vote: I do not like it

Comments Comments (76)
| Write comment?
»
11 years ago, # |
  Vote: I like it +9 Vote: I do not like it

will you write problem analysis after the contest?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I don't think so :) I'll be willing to discuss the problems, but writing the formal analysis is a bit too much.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        Sure, I can write the solution ideas. I just don't have time to write analysis at the level people expect here at Codeforces :)

        → Reply
»
11 years ago, # |
  Vote: I like it -29 Vote: I do not like it

Ready, Steady , Goooooo.............. :)

→ Reply
»
11 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I think it deserves five stars, the problems are really hard.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

Tasks will be on English and Russian?

P.S. sorry, don't read description in gym

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    The tasks will be in English.

    "Statements: in English"

    → Reply
»
11 years ago, # |
  Vote: I like it +29 Vote: I do not like it

22 hours and 30 minutes before the start of the contest.

→ Reply
»
11 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Will this contest be rated ?

→ Reply
»
11 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Excuse me, How can I find the problems of the previous Petr Mitrichev Contests?

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it -14 Vote: I do not like it

Is Input and Output formats are same as ordinary problems in codeforces??

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Not sure if I understand the question. The input and output are text files, usually containing whitespace-separated numbers.

    → Reply
»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

→ Reply
»
11 years ago, # |
  Vote: I like it -8 Vote: I do not like it

is the contest rated ??

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sorry i did not read the previous comment

    → Reply
»
11 years ago, # |
  Vote: I like it -7 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Yes,Ramp, I'm agree with you!

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    So you just copy pasted Epiq's comment?!

    → Reply
»
11 years ago, # |
  Vote: I like it +75 Vote: I do not like it

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)

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +21 Vote: I do not like it

    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!

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will the solutions be public after the contest ??

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks Petr, really nice problem set.

→ Reply
»
11 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Solution ideas: http://petr-mitrichev.blogspot.com/2012/10/petr-mitrichev-contest-10-solution-ideas.html

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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??

→ Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Will testcases be published? (What is case 22 of F?)

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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?

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the intended time limit for D: 2 or 5 seconds?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But anyway, congratulations on solving it! I'm pretty sure you'd be able to fit under 2 seconds if you wanted.

    → Reply
»
11 years ago, # |
  Vote: I like it +13 Vote: I do not like it

A 4-star contest that the winner solves 4 of 10 problems.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 ???

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, we handle 2 in the same way we handle 5.

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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!

          → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            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).

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              11 years ago, # ^ |
              ← Rev. 3   Vote: I like it 0 Vote: I do not like it

              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!

              → Reply
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

By the way, there are standings for this contest held in Petrozavodsk. On that contest there was no problem G though.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      One strange difference is the Tennis Scores problem — it's actually quite straightforward and I'm very surprised nobody got it today.

      → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why can't I see others' code?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You can only see submissions for a problem in gym after you solve it.

    → Reply
»
11 years ago, # |
  Vote: I like it +24 Vote: I do not like it

A funny thing . Team's name can be a space. :)

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can I see the test cases? When I open my submissions, I can't see them.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Can you try submitting in practice mode? I've just submitted a bogus solution and I can see the testcase.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, my submission was submitted in practice mode.. Maybe problem G's testcases aren't available?

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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?

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
          ← Rev. 3   Vote: I like it +36 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            What to do if I log in with my Google account and don't have a Codeforces password?

            → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I find some .lab files. What should I do to open them?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              11 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              /%gym_id%/release/problems/%problem_name%/tests

              → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Excuse me, in problem B, how can I calculate the answer modulo 2^10?

→ Reply
»
11 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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 ?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    You can use Tor or VPN. Don't be lazy.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      What you advise is basically to break the law. Not fair or good, but law nontheless

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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).

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          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

          → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            yes of course the former; like wikipedia and facebook etc... vpn costs money and is forbiddden so it's al little troublesome...

            → Reply