drazil's blog

By drazil, 10 years ago, In English

Hello, everyone! Codeforces Round #272 will be held at this local time. We're looking forward to your participation!

The problems are from dreamoon_love_AA and drazil(that's me) from Taiwan, and thanks 9mmlitswe for some discussion. Also we want to thank Zlobober and Gerald for helping us prepare the round, Delinur for translating the statement into Russian, and MikeMirzayanov for Codeforces and Polygon.

This is our first round on Codeforces, we hope you'll find it interesting! Please read all problem statements and discover what the main character dreamoon_love_AA do in those problems for he's really cute =)

Update1 Note this round will be held 1.5hrs earlier than usual Codeforces rounds, so please double check the starting time in your local time.

Update2 Score distribution!
Div2: 500-1500-1500-2000-2500
Div1: 500-1000-1500-2000-3000

Update3 The contests are over. Congratulations to the winners!

Div1:
1. Petr
2. qwer1561
3. kutengine
4. ifsmirnov
5. TankEngineer

Div2:
1. ridowan007
2. a00012025
3. xavier13540
4. v_Enhance
5. pkq2006

And standings are here:
Div1: standings
Div2: standings

Update4 Editorial can be found here. It's finished by now but it's welcome to tell me if anything can be improved!

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

| Write comment?
»
10 years ago, # |
Rev. 2   Vote: I like it -48 Vote: I do not like it

After the rather lengthy round announcements of Round 271, Bayan Contest, Round 270, and Round 269, the age of short announcements are back. And what has dreamoon_love_AA been doing the past few contests? Trying to be another worse ?

»
10 years ago, # |
  Vote: I like it +80 Vote: I do not like it

Did Zlobober became a long-term problem tester as Gerald? Fact that he is no longer visible in contribution standings (as MikeMirzayanov :P) seems to confirm this.

»
10 years ago, # |
Rev. 2   Vote: I like it +23 Vote: I do not like it

I think you should write a warning about the unusual time of the round

Some people may miss the round if they didn't notice that.

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    This round will be held at CST-1:30 (1.5 hours before Codeforces Standard Time)

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

      Let's hope for math :)!

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

        yep he always hope for math for me I always hope for early score distribution announcement :D

»
10 years ago, # |
  Vote: I like it +18 Vote: I do not like it

I expect it will be a very Nice contest and contains various problem set
dreamoon_love_AA rank at UVA is 7 solved about 3205 problem this is his profile
http://uhunt.felix-halim.net/id/2397
I don't know other Online judges but being rank 7 on UVA is sufficient to see cool & various problem set

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

    Doesn't being an international grandmaster (like dreamoon_love_AA was before his fall (partially on purpose)) is a sufficient proof :P?

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

      sometimes Theorem has more than one proof :P :D

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    dreamoon_love_AA also solve around 1432 problems here in codeforces ( as like you i don't know others OJ number but i am pretty much sure there must be more than thousands also ) . i always wonder is problem solving is that kind of addiction to him if he won't solve 10 or more problems in a day he can't eat or sleep :D

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

    I wonder how many problem he solved in one day. Did he sleep at night or goes to school? I was trying to see his first solved problem in uva. But now it is still loading for few minutes.

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

      I don't think he'd go to school at night :D

      A year has 365 days. His profile shows 8 years of solving. That means about a problem a day (very roughly), probably often several easy ones a day. Do you think sleep matters at all in this case? :D

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

        Of course you are right. He is solving till 2006. At 2014 he solved about 8-15 problem some day. Of course it is easy for him after a lot of solving.

»
10 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Damn. Bayan Qualification + Marathon24 + NEERC + Codeforces Round #272.

Because screw weekends

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

    You count Bayan Qualification along with those other contests? >_>

    I'd replace it with Codechef Long Challenge, it has more decent problems now.

»
10 years ago, # |
  Vote: I like it +12 Vote: I do not like it

3000 point E problem come back! Do you guys want to make a super hard problem that is even harder than Chinese IOIer's round?

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

    I was about to say the same :). Maybe I should read E in the beginning and in case I got this coded already, paste my solution, otherwise not give it any thought :P.

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

what a nice contest time :)

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In the div2,the second problem is 1500,I dont't think it's easy.

»
10 years ago, # |
  Vote: I like it +12 Vote: I do not like it

I think a newly registered guy will be on top of Div.2 contest.

»
10 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Found out that I don't have a pen at home 10 minutes before the contest. Going to use Paint instead of pen!

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Oh I forgot registering contest.. :<

»
10 years ago, # |
Rev. 2   Vote: I like it +44 Vote: I do not like it

Goodbye red color :(

»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Who else failed A because of long overflow

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

    Are you happy with math problems?

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

      C was good non maths problem >:D

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

      Yes I am happy (yay I got B) but failed A

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

      I don't understand why this naive code fail for pretest 5. code

      I was using that for find my mistake, but I couldn't

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

        Because (i%b) should be a divisor of (i/b).

  • »
    »
    10 years ago, # ^ |
    Rev. 3   Vote: I like it +22 Vote: I do not like it

    I thought: "Problem with MOD! I'll do some hacks today!" and instalock it. After few minutes I figured out that my solution is wrong because I forgot to add some MOD...

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

    Exactly though i didn't give the contest because I actually woke after 30 mins past the start time but definiately this is the first problem I have seen of long overflow.really tricky on this part.

»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

how to solve B -div1 ??

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it +16 Vote: I do not like it

    Output ((6i + 1)k, (6i + 2)k, (6i + 3)k, (6i + 5)k) for all i = 0, 1, ..., n - 1. (And thus the maximum is (6n - 1)k.)

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

      missed it completely ...thnx

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

      Why 6i ???

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

      why this 6*i+1 format ?? I mean a simple proof ?

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

        See here

        Basically you need three odd numbers for each set, and there are 3 odd numbers every 6 numbers.

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

        First, divide everything by k, so now we want all numbers in each set to have pairwise GCD 1.

        Note that we can only have one even number; if we have two even numbers, their GCD is even and thus not 1. So we need three odd numbers.

        As it turns out, 6i + 1, 6i + 2, 6i + 3, 6i + 5 has pairwise GCD 1 for any integer i, so we might as well use it. By using all lowest values of i (namely i = 0, 1, 2, ..., n - 1), we have maximum m = 6(n - 1) + 5 = 6n - 1. Also note that since we need three odd numbers per set, we need 3n odd numbers, and if m < 6n - 1 then we don't have enough odd numbers to use. Thus m = 6n - 1.

        Remember that we have divided everything by k to make the pairwise GCD 1 instead of k, so now just multiply everything by k again.

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

          why 6 !!!

          why not any other even number 4, 8, 2, anything :3 ?

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

            You need three odd numbers (one can be even), and this happens every 6.

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

          I wrote for each set 6i+1,6i+3,6i+5 and first even number, which is coprime with each of these 3 numbers. And each time I was choosing an odd number bigger than previous one. I've checked that the even number in each set is less than all other odd numbers. And also multiplied each number to k and m=(6n-1)k. But this solustion didn't pass. Do you know my misstake? Could you show me some test for this, in which this solution is wrong?

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

            You read in n as k and k as n.

            n comes before k in the input.

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

              OMG I've just found it)) that is impossible misstake)) I can't believe it =D tnx

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

              and it passed after changing n and k

»
10 years ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

92anurag was the first to ask.

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

    Uhm, the solution is in the sample. Just use 6i + 1, 6i + 2, 6i + 3, 6i + 5 (assuming k == 1). Upper bound is easily obtained from the observation that at least 3 numbers in each set should be odd.

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Explanation for problem C Div2?

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    for (mod = 1; mod < b; mod++) 
    res += mod * b * a(a+1)/2  + mod * a
    
    • »
      »
      »
      10 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      How are you sure that an O(b) solution with multiplication,division and mod solution will pass under 1 second? Same question to O(a) solutions also

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

        10^7 * k operations (where k < 50) should mostly pass.

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

      I did the same. Can you tell me why 8200906 is hacked?

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

        You casted to double, losing precision. (Double can only hold about 53 bits of precision; with a = 109, that you're computing needs 59 bits.)

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

          Thank you! And also, how do you calculate how much precision it needs?

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

            Oops, I have successfully confused myself. a = 107, not 109.

            No, the problem is below that: sum*i*b essentially explodes. With a = b = 107, i = 107 - 1, we have , thus you're computing . This requires 94 bits; long long only has 63 bits.

            Computing precision is simple; take the number, take its logarithm base 2, and round up. That's the number of bits you need.

            • »
              »
              »
              »
              »
              »
              »
              10 years ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              I actually tried sum*((a*b)%MOD) I doesn't work either.

              • »
                »
                »
                »
                »
                »
                »
                »
                10 years ago, # ^ |
                Rev. 2   Vote: I like it +3 Vote: I do not like it

                You want sum*i*b not to give overflow. Thus:

                • You should have taken the modulo of sum earlier. Insert sum %= MOD; before the line, or perhaps after computing sum with that casting to double.
                • You should have taken the modulo of the first multiplication before doing the second. Replace sum*i by ((sum*i)%mod).

                The good thing is that delaying the modulo to the end of the line is still okay, although you should try making a habit of taking modulo after every arithmetic operation if overflow is a problem.

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

                  Yeah, it worked! Thank you really much. I appreciate your effort.

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

        ll sum = (double)(1+a) / 2 * a;

        (ll) expected, but (double) found

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

          Shouldn't it be double because something divided by 2 might something.5?

          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            use (ll)(a+1)*a/2 instead

            Because there is exactly one even number in a+1 and a.

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

              There should be another mistake somewhere else because it still doesn't pass. 8208763

              • »
                »
                »
                »
                »
                »
                »
                »
                10 years ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                res = (res + ((sum*((i*b)%MOD))%MOD) + ((a*i)%MOD)) % MOD;

                sum is too large.


                res = (res + (((sum%MOD)*((i*b)%MOD))%MOD) + ((a*i)%MOD)) % MOD;
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Observe that all numbers satisfying the condition has the form x = (bk + 1)(mod(x, b)). Since mod(x, b) can be any integer between 1 and b - 1 inclusive, k can be any integer between 1 and a inclusive, and all those numbers are valid, you're adding up (b + 1)(1) + (b + 1)(2) + ... + (b + 1)(b - 1) + (2b + 1)(1) + (2b + 1)(2) + ... + (2b + 1)(b - 1) + ... + (ab + 1)(b - 1).

    We group every b - 1 terms; these are all in the form for some x. Thus our sum becomes , which can be simplified to .

    There you go, an O(1) solution. I wonder why the time limit is 1.5 seconds...

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

      Time limit is 0.00001 seconds ?

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

      hey thanks for the solution.. Can O(b) or O(a) solutions which are given here pass under 1.5 seconds? Also, How do i check what is the expected complexity according to constraints in such problems

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

        Yes, both O(b) and O(a) will pass. Can you rephrase the second question as I did not understand it.

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

      Are there any mathematics calculations which way you thought that all numbers satisfying the condition has the form x = (bk + 1)(mod(x, b)) ? Does it mean that you get this formula with transform this: k=(x/b)/(mod(x,b) or you just get it by logical analysis ?

      I know that 'X' has form (bk + 1)(mod(x, b)) but I doesn't get it by algebraic manipulations. Could I get it from this formula: k=(x/b)/(mod(x,b) ? ( Excuse me for this stupid question but i really don't understand why you add 1 there: (bk **+ 1**)(mod(x, b)) ) certainly if you get this by algebraic manipulations. )

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

        Note that x = b·div(x, b) + mod(x, b). (This is more or less by definition; div(x, b) is x / b rounded down, thus when multiplied by b gives the largest multiple of b not exceeding x, and mod(x, b) is the missing amount to bring the multiple of b up to x.)

        The rest is just plugging in what's given in the problem and manipulating a bit.

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    x = q*b+r ---(1)
    and q/r = k
     or q = rk;
    put this in 1
    x = brk+r = r(bk+1)
    

    Now we see that , r can be 1 to b-1. thus for a particular value of k, we have

    1(bk+1) + 2(bk+1) +3(bk+1)... (b-1)(bk+1)
    =(bk+1)(1+2+..b-1)
    

    so , psudocode is below

    sum = 0;
    for(k=1;k<=a;++k)
    {
       sum+=b*(b-1)/2 * (bk+1)
    }
    
    

    don't forget to mod every expression.

»
10 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I spend more time for problem C div 2, I am bad

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

    Yeah i did that too. i was just getting confused with all those numbers . (defined by problem and me !)

»
10 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

tfw understood how to solve C at 30 sec before contest finish

»
10 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Very interesting problems! Thanks to authors!

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Problem C Div 2 / problem A Div 1 ? i am trying to calculated with arithmetic sum formula Sn = (n/2) * ( 2*a + ( n - 1 ) * d ) , where n is the limit of the sequence . here is my code WA at test case 5 . can anyone please explain what is going wrong here .

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is my submission on A Div.1: 8203037

What is wrong with my expression?

  • »
    »
    10 years ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    Because your algorithm is wrong !!!!!

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

      Thank you, captain obvious :v

      Btw I'm asking what's wrong, not why it's wrong :v

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

    I think you misinterpreted the problem or something, thinking that you're only counting numbers between 1 and a or something, not counting numbers whose k is between 1 and a.

»
10 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

solution of div2-E / div1-C someone please?

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

    DP with state pos, no_char_to_delete, where pos is the position of S.

    First pre-calculate next[i] for each i, where you can find P in S[i,next[i]], deleting zero or more character.

    Then using this info, you can run the dp.

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

      Isn't this O(pn^2), too slow?

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

        I implemented a DP with those states using some precomputing and making it in total O(pn log n). I suppose the simplest O(pn^2) approach should TL.

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

          I got that, but the number of useful states isn't Theta(pn^2)? If that's not the case, may you only hint which kind of states are useless?

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

            there is precalculation of |S|*|S|

            then the dp too is |S|*|S|

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

            Your DP is F[i][j] — maximum amount of patterns that can be formed if you use characters 1~i and remove exactly j letters. O(pn) states.

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

        But its only O(n^2).

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I tryed to use long double (16 bytes in my gcc) and printf("%Ld",v) for "B" problem but not lucky at 1st test. double and "%f" passed 1st test, and "%.9f" passed all tests... I don't understand why "%Ld" not passed 1st test, where is my error?

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

    long double,you should use cout<< to output....Ld is not using to output long double

  • »
    »
    10 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    BTW,if you run this code in CF.

    #include<stdio.h>
    int main()
    {
        printf("%d",sizeof(long double));
    }
    

    you will find sizeof(long double) is 12 in CF...

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

      who can tell me where is my "#"? and why the string is bigger than others?

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

        # produces a level 1 heading.

        Heading level 1 (# in front)

        Heading level 2 (## in front)

        Heading level 3 (### in front)

        Use ~~~~~ to delimit your code, putting it above and below the code.

    • »
      »
      »
      10 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      thanks for your answer.

      I'll use cin/cout in future. but. I think printf("%f",(double)ld); is not bad.

»
10 years ago, # |
  Vote: I like it +26 Vote: I do not like it

C Fail system test on 26.... Yellow, here I come back!

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain pretest 5 (input: 4 3) in problem C(div.2)?

Which numbers should be added?

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

    a = 4, b = 3

    Try for k = 1. We want div(x, 3) = mod(x, 3). Since mod(x, 3) = 1, 2, we thus have two numbers: one with div(x, 3) = mod(x, 3) = 1, and one with div(x, 3) = mod(x, 3) = 2. The numbers satisfying this are 4 and 8 respectively.

    Try for k = 2. We want div(x, 3) = 2·mod(x, 3). Since mod(x, 3) = 1, 2, we thus have two numbers: one with div(x, 3) = 2, mod(x, 3) = 1, and one with div(x, 3) = 4, mod(x, 3) = 2. The numbers satisfying this are 7 and 14 respectively.

    Trying for k = 3 gives 10, 20, and for k = 4 gives 13, 26.

    Adding them all gives the requested 4 + 8 + 7 + 14 + 10 + 20 + 13 + 26 = 102.

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

    Just write a brute force ....

    the numbers are : 4 7 8 10 13 14 20 26 sum = 102

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello !

what's wrong with my code?! for div 2 C

http://mirror.codeforces.com/contest/476/submission/8197243

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    ((b % mod) * (sum2 % mod) * (sum1 % mod))

    If b % mod, sum2 % mod, sum1 % mod are together pretty large (about 109 each), they make the resulting number to get overflow (about 1027).

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

    Try to mod every value RIGHT AFTER multiply. Don't multiply three values in a time, it will be overflow.

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi!

I got a TLE on D, but I found out that my program ran exactly 2000ms on some case but the system gave me a TLE :(

Here's the submission link: http://mirror.codeforces.com/contest/477/submission/8206241

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

Changed

const int N = 2e3 + 2;

to

const int N = 2e3 + 3;

and my C passed ;__;. I'm such a loser ;_;.

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve div1-C?

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

    First you need to calculate nearest subsequence that match P and start from i for every i<s.size .

    Now we can use a simple dp, at each position we have 3 choices :

    1- you can skip this position to next one so : rec(pos+1, should_delete).

    2- you can delete this position if should_delete!=0 so : rec(pos+1, should_delete-1).

    3- if we have match from pos we can use this match, we have the ending position of this match (calculated in first step) so number of characters we need to delete so we can use this match is : end[pos]-pos+1-p.size . now if this number is less than or equal to should_delete then you can use this match so : 1+rec(end[pos]+1, should_delete-(end[pos]-pos+1-p.size)).

    The answer for each step is maximum of this three choices.

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

    First, let's calculate for each position i in string s value L[i] — minimum length of substring which ends in i and it is possible to get string p by removing some characters from it. It can be easy calculated using dynamic programming.

    Next, let's find dp[i][cut] — answer for prefix of s which ends in i and with cut character removes done. It can be calculated next way:

    dp[i][cut] = dp[i-1][cut];
    if (cut > 0) 
    	dp[i][cut] = max(dp[i][cut], dp[i-1][cut-1]);
    for (int k = L[i]; k <= cut + p.length(); ++k) 
    	dp[i][cut] = max(dp[i][cut], dp[i - k][cut - k + p.length()] + 1);
    

    This solution gives us O(|s|3) complexity. But you can notice that in every dp visited in the cycle difference between i - k and cut - k + p.length() is fixed: it is equal to i - cut - p.length(). So, you just need to use fenwick trees where in ftr[i + cut][i] you will update the answer.

    Then the cycle will look like this: dp[i][cut] = max(dp[i][cut], get(ftr[i - cut - p.length()], i - k) + 1); where get(a, b) function returning maximum on fenwick tree a prefix with length equal to b.

    Of course, you can examine my solution: 8203748

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I read all the problems first time incorrectly. I figured first one after first wrong submission, figure second after frustrated by C which I made it too complex.

Btw problem was very good, lot to think less to code.

»
10 years ago, # |
  Vote: I like it -25 Vote: I do not like it

Last contest Bayan Warmup, my rank was 150, and top 50 won T-shirt.

This contest, my rank was 46, but top 50 didn't win T-shirt.

Why aren't there any T-shirt for each contest???

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

    Indeed, Codeforces should start giving T-shirts more often. I need Codeforces and Facebook T-shirts to complete my collection.

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

    Then some people would get too many t-shirts :D

»
10 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Today my contest is not so good at all, but feeling proud to see the participant ridowan007 of our country(Bangladesh) got rank 1 in Div-2. Really nice performance !!

»
10 years ago, # |
Rev. 2   Vote: I like it +28 Vote: I do not like it

Thank drazil for this interesting contest!

»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

My submission for Div1-C got TLE, even though first inspection shows its complexity is O(|s|2 + |s||p|). Besides "use a faster language other than Python", is there anything in my code that can be improved?


My algorithm is to first find all "sufficiently close" subsequences of s that is equal to p (this is constructing the array found), by iterating over each character of s and p, taking note when the latest starting position of a subsequence of s ending with the character in p. Note that since any ending character is used only once, there are only |s| elements at most. Next, I used a DP with states of the form (latest found element considered, number of subsequences) (this is constructing the array dp).

At the end of this, I have an array of how many characters at least must be deleted to give a given number of subsequences (this is constructing the array dpres), which is easily converted to give the maximum number of subsequences possible by deleting a given number of characters (this is the first state of res; the second state just takes the minimum of the first state and the theoretical maximum number of subsequences with only having a certain number of characters).

»
10 years ago, # |
  Vote: I like it +61 Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Thanks for all the interesting problems.

I liked Div 2 C and B very much.I didn't come up with solution for A.Interesting and nice problem set.

»
10 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem C div 1 (E div 2) occ(s',p) was a set of substrings. What does "substring" mean?

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

    A substring of another string S is a string of consecutive characters of S; in other words, it is formed from S by deleting some (including all and no) characters from the front and the back, but without deleting any character in-between the chosen characters. If S = abcd, then bc, ab, b, a, abcd, ε are substrings of S (ε is the empty string), but bd, abd, cb aren't.

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

      Thank you, sometimes it is not clear for me, is substring like subsequence — where you can delete some character in-between.

»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I think there should be one more line in problem C Div.1. div(x,b)%mod(x,b)=0. This causes problem in understanding problem statement for a lot of participants.

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

    You mean C Div 2?

    Normally if division is written using mathematical typeset it is to be interpreted as real division. Besides, if the intention is floored division, it should have been div(div(x, b), mod(x, b)) = k instead, as the problem already defined div. And of course you can always ask the problem setter using the question asking feature.

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

    No. It was stressed that their quotient must be an integer (e.g. not real), which is sufficient.

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I didn't understand prob C. Could someone please explain me this problem

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

(a + (a*b*(a+1)/2))*(b*(b-1)/2)

Prob C — Div 2 By using above formula why i am getting WA http://mirror.codeforces.com/contest/476/my#

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

    long long?
    Btw — look at the link you've attached. There is "my#" in the end. Is this what you wanted to link :)?

»
10 years ago, # |
Rev. 2   Vote: I like it +20 Vote: I do not like it

Is there a bug with the rating? It looks weird ._.

»
10 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I apologize for a re-post but i can't understand why this summation works for Div1-A/Div2-C ![ ](Image and video hosting by TinyPic)

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

    seeking answer to same question....

    Why this summation works/how one has come up to this summation??

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

    and . So expanding that summation will give the exact formula as the one in editorial.

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hm...please tell me where is my mistake in div2b? (wrong test 11 after all formatting)

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Div I problem E: an almost same but stronger version of this problem:

http://mirror.codeforces.com/gym/100162/problem/I

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

    This problem can be solved with O(m n log n) with simpler idea and implementation in comparision with Div.1 E.

    • »
      »
      »
      10 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      en,yes,but there is one issue to write this kind problem to contest,if someone has solved the weak version with (n+m)*log(n) approach, he or she can copy previous code and submit in contest,and (I say just in theory) some red coder has opportunity to copy others code in the contest

      • »
        »
        »
        »
        10 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        In fact, there is a more similar problem on regular Codeforces round: Codeforces Round #154 (Div. 2) pC I have considered the case you mentioned. But I think the implementation of this solution is complicated and boring so nobody would implement it before CF272. I cannot deny the risk of providing this problem as pE.

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

        And you always cannot expect a problem nobody solved it before. In fact, I think I can arrive high rating at Coeforces or Topcoder just because there are many contest problems I had written in past.

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

          er... I think you misunderstood what I mean"write problem to contest", I'm not meaning solve problem ,I mean set task for others to solve. I haven't seen you as problem writers for many times

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

            I think I understand what you say correctly. As a writer, I always hope my problem to be the same with other old problems. But usually I can still see other people say he create the same problem before.(I am so sad that see somebody say he set the same problem before with my SRM629 Div 1 hard. OAQ).

            At least I think the idea of the problem pE is far away from the problem you mention. But it seems you don't think so. The only thing I can say is very sorry.

            I am eager to create totally original problems OAQ.

»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm trying to submit a solution to the Div2 E problem, but I'm repeatedly getting WA on the first test case itself, even though my code is giving correct answer for both the sample test cases on my machine. Here's one of my submissions for reference. TIA.