The editorials had been very fast lately

Great editorial! :)

Is there a term for binary numbers that fill in all 1's when xor'd? For example 11000 xor 00111 is 11111 so they fulfill this property.

I think if such numbers have a name problem B relies on this idea.

I can't believe B turned out to be so simple, I didn't realise it said "at most k"

I think you made a small mistake — the complexity in E is O((D(A) + D(B)) * log(D(A) + D(B)) * log10¹⁸)

Can someone explain the calculation of f(x, y) in problem D?

Very nice problem set! I hope to see more contests from you in future.

For problem D, how do you check if a cell (x,y) has already been visited in O(1) ?

Автокомментарий: текст был обновлен пользователем rek (предыдущая версия, новая версия, сравнить).

the contest was very good for me, but i don't think that was a standard contest.

because normal Div.2 participants mostly solved problems A and B but in a standard contest, a normal participant usually solve 3 problems.

nevertheless thank you for the contest:)

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

In problem E, how could I estimate |D(A)|? Should I just do what I guest and check it?

( In the contest, I think the size might went to 10^9 or larger, so I didn't try to implement and check it. TAT

BTW, I think it's a good contest, thank you!

In problem D, how f(x, y) is formulated ?

Why isn't time limit for java 2x of C++ in codeforces, it is very painful to see same solutions running in C++ rather than in java, and this makes extremely difficult to pass solutions in java.

"Let N be our initial set. Sadly we cannot just generate D(N) since its size might be of the order of 8·10^^8". How did the you compute the number 8.10^^8 ?

Also, similarly, how did you come with the number O(log 10^^18 .(|Da| + |Db|)) ?

Thanks.

Can someone elaborate on the implementation details of the problem E?

The first thought is to send the first elements to A and the rest to B. However, this is not enough; in this case the approximate size of D(A) might reach 7·106 which is way too much to pass.

How do we know this?

What is the time complexity of the "count_le" function in xen's code?

"The first thought is to send the first n / 2 elements to A and the rest to B. However, this is not enough".

I did exactly that and it passed in around 1100MS: http://codeforces.me/contest/912/submission/33953122

GreenGrape is that a typo, or did I get lucky?

In problem C, isn't it easier just to add f(t) changes in map and then count ans after any change (choose max of them). And then output ans if f(t) == 0 after all changes or "-1" in another case. like this

For problem E: Can someone explain what's happening in the function "go" of the editorial solution? I understand that the primes are split between lp and rp, but I didn't get what the recursive function calls will do:

go(1, 0, lp, A);
go(1, 0, rp, B);

thanks for a nice editorial :) specially D and E !

Can't E be solved using bitmask?

I liked the thought behind E. It's all about optimizations!

some one interesting to problem B if you can choose "exactly" K numbers? obviously K=1 or 2 is like the ordinary problem

In problem " B " , in testcase #48 , n was 2^58,so answer should be 2^59-1(xorring 2^58 and 2^58 -1) but answer was 2^58-1 (when k=2)!! how!! also why different answers with log2() and log2l()... is it about (rounding off) of double value

For problem D, May I ask why this part || (f_a == f_b && a > b); is added in the compare function of solution 2? (f_a == f_b && a > b) and (f_a == f_b && a < b) both give AC and without these output do not match.I wonder why?

In D we can use another method. Let see that optimal area is convex (or approach to convex). For this reason we should find rectangle area with square >=2*k. For find it let move vertical or gorizontal bounders (what's is better).

in Tricky Alchemy problem,my algorithm was correct but in third test case, the output was correct but negative (-2147483648),i tried using long long,long double,int and it didn't work,any help?

"The first thought is to send the first elements to A and the rest to B. However, this is not enough; in this case the approximate size of D(A) might reach 7·106 which is way too much to pass. To speed it up we can, for example, comprise A of elements with even indexes (i.e p0, p2, ...) so that sizes of both A and B do not exceed 106 and the solution runs swiftly."

What's the difference? In both the case, one set will be of size floor(n/2), and the other will be of size n — floor(n/2). What am I missing?

Wonderful job with the editorial!!

So I've been stuck on E for a bit now (did this as a virtual contest and spent most of my time on it). I had a (I think) similar-ish idea. Instead of splitting the set in two I added one prime at a time, keeping track of the smallest k numbers one can make with the first m of the n primes. This (or at least my implementation of it) ended up being too slow. Is there a reason the DP approach is doomed to be too slow that I'm not seeing? Or is it likely just that my implementation sucks? Also (relatedly) I'm not seeing how to prove the O(|D(A)|+|D(B)|) part of the complexity? I suspect if someone would be nice enough to fill in this bit I'll see what I'm doing wrong on this problem.

GreenGrape , can you explain how do we get the numbers 8*10^8 (size of D(N) ) ... and also how do we get numbers 10^6 if we split N into A and B...

In this Code (rek): 33953146 what does cnt[at-1]+=0 and cnt[time-1]+=0 do? why to do += by zero

Can someone explain C problem ? I couldn't understand the tutorial and why cnt[at]--?

Just by practicing E, I managed to understand how two pointers are more efficient than STL upper_bound/lower_bound in merging results in sub-problems in a meet-in-the-middle problem. Never thinking that way before ;)

Many thanks for enlightening me ;)

For Problem E, I used a Accepted code run the second sample. But I found a problem ==> I print the rank of 98 and rank of 93, both of them are 17, In other word both of them satisfy the Problem E, But the right answer is 93, so I want to know why it is right that if both of number have same rank, Always choose the smaller one. ( It can control by changeing the detail in the binary_search )

Hope someone can understand what I say and help me solve this problem, thanks!!!

I have a shorter(/est) solution for Problem B

n,k=map(int,input().split())
if(k==1):
    print(n)
else:
    print(2**(len(bin(n))-2)-1)

For the second problem if we consider K=4 then we have chosen 2^p and 2^p - 1 that's all right but what about the other two numbers? How can you say that even including the other two numbers won't change the result?