allllekssssa's blog

Codeforces Round #307 (Div. 2)
By allllekssssa, history, 9 years ago, In English

Hello Codeforces community !

I am glad to announce Codeforces Round 307 (Div. 2) on 12th of June at 19:30 MSK. Authors of this contest are Nikola Mandic (nikola12345) and Aleksa Plavsic (allllekssssa). This is our first round and we really tried to make interesting and solvable problems. Traditionally Div.1 participants can take part out of the competition ( personally I believe that the problems are worth to Div 1 participants, and nobody can solve everything in 20 minutes ). This is the first Serbian round and we want to invite our friends from Serbia to take part in this round and maybe prepare some of next rounds.

The main character of this round is gonna be GukiZ ( our proffesor of computer science ). He really helps us to become better people and developers !

We want to thank Zlobober for help in preparing contest and great advices, Delinur for translating problems statements into Russian and MikeMirzayanov for fantastic Codeforces and Polygon platform !

We wish you great fun, a lot of Successful hacks, Accepted solutions and high rating !

UPD: Scoring distribution: 500 — 1250 — 1750 — 2000 — 2500.

UPD2: Due to technical reasons round was delayed by 10 minutes. Stay tuned!

UPD3: +5 minutes. Thanks for your patience!

UPD4: System testing is complete, but the rating update won't be that fast since we are working on improving our cheater catching system. Thanks for your understanding!

Congratulations to winners!

DIV 1:
1.MrDindows

2.kennethsnow

3.ecnerwala

4.I_love_Tanya_Romanova

5.Hasan0540

DIV 2:
1.hrzhrz_hrzhrz

2.slo

3.wangjing

4.cyber_tourist

5.Moose_Lee

Thanks to all participants. We hope you have a good time and learn something new.

UPD5: Link of editorial !

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

Comments Comments (208)
| Write comment?
»
9 years ago, # |
  Vote: I like it -33 Vote: I do not like it

Okay, let's be finally realistic here: This time I will either jump into Div.1, or I will not.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

I wish good luck to all participants.;)

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

It clashes with Codechef Snackdown is it possible to shift it ?.

http://snackdown.codechef.com/schedule

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

    if you prefer a codechef round to a codeforces round I think...

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

    dont worry codechef will be loading while this contest happens :)

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

    Too bad you can't do both.

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

      I will still try to participate in both

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

        Not a good idea according to me, but then maybe YOU can :)

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

        I am such a fool that I waited for codechef snackdown elimination mirror to start till 11 pm, but didn't noticed that official elimination round had already started at 9:30 pm. I noticed it only when I was not able to submit any solution in mirrored contest. This big mistake has costed me 3+ hours of penalty time due to which my rank went beyond 700. If I hadn't made this mistake, my rank would be under 300 and our team would have got T-shirt and would have qualified for finals.

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

          Life can seriously betray you sometimes like this.

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

i might not be red but i can host a contest and i will do it .... best of luck

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

It looks like we will have harder division 2 contest than usual. Hopefully it will be not too hard ;)

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

Congratulations on your first round! Zelim sve najbolje

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

( personally I believe that the problems are worth to Div 1 participants, and nobody can solve everything in 20 minutes ) May I shout out tourist and run away?

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

Really look forward for this contest! allllekssssa helped me a lot to understand problem's editorial with his solution (back when I used to only know Pascal).

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

First Serbian round! Congratulations setters. :)

One day, we'll have an Indian round too. And I'm looking forward to that day with excitement. Hope it comes soon.

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

Thanks guys ! I hope that we will justify expectations !

We have solutions in Pascal and after contest we will put it in Editorial.

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

    I hope you also have solutions in C++ and Java, to prevent the TL (java) or naive solution due to your time constraints
    P.S. Today in Russian Federation celebrates the Day of Russia :)

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

Challenge for tourist: Solve all problems in 20 mins

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

    I talked with him ! He can't do competition, but he can do virtual contest anytime. Also same chellange can be for Petr, vepifanov and other top participants...

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

If the problems are so hard, how do you expect div 2 participants to enjoy the round?

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

I hope that the problems will be on different topics ...

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

"a lot of Successful hacks" :/ I guess this line is not pleasant for me. every-time I saw it on the round announcement, one of my sol got hacked just before the contest end. and when I try to hack someone else's sol I fail.

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

Auto comment: topic has been updated by allllekssssa (previous revision, new revision, compare).

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

"( personally I believe that the problems are worth to Div 1 participants, and nobody can solve everything in 20 minutes )"

it appears that problem statements will be lengthy and (especially) problems A and B will be implementation problems with lot of cases and variables to handle, that may make these problems, easy but time taking problems.

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

the earliest scoring distribution ever .

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

Hi, this is the first time I will participate out of competition. I want to know if my rating will be affected.

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

I'm surprised by the scoring! It seems that we're gonna have a harder B than usual... :)

Good Luck

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

I want to get out of the green zone towards blue and purple .

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

will, I wish to get accepted as possible because I got enough of digging in the newbie area ..

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

    Once I was also deep in newbie, but through regular practice I have managed to participate 5-6 times in Div — 1 (candidate master). One day you will also enter Div — 1 by learning DS and algo, regular practice and by making, "up-solving", your habit.

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

Seen 5000+ (and still counting) registrants for the first time in Div 2 only contest.

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

    There is 4532 Participants actually, all others are participating unofficial

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

And its delayed....

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

The best option : Switch back to Snackdown... :)

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

Damn I hate Delays

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

    Come on! 5 more minutes?! I have a chemistry exam tomorrow.

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

~800 unrated participants :3

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

    At least they're fair enough to participate with their real account (^_^)

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

    5578 — 800 = 4778

    ~4778 rated participants Oh My God I'm very Clever

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

      this is more correct
      5500 — 800 = 4700

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

        why is this more correct? :p

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

Great. People, we have yet another delay (+5min this time) :(

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

In Russian, please.

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

Good luck have fun.

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

What The Fuck happened?? why these delays??

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

Soon contest announcements will have "due to technical reasons, round will actually start on time. Thank you for your understanding!"

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

Really this last delay?

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

heeyy , you are not codechef

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

10 + 5 + 2.5 + ... it's gonna be 20 mins...

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

It's 1:41 a.m. here in Korea.. Delay means less sleep to me T_T

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

00100011 00100110 00010000 00010011 00010011 00010000 00100100 00100011

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

4859 rated contest registration !!! I this its a new record For Div — 2 :D

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

Are you sure it's for DIV 2 ???

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

Remove problem A, and it becomes Div1 Only

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

    B was probably too easy for Div1 too, but others are ok.

    Spent last 70 minutes on D, almost come to the solution, but lacks of knowledge in combinatorics. Also can't get how to do fast 2^(bignumber) mod 10^9+7.

    I've came up to formula: 2^(n * total_bits — 2 * (bits1pos1 + bits1posn) — 3 * (bits1pos2 + ... bits1posn-1)) for each combination of bits1pos1 ... bits1posn-1 where thier sum = amount of bits with value 1 in K.

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

      2^N mod 10^9+7 is actually quite simple, and can be done in O(logN). All you have to do is exploit these two properties,

      1) (a*b) mod m = ((a mod m) * (b mod m)) mod m.
2) For an even b, (a ^ b) = (a ^ (b/2) ) * (a ^ (b/2)),
   and for an odd b, (a^b) = a * (a ^ ((b-1) / 2)) * (a ^ ((b-1) / 2))
      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ah thanks! So its just usual fast power but with mod addition... So easy :)

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

This contest was too easy

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

    u know that there are total 5 problems in the contest ri8 and not one !! :p

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

      don't argue with me it was pretty easy (Face with sunglasses)

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

    maybe no body understands sarcasm that's why i decided to leave a post here for u guys to know that i'm obviously being sarcastic ...

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

    Was this serously a div 2 contest? 130 accepts on C 50 Accepts on D and 25 Accepts on E

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

      Possibly you have seen "unofficial" standings. In official Div 2 standings stats are like this:

      A->2622 B->416 C->43 D->4 E->6

      so I think it was slightly harder Div 2 contest

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

Thank you for this great round! (no sarcasm here) I've never thought that Div2 rounds may be that tough ;)

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

Both announcements were so obvious and useless.

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

How can we solve problem C??

was it a DP?

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

    It can be solved using binary search. If we fix time, we can use greedy to put students from left to right and then compare it to M to check, whether it's possible to make it with this time

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

      That is a great idea but could you explain the greedy part in more detail?

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

What could be pretest 12 for B?

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

    I could provide a tricky case that let me pass pretest 12

    input:

    aaabbbcd
ab
bcd

    output:

    abababcd

    here the maximum is 3 which is ab, ab, ab 3 times not bcd..

    this implies when you the possibility of adding string b as well as string c, choose the one with minimum len.

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

      My solution passes this test case, but failed #12 on pretests. I don't think they are related.

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

      I am getting "bcdababa". Why is it wrong?

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

        when u get bcdababab u are first including string with larger length that is string c, and adding the rest afterwards, while you need to first focus on adding the strings with smaller length if you have the opportunity to add any of them( either b or c).

        this works as a tie breaker.

        UPD: and as a result will increase answer by a significant amount.

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

      I've got fault on test 12 too and I used that idea about minimum length. And input strings for this test is too long and all I can see is that an optimal solution maximum is 133 and my 129...

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

      This is wrong, actually.

      Consider a = "aefaefaef" (3 times aef), b = "aa", c = "aef". If you make the shorter string while you can you'll get 1 "aa" and then you'll have just one "a" to make one "aef". So you'll have one "aa" and one "aef" in total. It can be easily seen that one can make "aef" 3 times, though.

      I made the same mistake at first but then figured out it's not always true :). Unfortunately couldn't debug on time the other solution I came up with.

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

        hey u are absolutely correct..

        actually breaking tie on length is the 2nd tie breaker.

        first you need to add the string one time which can be repeated max number of times.

        if in this both the strings can be repeated same number of times then you need to break tie on length of strings.

        See my submission 11550880

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

      My solution also passes this case(same output as you)!! But it can't pass case 12!!

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

    I don't know, but try these testcases:

    ==> in <==
ababc
bc
ba

==> in2 <==
ababac
abac
ba

==> in3 <==
abaabaabacc
aba
ca
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Answers?

      I am getting: 1 — babac 2 — abacba 3 — cacaabaabab

      Do I have anything wrong?

      Thanks in advance!!!

      UPD: No idea why my solution is failing!

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

        Your output looks correct to me.

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

        Your answers seems correct.

        My own solution passes the #12 pretest (have no problems with it), but failed with runtime error on #23. Yet haven't find the error, but probably it caused by bad i/o, haven't read such a long strings before, not sure about that.

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

          Huh, found error. Its when neither of b and c is substring of a. In my code it was uninitialized result, so it failed on print.

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

      For your second test i get: babaac and it have 'ba'+'ba'+ac = 2. And the answer for deinier was abacba and it is 'abac'+'ba' = 2. what is the criteria in tie case? My solution can't pass test case 12.

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

    Input: aaaaaabbbbbb aba bab

    Output: abaabababbab

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

Looks allllekssssa is fan of PrinceOfPersia

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

I have solved 2 problems A and B :))))

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

These cases with L=0&M=1 for D which are not included in pretests... Pure cruelty :)

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

    Have to agree with you. I feel lucky that at least there was a pretest in which K >= 2^L. It was then that I realized that there were special cases (including those you mentioned above) :P.

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

      I am not as fortunate as you. That was the only corner case I handled :'( I though I had it in the bag but missed 2-3 corner cases :'(

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

    I've got one more personal rule: never use constants without MOD inside modular arithmetics code.

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

What's behing B's pretest 12 ?

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

    Maybe something similar to this..

    Input:
    aaaaaabbbbbb
    aba
    bab

    Output:
    abaabababbab

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

How to solve D?

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

    you just need to calculate how many binary numbers with length l,where no 2 1bits together.this all is fib(n+1)*x+(2^l-fib(n+1))*y,where x=number of 1 bits in binary representation of k and y=number of 0.

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

      Not sum, but product, I think, no?

      Fn + 1x(2N - Fn + 1)l - x

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

        hey how did you come up with this formula involving Fibonacci numbers.

        Is it some less common standard formula or something else?

        Thanks in advance. :)

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

          To create digit 0 from N numbers we will start with the first one it can be either 0 or 1 in this digit. The next one can also be 1 if and only if the first is 0, and can be 0 in any case. Now we have three case:

          0 -> 1 : the third must be 0;

          0 -> 0 : the third can be 0 or 1;

          1 -> 0 : the third can be 0 or 1;

          The number of the allowed zeros equals the number of all cases in the previous number.

          The number of allowed 1 equals the number of allowed zeros in the previous number so it equals the number of all cases in the number before the previous number.

          So the number of ways to construct zero is a Fibonacci sequence: 2, 3, 5, 8, 13, etc;

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

          There is log(N) code for precise Fibonacci numbers. It is discussed here in Russian. See my submission 11558240

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

        yes right,you should write dp solution and you will find formula yourself

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

          okay the recurrence is the key.. which I believe would resemble the Fibonacci recurrence.

          thanks for replying :)

          → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

.

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

    It is a usual problem of last 5 minutes. Live with it.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Very disapointed because of lags on the site at the end of the contest. Was not able to submit my D problem in time because of too long response of site.

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

the contest ended before time i couldn't submit in last 5 mins constantly got cf is unavailable :(

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

On this contest I've intentionally solved A in C++ and D in Java to get the achievement "Polyglot" on this site (there was a blog post about it). Now my only hope to get it is to have A && D passed systests :)

UPD NOOOOOO, my D solution has failed system tests :(

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

Nice Round :)

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

Worst contest in CF history.

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

    Be positive.

    Tasks was interesting, tests was ok. Maybe a bit hard for Div2, but definitely not bad contest.

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

      When there are 761 out of contest (div1) competitors and only 160 correct solutions for C there is something badly wrong... Definitely crosses from good to bad.

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

    Writer with lower rating (like purple) tends to underestimate the difficulties of the problems, having fear to be regarded as too easy by contestants, and the problems actually become harder than usual.

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

      Maybe so, but we have Zlobober for such problems :)

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

Test cases of Problem B are fun to read. For eg.

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

I have totally misunderstood B, I was searching for maximum length of concatenated substrings instead of maximum number of substrings and besides that I have passed 12 pretests :D

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

I hate this contest because this contest Ever not Normal and very hard ):

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

which data structure needs to E?

→ Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Why O(|a| * 26) solutions on problem B gets TL54?

UPD.Answer here

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

What a shit contest , fucking aweful :) allllekssssa dont creat contests anymore

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

It was quiet contest for Div.2 participants.

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

Prob C : Is this a valid test case 4 1 2 3 0 0 Ans : 8 If so should be a good hack !

→ Reply
»
9 years ago, # |
← Rev. 20   Vote: I like it 0 Vote: I do not like it

Rating should be given too much late. Follow topcoder's Rating system.

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

Thanks to authors for good problemset!

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

    It's good only for div1 not div2.Bcoz it was rated only for div2 and most of the contestant don't solve problem more than 1. problem A and problem B are huge difference.

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

      So, do you want to stay in Div2 forever? You should be able to solve problems like this to get higher in ranks, imo. And this contest was the one, where speed was really important, for example if you managed to solve A only. The problems were quite nice, looking forward for such challenging round further on.

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

Thanks for the nice problems. Best Div-2 only contest in a while.

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

Can somebody help me out here? My submission 11555558 for B gives MLE.I have no idea why.I use O(|a|) memory according to me.

And now problemset wouldn't open to check.

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

I think problem statement's are shit!!

What is the approach for B ??

I tried to find as many of string b as possible and then as many string c, and i tried c then b and printed the one with max non-overlaping substr and didn't work.

this is my code

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

    I did the same and it passed. Ok I am joking,it didnt :). I am really curious to explain us a better programmer the reason.

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

    Brute force solution: try all possible counts of b and calculate count for c. Find the case with max sum of counts for b and c.

    11550107

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

      I had troubles solving B, but even had an idea like this, but thought that it is going to TL. Your solution seems clear to me, thanks alot for explaining!

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

    Did exactly the same. I believe there might be a case that fails it, but I couldn't come up with it during the contest, so submitted, and got wa on #12.

    It's a very long pre-test, so it's hard to see where your solution goes wrong, I hope the author can explain why this approach fails. ( or someone else).

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

      Maybe something similar to this.. Input: aaaaaabbbbbb aba bab Output: abaabababbab

      Here I found it from a user above in the comments. Here we fail :P

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

    Binary search:

    Let N be a number of non-overlapping substrings in string a, that are equal to b or c. We want to maximize this number.

    Here is the main idea


    lo = 0   // the answer should be at least 0
hi = a.length()+1  // the answer can't be larger than a.length()
while (hi - lo > 1) 

    N = (hi + lo) / 2
    doesThisNWork = false
    for each numberOfStringBinA = 0 ... N
       let numberOfStringCinA = N - numberOfStringBinA
       good = true
       for each character ch = 'a' ... 'z'
           if ( (number of ch in string a) <
                 numberOfStringBinA * (number of ch in string b) + 
                 numberOfStringCinA * (number of ch in string c) )
                 good = false
       if good
            // we found a way to make numberOfStringBinA b's and
            // numberOfStringCinA c's in string a.
            doesThisNWork = true
    if doesThisNWork
         lo = N
    else
         hi = N
    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ya I did the same But it will not contain all the case example aaaaaabbbbbb aab abb If you go by your approach then the answer would be B: 3 & C: 0 then C: 3 & B:0 which will both give you 3 as final answer whereas the final answer would be 4 B:2 C:2 So you have to take cases like this in consideration

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

Auto comment: topic has been updated by allllekssssa (previous revision, new revision, compare).

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

most rating will be decided by how fast we solve problem A

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

If you have TL54 in B, check int values.You should use long long. Maybe you have such lines with mistake:

 for(int i = 0; i <= sz(a); i++){
    bool ok = true;
    for(int j = 0; j < 26; j++)
      if(tmp[j] - i * usedB[j] >= 0)
        tmp[j] -= i * usedB[j];

You have i <= 1e5 and usedB[j] <=1e5. i * usedB[j] <= 1e10.

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

    Thanks a lot ! Finally i understood where i went wrong !

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

very nice problems . tanks lot!

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

Can anyone tell me why my code was too slow for problem B? http://codeforces.me/contest/551/submission/11556052

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

First time reading C, D, E...

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

What is the expected complexity for problem E? Tell me it's better that ...!

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

For the problem B i used this idea:

Let a,b,c the input strings
Let x the amount of only strings b in a.
ans = 0
Now we can:
iterate for i=[0..x] 
   substract i strings from a. 
   let j = the amount of string c in the remain string. 
   if (i+j) > ans
       //save results
print ans;

I think this is the same that 
A >= i*(B)+j*(C)
where A,B,C are column vectors (from string a,b,c)

(sorry if it was incorrect. I am not good in maths) and we want the maximum value of: (i+j) How solve this math problem? thanks in advance

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

This is my first time using C++ in a contest, and I'm having the following issue.

The code for problem D runs correctly on my machine, but when I do the custom invocation, the answer always returns 0.

Any ideas why? Thanks.

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

Auto comment: topic has been updated by allllekssssa (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it +13 Vote: I do not like it 
Thanks to all participants. We hope you have a good time and learn something new.

Yes,those who are complaining dont want to learn anything and just want good ratings and easy problems

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

Obviously this contest was harder than usual. Specially B seemed to suit for C and C for D. Whatever, still great contest due to the beauty of the problems.

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

This contest was great! Many thanks to the authors.

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

Congratulations to the real winners!

Real Div.2 winners:

  1. slo

  2. sheep

  3. AICoderMike

  4. unkoman

  5. please_delete_account

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

    Indeed. I believe it's better to ignore unrated Div-1 participants while announcing the round winners. It just gives them more motivation.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +22 Vote: I do not like it

Just noticed the dreamoon_love_AA test case in B. hahaha

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +20 Vote: I do not like it

There are more funny tests. Like this:


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

    I wrote all the funny testcases. My friend has nothing to do with it :)

    Also I have a lot of funny comments on Serbian ( some comments are about my friend, teachers, or my 'good' english ). I hope nobody feels hurt. I relly hadn't bad intention with testcases !

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

      Is that typo on test #45? I don't know the correct one between grandpa or she. Btw, I'm looking forward for your Pascal solution as you mentioned :)

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

    I like testcase with Egor and tourist :)

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

Admins ,

I just wanted to say one thing that all these people who participate in their first contests and get into top 5 or top 10 must be banned ! These discourages others who are working to get in top 5 because of these genius div1 players who make fake profiles to just see where they stand in div 2 . For instance in this contest 4 out of top 5 players are those who are playing in their first match and now voila these geniuses are in top 5 :/

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

    Should Petr or ACMonster or vepifanov or rowdark or dreamoon_love_AA be banned? Codeforces isn't the only Online Judge in the world.People can practice in other Online Judges and then particpate in CF.

    UPD:In case of misunderstanding,I didn't say multi accounts shouldn't be banned(and I think unrated Div.2 winners in this round is from Div.1).All I say is banning all unrated Div.2 winners is not a good way to prevent multi accounts,I think.

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

It was a good contest.but I don't know why my B was not accepted. :\ :D good luck!

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

    As per previous comments above, your code won't pass the following test case:

    Input: aaaaaabbbbbb aba bab Output: abaabababbab

    It assumes that the maximum answer will occur when string b is taken out fully before string c, but the maximum can occur for 'interior' solutions where b and c are not fully removed.

    Fix: Find max number of times b can be removed, then iterate through removing 1 to max b's (and any remaining c's per case) and find the instance with largest sum of b and c removed.

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

I have no idea why this submission gets runtime error on codeforces but runs fine on my local ide and codechef. http://codeforces.me/contest/551/submission/12304739. Please check.

→ Reply