Fortunately the wish came true. Good problemset!

It will be posted not long before the contest starts, maybe.

(It is posted just two minutes before starts.)

Ok, ok I deserved it (-52)

During the contest of course, just like in regular rounds.

eights

happiness is a state of mind.

If you do not make a single attempt, it won't be rated for you. Otherwise it will be.

LOL what an attempt to get free upvotes

This comment has been edited and I sincerely apologize for my lack of knowledge about this great anime

Still cannot believe I lost this round...

Aha! I believe that there are only two sorts of people in the world, those who like JOJO, and those who don't know JOJO!

C feels somewhat hit-or-miss, if you're familiar with the trick behind it, it's a cakewalk, otherwise it'd take some brainstorm.

Oppositely I thought E was easier than D.

Weird flex, but D was extremely hard for me, lol

Did we have to use the fact that every integer from 1 to 2⋅n is mentioned exactly once anywhere in the solution? I think I have not used it anywhere in my soln. But its complexity is nlog(n) using segment tree. UPD: Got it.

i felt is was easier than B also.

One case I can think of is an array with all elements equal(of size 60 or so) and maski has the ith bit set.

No. Suppose that we have one object for each mask with exactly two bits set, and that each object has value 1. If we use an s with at most 2 bits set then only a small fraction of the objects will have their values negated, so the sum will still have the same sign. And the same thing happens for all s with 60 (or more) bits set (this was what you meant by compensation, right?).

But if you're lucky such a case won't be in the system tests. :)

Maintain sum and try to randomly switch bits?

I passed the pretests with following algorithms:

Repeat this operations until you find an answer.
1. Choose value s randomly between $$$1$$$ and $$$2^{62}−1$$$.
2. Check the total prices. To calculate, it usually takes $$$O(NlogN)$$$, but if you use __builtin_popcountll (if C++), it takes $$$O(N∗C)$$$ and $$$C$$$ is around $$$5$$$.
3. If the sign of total prices has changed, you successfully found the answer.

On average, you should do $$$~2$$$ operations. Is there any doubt that there is some cases that the sign of total price changes in very less percentage of $$$s$$$? I think it's not. I checked $$$100,000$$$ random cases which the value of mask is between $$$1$$$ and $$$63$$$. The worst case was the sign of total prices changes in $$$8/63$$$ of s assume s is also between $$$1$$$ and $$$63$$$.

P.S.
The testcase which the sign changes with only $$$8$$$ out of $$$63$$$ $$$s$$$ is as follows:

Sort points via $$$s_i$$$. Then maintain stack of points having $$$s_i < t_i$$$. When you check another point, push it to stack if $$$s_i < t_i$$$ and try to match it with points on stack until stack becomes empty or you get $$$s_i = t_i$$$ if $$$s_i > t_i$$$.

Unfortunately, I have drunk too much prostate juice today, so I solved the problem incorrectly (greedly from both ends) and can't give you a hint what the correct solution is like.

Something like this maybe? I got WA on 14 until I fixed this case

4
1 4 5 8
2 3 6 7

Consider how to use no more than $$$5$$$ swaps to move number $$$i$$$ to position $$$i$$$.

I also had this problem. I think we need to add d=min(d, (s[j] — s[i])/2)

Your code will fail on tests like

4
1 6 7 10
3 5 8 8 

Your code gives the output "NO" but the correct output will be "YES"

YES
3
1 2 1
1 4 1
3 4 1 

here^ is one of the suitable output for the above test case

(retracted my previous claim; turns out there are counter tests)

System test haven't started yet. I think they're trying to make that test :)

Deterministic solution for F:

WLOG assume sum positive, otherwise change all signs. Iterate $$$k$$$ from $$$61$$$ to $$$0$$$. For each $$$k$$$ and each $$$i$$$, sum $$$val_i$$$ over all masks such that the lowest on bit of $$$mask_i$$$ is the $$$k$$$-th. If this sum is positive, then turn on the $$$k$$$-th bit in $$$s$$$, otherwise do nothing.

Proof this works: Consider a certain $$$0-1$$$ mask, and consider the expected value of the sum over all masks that have this mask as a prefix. (choosing a mask uniformly at random). All $$$i$$$ that have an on bit below the $$$k$$$-th contribute $$$0$$$ to this expected value, while the ones that are all $$$0$$$ below the $$$k$$$-th bit contribute $$$2^k$$$ times their sum. So our algorithm just forces the contribution for these to be always negative.

I have a algorithm (not random) for problem F. Haven't tested it yet, but I think It's correct.

Let's split A (the origin set of objects) into two subsets: A1 and A2. All masks in A1 have the bit 0 turn off, and A2 = A\A1.

Suppose we have someway to assign bit 1, bit 2, ... such that sum of all val in A1 is non-negative. After assign bit 1, bit 2, ..., we have two option: turn off bit 0 or turn on bit 0, one of them will make the sum of A2 is non-negative. So, we found a way to assign bit 0, bit 1, ... such that sum of A is positive.

I think that tourist's solution is not that kind of solution.

There's no such thing!!

I was in same room as Um_nik and I made random solution to problem F. he didn't hack my solution, so there is no counter-test.

Yep, cdkrot found some about a week ago :)

Greedy. Fix the number of canceled flights from the first set (A to B) and then check what the earliest time we can go from B to C with binary-search/lower_bound is.

Suppose you cancel the first x flights from A to B. That means Arkady will take flight x+1 from A to B

Doing a binary search on b you can get the first available flight from B to C. But since you have only canceled x flights, you can cancel the next k-x flights, forcing Arkady to take later flights. Then you can now whats the earliest that Arkady can get to C.

You can do that for every x<=k

Can solve using two pointers too instead of binary search! Here's my code

Problem C: You can solve this task in less than 3*n moves is this true?
No.

I solved C taking less than 3*n moves. code

So, the answer to the first question is, YES. In my code the operation works within 3n times.

too many flushes. try without endl perhaps

Alex's right: 54950010

What was your approach to solve C ? Please help! as I couldn't get it.

And the new one:

Good enough, I think.

I felt the same, and there's my comment like yours in the middle of comments.

I did

Yes, Really interesting in the last minutes.

Author's solution doesn't use bitset.

We think that it is easier to write incorrect solution in this case, because an efficient test requires $$$O(N^2)$$$ edges, therefore, number of vertices must be $$$\leq 1000$$$. So, we have decided to make this version with $$$10^5$$$ vertices.