RetiredAmrMahmoud's blog

By RetiredAmrMahmoud, 9 years ago, In English

Hello Codeforces!

I'd like to invite you to Codeforces Round #312 (Div. 2). It'll be held on Tuesday, July 14th at 18:00 MSK.(notice the unusual starting time) and as usual Div. 1 participants can take part out of competition.

This is my second round after Codeforces Round 287 (Div. 2). :)

Great thanks to Maxim Akhmedov (Zlobober) for his great help in preparing the contest, Maria Belova (Delinur) for translating the statements into Russian, Mike Mirzayanov (MikeMirzayanov) for the great Polygon platform and Polygon's developers team for their hard work in enhancing Polygon system.

The scoring distribution will be announced later.

Good luck everyone and I hope you'll find the problems interesting. ;)

UPD1 Scoring distribution will be 500-1000-1500-2250-2500.

UPD2 Contest is delayed 10 mins. Sorry for inconvenience.

UPD3 Contest is finished. Thank you everyone!

UPD4 System testing finished. Congratulations to the winners.

You can find the editorial here.

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

| Write comment?
»
9 years ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

So Few Contest Now a Days. Hope this Contest Will love Everyone .

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

your problems in last contest were awesome

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

I wish good luck and good scoring for everyone. :)

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

 contest is coming :) finally !!!

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

    You should brace yourself after contest, when system testing starts. But before just enjoy the contest

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

I'm waiting for another fight in comments under blog... ^_^

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

Why no div1 :/

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

    because no problems setters :/

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

finally new contest...

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

Thank you AmrMahmoud.
Eagerly Waiting for your interesting problems...  

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

Чувствую будет классный контест!

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

I wish you all good luck, but the 1st place is for me!!!!!!

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

    It's not funny nor interesting to participate in a div2 contest and solve all problems and prove yourself, do that in div1!!

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

      yea this is getting pretty ridiculous.

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

      Bro, who cares about that? Do your best work and that's it!!!

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

contest after two long week , hope short and simple problem description with explanation of test cases :)

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

    Agree with short problems not like this :|||

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

      I'm still a noob but I feel as if how long a description is should not be very imporant. Although I do think the Clarity of the statement is very important.

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

we want div.1 contests

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

after long waiting! finally we have contest

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

Will the scoring be dynamic?

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

    Scoring is not published yet.

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

    Why they do not decide their scoring system and then post? ;(

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

      Do you think that it's easy to determine the difficulty of the problems?

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

        It's not easy, but I don't understand why authors always publish the scoring 5 minutes before the start of the contest? why not sooner?

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

Writing from Japan this time round ... where are you all writing from? :)

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

Rise of unrated s !!!

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

Delayed...

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

Delayed again!

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

Delay again! Unhappy( ˇˍˇ )

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

10 min delay again !!

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

Thanks for delaying! Only now I am online :} .

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

 UPD

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

The comment is hidden because of too negative feedback, click here to view it.

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

Thanks for delay. If there is no delay, I could not register.

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

    Haha, me too, registered in the last 30 seconds.

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

It will be my first online round on CF, so I wish that it wouldnt be so bad... Good luck!

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

good luck everyone

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

More than three years ago, in April 2012, the same problem as E was created on my polygon account...

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

НАСКОЛЬКО же уёбищный контест.

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it
  1. What is pretest 4 in problem B?

  2. How to solve C?

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

    C. We need to make all numbers to be equal to some FIXED value. FIXED is always <= max(a[1..n]). We can get only log^2(x) unique states from some number x, by dividing and multiplying it by two.

    Summary O(N * log^2(x))

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

      Same logic, but didn't submit

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

      Why FIXED is always <= max(a[1..n]) ? Thanks in advance!

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

        If FIXED is bigger than maximum, then last operation for all numbers is multiply, so we can just divide all numbers.

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

      You get log^2 states for some number, but how for any other number you calculate the minimum number of ops to get to a particular state? I mean the straightforward approach is log^4 which is obviously TL, I used some sorting on log^2 (so O(log^2 * loglog)) and it also TL'ed — on my laptop it was 1.6 sec on max test.

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

        I have array cnt[] and sum[]. cnt[x] is how many numbers of a[] can get the state x, and sum[x] is sum of all minimum number of operations.

        For the current number a[i], I get all possible states and update cnt[] & sum[].

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

          For the current number a[i], I get all possible states and update cnt[] & sum[].

          This could not be done with simple two "for" loops? I mean for each state you need to know the minimal number of operations to reach it.

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

          Ah I see, the "timer" trick to reuse array allows to avoid using map! cool

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

          Thanks, that really helped. This is by far my favorite problem so far in codeforces (I've only competed 5 times), I was thinking for it for an hour and I made a lot of progress but never enough to make something implementable.

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

          That's really nice solution. I've tried to do something similar during contest, but couldn't :-(. Thanks!

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

    I solved C this way:

    1) Converted all A to binary representation (e.g. 111000111)

    2) Found maximum prefix that is the same for all A (e.g. if we have 10100 101000 1010000 max prefix would be 101)

    3) Tested all possible solutions and find the min result:

    step 1. Take prefix, test it as a possible solution

    step 2. Add zero to the right, test it as a possible solution. Repeat until max possible length reached (=max lenght from all A)

    step 3. Cut prefix by one number from the right (if it was 101 it becomes 10). Go to step 1. Repeat until prefix is gone

    Probably there are a proof that one of these possible solutions is minimal, but is it ok to test them all.

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

      Complexity is O(N * log^3(max(a))), so no more than 0.5 * 10^9 operations.

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

    My approach was to find the largest number in the array, and looping over how many divisions I applied to it(from 0 until the number equaled 1). Then I found the "distance" from that divided number to every number in the array. My distance function found the minimum number of changes needed to reach b from a by first finding all possible divisions of a(exactly the same as in the first part), and then applying multiplications until it equaled b. For example, if we had 23 to 10: 11, 5, 2, and 1 are candidate solutions, so we try each one. Keep applying multiplications by 2 to each candidate until you pass 10. 11 is already past 10, so just ignore it. Multiplying 5 by 2, we get 10, so the solution would be 3(two divisions and one multiplication).

    So just for each division of the highest number in the array, calculate the sum of the distances from each array element to this division. Return the minimum of these sums.

    Nevertheless, I got WA on test case 7 :P

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

    Alternative nlogn solution for C:

    Keep two arrays for each number x=1,...,10^6 — the number of original a[i] that can reach it (num[x]), and the minimum total number of steps required (req[x]).

    Then, first only consider the "divide by 2" operation, and for each a[i] update the values accordingly.

    To account for the "multiply by 2" operation, iterate up from x=1,...,10^6. First do check if this number works — num[x]=n — and update the answer. Then, "multiply" every number here by 2 — look at num[x*2], and we get req[x*2]+=(n-num[x*2]) + (req[x]-(req[x*2]+num[x*2])).

    Total O(nlogn)+O(n)=O(nlogn).

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

    Here's another O(N log(N)) solution for C (which can be made O(N) with a simple modification).

    Let ans[i] be the number of moves to reach the state where all numbers are equal to i.

    Also, notice that any minimal sequence of moves for one number consists of some number of divisions, followed by some number of multiplications.

    Now suppose that we have ans[k / 2] and want to find ans[k].

    Case 1: k is even.

    Every number i that cannot reach k with only divisions must end its sequence of moves i -  > ... -  > k with a multiplication k / 2 -  > 2 * (k / 2) = k, so it requires one more move to reach k than to reach k/2.

    Every number i that can reach k with only divisions must pass through k on any minimal sequence i -  > ... -  > k / 2, so it requires one less move to reach k than to reach k/2.

    Case 2: k is odd. By the above logic, the final number can only be k if every i can reach k with only divisions: a multiplication by 2 can never end up at k. If this condition is satisfied, we proceed as above; if not, we mark k as impossible to reach.

    Thus if we pre-compute in O(N) the array nreach[i] = number of numbers which can reach i with only divisions, and pre-compute in O(N log(N)) or O(N) ans[1], we can calculate ans[k] for all values of k in O(N) with the formula ans[k] = ans[k / 2] + (N - nreach[k]) - nreach[k].

    O(N log(N)) code: 12059157 O(N) code: 12060248

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

      I think you meant ans[k] = ans[k / 2] + (N - nreach[k]) - nreach[k] for the last formula right?

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

How did you solved E ? I think there must have been a lot of different solutions.

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

E is sqrt decomposition?

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

    Yes. And counting sort.

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

      Or segment tree with lazy propagation:)

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

      I got stuck on the part on how you merge the buckets to get the final array. How did you do it?

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

      yes,i'm the method with you..(i caculate the range to 2e17),but the judge result is always wrong answer on pretest 7 , but i really do not know why there is a mistake , can you help me?

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

      That was way simpler than lazy propagation segment tree.

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

    I solved it using a lazy segment tree.

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

    I used a set that keeps contiguous segments that are all the same letter. For a query I possibly create two new segments (on the border), then sort the segments within the range and combine, so I have at most 26 segments in that range afterwards (one for each letter). Nothing complicated :)

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

    When I attempted to challenge others, I found a quite easy method. We can record sorted list of all occurred positions for all lowercase letters. Then for each query, we binary search to find which range of positions will changed for each letter and change them to new positions. The complexity is O(nq). It's quite safe to c++ in limit of 5 seconds. (x)

    Note: After I did some experience, some O(nq) algorithm such as counting sort is not easy to pass...(still get TLE)

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

      It means that once again we have a problemset where hardest problem can be easily solved with brute-force...

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

      Did you try worst case on this solution? I am surprised that an O(nq) solution will work with n=100000 and q=50000.

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

        I tried this case:

        n = 100000 q = 50000

        s[i]: i%26 + 'a'

        all queries: 1 n 0

        Runtime: 2854 ms

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

      Note: After I did some experience, some O(nq) algorithm such as counting sort is not easy to pass...(still get TLE)

      Easy =)

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

what is the testcase 7 in problem C it failed for me

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

it's so bad felling when you find bug 1 minute before end

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

    bad feeling if you can't fix it in 1 minute(before end)

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

      more bad when you fix it and it still doesn't go and then you find it after 8 seconds(after contest).

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

Contest started time is not word If there are several possible answers you may output any of them. Why?

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

    Problem B. Contest started time is not word. If there are several possible answers you may output any of them. Why???

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

At least allow me to submit!!!!!!!!!

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

Nice contest. Task D is very nice. Haven't solved it — first failed on pretest 6, then 7, then 8 lol. Right after contest finish found one more stupid error in my Cut method. Anyway, it is a nice problem and overall nice contest, thanks.

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

    Huh, it fails now on pretest 10. Still not there.

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

E without sqrt decomposition and without lazy propagation:

For every letter let's keep intervals in a word with this letter. How? I did it with c++ set. For word abaab letter 'a' has intervals [0,0] and [2,3]. How to process a query with range [low, high]? For every letter let's remove its occurrences in [low, high] and count how many occurrences of this letter did we remove. Note: for some intervals we only cut them, not remove. Then for every letter in increasing or decreasing order we add one interval (e.g. for 'a' interval from low to low+count['a']). We add O(26) intervals in each query so number of removed intervals in previous part will be amortized O(26*q). Total complexity is O((q+n)*26*log(n)). Log because I use set.

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

Why does my lazy propagation get TL? :(

12055344

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

    12060842 the correct one. Your lazy propagation is wrong somehow.

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

      It isn't wrong, it is just slower by a constant factor...

      Here is original version with small optimization which gets AC: 12059185

      Anyway, thanks for help, I like your simplier version! Didn't realize that it is only assignment on the segment, not assignment + addition.

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

Why i cant hack solutions with test with size over 256kb... I must decrease test twice, because of this limit, and solution passed my test, but timelimits on maximum test.... Now instead of i hacked 5-6 solution using STL on B problem, i have one unsuccessful challenge...

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

i don't know why my code is wrong????? http://codeforces.net/contest/558/submission/12058908

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

What's wrong with my code for Prob A? Getting unexpected behaviour :( Code

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

    your code prints two extra lines before answer remove these lines:

    cout<<in->apples<<endl;;
    
            cout<<ip->apples<<endl;;
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That was for debugging(myself), it crashes on test case two, the iterator does not stop at the end(), rather it continues on :(

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

What about rating?

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

What order is calculating Ratings? N^3 would be finished until now.

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

it's a good contest although i can't solve d and e :)

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

After contest, I solved C with BFS. :D

Damm, y couldn't I figure it during contest time.

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

I don't like participating when it is only div 2 without div 1 because all those unranked users always distort the rankings.

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

Could anyone tell me that why all my submissions are skipped? Although they passed all the system tests

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

Is anyone one help me for find my bug in problem C.

I got lot of wa... and lastly got TLE.

But i don't understand why ???

My code: Code

By the way.. Nice problem , thanks =D

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

مبروك

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

For Div2C, (another $$$O(n\times m^2)$$$ solution):

Observation: We can never add a set bit by these operations. The number of set bits in a number can remain the same, (left shift), or decrease (in case of a right shift). So we should look at the numbers that have the minimum number of set bits in them. We can use __builtin_popcount for that. We do so, because in the end all the numbers must have equal value. So the bits must be equal too. So, since you can't increase the number of bits, the numbers generated by the numbers that have the minimum number of bits are the ones which are needed to be checked.

Amongst the numbers which have the minimum number of set bits, we take the one which has the minimum value (rightmost MSB). Let's call it $$$j$$$ This is selected because it is easiest to decrease the number of set bits from it.

Now you generate every number from every number, and count the total number of operations needed to generate it, plus a check, whether the number is generatable from every number in our array.

Now, we check every number $$$K$$$ generated by $$$j$$$, if $$$K$$$ is generatable from every number in our array. The minimum number of operations are output as the answer.

Here is my submission