Why? cause they were easy?

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

I think one is about to start http://mirror.codeforces.com/blog/entry/19173?#comment-240780

because no problems setters :/

Yes Yes...

You're right :|

-

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

Agree with short problems not like this :|||

Scoring is not published yet.

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

i am writing from my home.
(my home is in iran btw xD)

russia, siberia, yakutsk.

It's Syria :D

US, from work, lol!

Your picture is very good ;)

It has become daily(contest) routine for CF :(

Very original post http://mirror.codeforces.com/blog/entry/18896#comment-238419

Very funny -_-

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

Thanks.

Бомбит ? ))

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

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.

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

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

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

Yes. And counting sort.

I solved it using a lazy segment tree.

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

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)

3
540 540 541

the answer is 2

Missed the same testcase :P

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

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

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

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

you could create 196 KB test size

100000

{1 1 1 ... 1 1}

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

cout<<in->apples<<endl;;

        cout<<ip->apples<<endl;;

see this

Got Ac :)