Блог пользователя drazil

Автор drazil, 10 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +253
  • Проголосовать: не нравится

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится -48 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится +80 Проголосовать: не нравится

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 лет назад, # |
Rev. 2   Проголосовать: нравится +23 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

    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 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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

Because screw weekends

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

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

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

»
10 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

what a nice contest time :)

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Oh I forgot registering contest.. :<

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +44 Проголосовать: не нравится

Goodbye red color :(

»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Who else failed A because of long overflow

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +62 Проголосовать: не нравится

    Are you happy with math problems?

  • »
    »
    10 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +22 Проголосовать: не нравится

    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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

how to solve B -div1 ??

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      missed it completely ...thnx

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Why 6i ???

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        See here

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

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +29 Проголосовать: не нравится

        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 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          why 6 !!!

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

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

          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 лет назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

92anurag was the first to ask.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Как С (div 2)/A (div 1) нужно было решать?

  • »
    »
    10 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    cout << (((((((a*(b-1)) % M) * 250000002) % M) * b) % M) * ((a*b + b + 2) % M)) % M;

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится -39 Проголосовать: не нравится

    Брутфорс->ищешь закономерность. Контест — треш

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Там есть формула, тупое решение за a * b, все, что нужно было сделать — сделать его умнее

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        Я пробегаюсь по всем k, плюсуя к результату сумму арифметической прогрессии, например.

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Я сделал так же, но при чем здесь закономерность?

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Я вывел формулу, полтора часа втыкая в брутфорс и переписывая его.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Explanation for problem C Div2?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    for (mod = 1; mod < b; mod++) 
    res += mod * b * a(a+1)/2  + mod * a
    
    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

            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 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

              • »
                »
                »
                »
                »
                »
                »
                »
                10 лет назад, # ^ |
                Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

                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 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

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

        (ll) expected, but (double) found

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

    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 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    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 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

Very interesting problems! Thanks to authors!

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

div 1 C без дерева отрезков\фенфика зайдет в ТЛ? Ясно что за |S|^2 находим отрезки из которых можно вырезать p, потом перебираем x, берем самые дешевые отрезки, которые не пересекаются, а потом нужно проверять пересечение и отмечать, можно ли делать это за линию?

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This is my submission on A Div.1: 8203037

What is wrong with my expression?

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 лет назад, # ^ |
              Проголосовать: нравится +8 Проголосовать: не нравится

            there is precalculation of |S|*|S|

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

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        But its only O(n^2).

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Первые 40 минут контеста решал задачу (и решил) с формулой

a * div(x,b)/mod(x,b) = k

Не знаю, чего здесь больше: моей глупости или плохо написанного условия. Но и то, и другое имеет место. Не надо так :(

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

Which numbers should be added?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Just write a brute force ....

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hello !

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

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

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    ((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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Changed

const int N = 2e3 + 2;

to

const int N = 2e3 + 3;

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve div1-C?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится -25 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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 лет назад, # |
Rev. 2   Проголосовать: нравится +28 Проголосовать: не нравится

Thank drazil for this interesting contest!

»
10 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится +61 Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

(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 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

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

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

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

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    seeking answer to same question....

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 лет назад, # ^ |
              Проголосовать: нравится +8 Проголосовать: не нравится

            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 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.