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 5001000150022502500.
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.
So Few Contest Now a Days. Hope this Contest Will love Everyone .
your problems in last contest were awesome
Why? cause they were easy?
Easy, but interesting ideas. :D
I wish good luck and good scoring for everyone. :)
contest is coming :) finally !!!
You should brace yourself after contest, when system testing starts. But before just enjoy the contest
I'm waiting for another fight in comments under blog... ^_^
I think one is about to start http://codeforces.com/blog/entry/19173?#comment240780
Why no div1 :/
because no problems setters :/
finally new contest...
Чувствую будет классный контест!
Yes Yes...
You're right :

I wish you all good luck, but the 1st place is for me!!!!!!
It's not funny nor interesting to participate in a div2 contest and solve all problems and prove yourself, do that in div1!!
yea this is getting pretty ridiculous.
Bro, who cares about that? Do your best work and that's it!!!
contest after two long week , hope short and simple problem description with explanation of test cases :)
Agree with short problems not like this :
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.
we want div.1 contests
after long waiting! finally we have contest
Will the scoring be dynamic?
Scoring is not published yet.
Why they do not decide their scoring system and then post? ;(
Do you think that it's easy to determine the difficulty of the problems?
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?
Writing from Japan this time round ... where are you all writing from? :)
i am writing from my home.
(my home is in iran btw xD)
i am writing from your home too
Hey... i thought i didn't give you internet :
but she gave me . you know her ;)
.' i didn't give your sister any internet either
dont be rude :((
please stop annoying me man .'
you fight with me on different accounts xD and its really annoying
I dont have multi accounts like you :D ( Bellsama )
Oh...I missed the fight :/
are you sure he is bell sama?
russia, siberia, yakutsk.
It's Syria :D
US, from work, lol!
Rise of unrated s !!!
Your picture is very good ;)
so his/her user name :D
Delayed...
Delayed again!
It has become daily(contest) routine for CF :(
CF doesn't have contests every day...
Delay again! Unhappy( ˇˍˇ )
10 min delay again !!
Very original post http://codeforces.com/blog/entry/18896#comment238419
IKR
Thanks for delaying! Only now I am online :} .
UPD
The comment is hidden because of too negative feedback, click here to view it.
Very funny _
Thanks for delay. If there is no delay, I could not register.
Haha, me too, registered in the last 30 seconds.
It will be my first online round on CF, so I wish that it wouldnt be so bad... Good luck!
good luck everyone
Thanks.
More than three years ago, in April 2012, the same problem as E was created on my polygon account...
НАСКОЛЬКО же уёбищный контест.
Бомбит ? ))
What is pretest 4 in problem B?
How to solve C?
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))
Same logic, but didn't submit
Why FIXED is always <= max(a[1..n]) ? Thanks in advance!
If FIXED is bigger than maximum, then last operation for all numbers is multiply, so we can just divide all numbers.
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.
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[].
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.
Code
Ah I see, the "timer" trick to reuse array allows to avoid using map! cool
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.
That's really nice solution. I've tried to do something similar during contest, but couldn't :(. Thanks!
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.
Complexity is O(N * log^3(max(a))), so no more than 0.5 * 10^9 operations.
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]+=(nnum[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 precompute in O(N) the array nreach[i] = number of numbers which can reach i with only divisions, and precompute 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
I think you meant ans[k] = ans[k / 2] + (N  nreach[k])  nreach[k] for the last formula right?
Thanks, fixed.
How did you solved E ? I think there must have been a lot of different solutions.
E is sqrt decomposition?
Yes. And counting sort.
Or segment tree with lazy propagation:)
Could you elaborate?
I got stuck on the part on how you merge the buckets to get the final array. How did you do 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?
That was way simpler than lazy propagation segment tree.
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)
It means that once again we have a problemset where hardest problem can be easily solved with bruteforce...
Did you try worst case on this solution? I am surprised that an O(nq) solution will work with n=100000 and q=50000.
I tried this case:
n = 100000
q = 50000
s[i]: i%26 + 'a'
all queries:
1 n 0
Runtime: 2854 ms
Easy =)
Wow, That’s impressive! I can't do it yesterday :(
what is the testcase 7 in problem C it failed for me
3
540 540 541
the answer is 2
It's not this one. My program outputs 2 but still wa7
answer will be 3 for this test case
nope! 541/2 then *2
No, answer is 2:
540; 540; 541 > 540; 540; 270 > 540; 540; 540
holy molly .. didn't think of that sorry :(
Missed the same testcase :P
it's so bad felling when you find bug 1 minute before end
bad feeling if you can't fix it in 1 minute(before end)
more bad when you fix it and it still doesn't go and then you find it after 8 seconds(after contest).
Contest started time is not word If there are several possible answers you may output any of them. Why?
Problem B. Contest started time is not word. If there are several possible answers you may output any of them. Why???
At least allow me to submit!!!!!!!!!
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.
Huh, it fails now on pretest 10. Still not there.
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.
Why does my lazy propagation get TL? :(
12055344
12060842 the correct one. Your lazy propagation is wrong somehow.
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.
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 56 solution using STL on B problem, i have one unsuccessful challenge...
you could create 196 KB test size
100000
{1 1 1 ... 1 1}
Its not the same.. Numbers should be different.
you can use generator
like this
i don't know why my code is wrong????? http://codeforces.com/contest/558/submission/12058908
What's wrong with my code for Prob A? Getting unexpected behaviour :( Code
your code prints two extra lines before answer remove these lines:
That was for debugging(myself), it crashes on test case two, the iterator does not stop at the end(), rather it continues on :(
What about rating?
What order is calculating Ratings? N^3 would be finished until now.
it's a good contest although i can't solve d and e :)
After contest, I solved C with BFS. :D
Damm, y couldn't I figure it during contest time.
I don't like participating when it is only div 2 without div 1 because all those unranked users always distort the rankings.
Could anyone tell me that why all my submissions are skipped? Although they passed all the system tests
see this
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
Got Ac :)
مبروك
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