Базара нет.

As mentioned in a previous blog, the problems today is harder than in a regular Codeforces round. Since it alao has one more problem than usual, I'm afraid 2 hours is a bit short :((

Please, do not register on Div.1/Div.2 Editions. I'll register you on "Final Round" manually.

The problemset for div. 1 will be a bit easier than from problemset for final round. Same, the problemsset for div. 2 will be a bit easier than the problemset for div. 2.

Программист — жаворонок? Не верю своим глазам :)

I am sure you will do great...

Since problem set is not same for all 3 variants it can't be combined

Try virtual participation after the round maybe? I think that is the only way.

You can wait 2 hours and then participate virtually

I'm also afraid of it.

You might find it hard to believe, but the world has different time zones. I believe it's morning for the contest creators.

Em, I think you have a bug there. I'm on the list, but I'm not an onsite finalist.

For some reason I can see myself in this list, despite not being onsite. Is it OK?

P.S. Nevermind. It seems every contest participant can see himself even if he is not in the list.

Please remove me from that list. It seems somewhere I clicked the button that I don't supposed to click :-)

Problems were extremely derivative. Not original.

Probably a high integer value > 10^9 I got WA at it just because I was making sums till 30 bits only!

Something like 10^12 10^12. My error was because of integer overflow.

I failed this pretest many times.

My mistake was that when sum == xor I divided the result by 2 and it's supposed to subtract 2 from the result because only the pairs (sum, 0) and (0, sum) are invalid.

It passed pretests after that, hopefully systests too.

I'm almost certain it was of the form (2 ^ i - 1) (2 ^ i - 1) for some positive integer i < 40. For instance: 65535 65535. I added a check in my code for this particular case (the answer is 2 ^ i - 2), and it passed the pretests.

try 4 4 answer is 0

correct answer 0?

Thanks for your quick mini-editorial! :D

Please, can you explain me why there is the special case in A?

In test case S = 3 X = 3, the statement says that there are only two correct solutions ( (1,2) & (2,1) ). Why (0,3) & (3,0) are not good solutions?

Congrats... they all passed :D

For D I implemented something like you describe, taking O(N) for each iteration of binary search, but it kept timing out on pretests (although I couldn't find a test case to make it take more than 1 second on my machine).

Hi! Could you please explain your approach to B? What about leftover production which can be used on later days? What are your fenwicks storing exactly ( prefix sum of min(ord(i), B) and a suffix sum of max(ord(i), A) ) because I don't understand how to find the answer from these. Please explain.

I found an approach with 5 fenwicks, so I want to understand your approach, you only use 2 fenwicks :) thanks in advance

Так в этой ситуации достаточно отнять 2 от результата :-)

dynamic programming on the bits. Let f(i, carry) be the solution considering the first i bits and if we have a carry (from the previous bits (0 , i - 1)).

Now depending on the value of the ith bit of the sum and the ith bit of the xor we call the appropriate recursive calls.

for example (assume carry is 0) if the value of the ith bit of the xor is 0, then we can put either (0, 0) or (1, 1). now if the ith bit of the sum is 0, then the first choice (0, 0) will have the solution f(i + 1, 0) and the second choice (1, 1) will have the solution f(i + 1, 1). and the rest of the cases are similar.

Hope it helped.

There's also an O(sqrt(N)) meet in the middle solution in which you split the number into 2 groups of ~20 bits each.

Make use of the fact that each integer has a unique binary representation,so this means we don't have to use DP , simply check if the binary representation of s' is a subset of ~ x, where s'=(s-(sum of 1<<position of bits set in x))/2, if s is divisible by 2. In other cases(s' is odd, or s' is not a subset of ~ x) output is 0.

Нужно переписать уравнение n^(s - n) = x в виде n^x + n = s. Дальше просто динамика по битам.

s - x =  удвоенная сумма битов, которая стоит у обоих чисел

С учётом этого, если данное число вообще может быть правдой (), то число пар это 2^{__builtin_popcountll(x)}. С учётом того, что считаем положительные пары, придется ещё вычесть 2 если s = x.

UPD: Due to onsite awards presentation, we will hold final system testing until around one hour after the end of the contest.

"Due to onsite awards presentation, we will hold final system testing until around one hour after the end of the contest."

Your hopes have been denied.

It's just a tedious well-known problem in my opinion. I think I've even seen it on USACO although I can't find where it is..

Link to the code?

Pretests are weak. My recursion also passes div1B:

ll count(ll s,ll x){ if(s%2!=x%2) return 0; if(s==0) return 1; if(s<x) return 0; if(s%2==1){ return 2*count(s/2,x/2); } else{ return count((s-2)/2,x/2) + count(s/2,x/2); } }

But it is O(s+x) in worst case.

I would say implementation of div2 F was way easier than div2 E or my approach is wrong (might be, cause it's pretty simple and obvious).

No it's time to rise and shine! :P

.o. height rating increasing. I think historical in codeforces record +548

You can use deque to maintain remained gas to get a O(m) solution instead of priority queue. but sorting is still needed.

I've solved this task many times (include the first time I come up with this task by myself..)

So the idea is: you can buy some gas, and at some point you can sell them at the price you bought it.

• When you are spending gas, spend the cheapest one
• When you arrive at a station, if there are gas more expensive than the one at this station, sell them all. And then buy as much as you can.
• When you arrive destination, sell all.

You can use an array with 2 pointers (left, right) to keep a sorted list of gas with different price and amount.

not sure if correct

sort all gas stations by cost

use set<start, end> of gas for gas station and for each gas station insert values and update answer

div1D can also be solved with divide and conquer. solve(l , r) denotes min cost to reach rth point from lth point if we leave with full fuel at l. find the point with minimum fuel cost in range l + 1 to r — 1 , and buy all fuel here or as much as we need to reach rth point and now add solve(l , index) + solve(index , r) to it. Code

I copied code of 364E of someone and modified it and pass pretest finally after some TLE >_< Hope I can get AC...

The problem 627C - Package Delivery is much easier version of 581E - Kojiro and Furrari.

Hadn't I solved the problem 364E, I wouldn't have been spending long time thinking about the method of divide and conquer :(

It seems the expected solution is way different from that of 364E.

My solution highly exploits the fact that n ≤ 3000.

The main idea: Suppose the top side of the rectangle is in row i and the bottom side is in the row j > i. First iterate over all i in any order, for a fixed i iterate over j from r - 1 to i. When we have fixed i and j, we have a horizontal strip of cells, write down for each column how many 1s there are in this column in our strip into an array A. Having this array, it's easy to find how many good rectangles there are in this strip: for each non-zero item j in A we only need to know closest non-zero item to the left prev[j] of it and the first positon from[j] such that on the segment [j, from[j]] the sum of values in A is greater or equal to k.

Now let's understand what changes when we decrease j by 1. Some values in A decrease by 1 (that's O(n) totally over all j), my idea is that there will be no more than k values of from we need to fix for each changed position j (actually, those positions are no more than k non-zero items to the left of j). I use this fact for a careful recalculation of array from.

The main difficulty here is how to find a closest non-zero item to the left or to the right in A. I do that by using path compression technique that provides a very fast log factor. So, overall complexity after careful amortized is for all path compression and O(rnk) for all changes in arrays A and from. Overall complexity is . It has pretty easy implementation, though I spent about an hour on optimizing this solution to make it fit into TL, and still, it runs for about 1.7 sec on pretests :(

UPD: formulas above had a mistake, I've lost the r factor in an analysis. Now it's fixed.

UPD: 1918 msec on final tests. Damn I feel lucky :)

So that's part of why the rating change prediction plugin thing shows so much loss for me :D I did screw up royally, but -82 does seem like worse than my previous royal screwups.

3500 signed up but I only see 1300 in the standings. Still trying to figure out where the rest went...

move 0 in both arrays in place 1 then check numbers in places 2 to n to each other

Ignore zero in both arrays and then check whether they are cyclic permutation.

1. Read the two lists of numbers.
2. Remove the number 0 from both of them (can be done while reading)
3. Rotate the second lists until it starts with the same number as the first list.
4. Compare if every number in the same position of both lists are the same, if they are --> YES, else NO

ignore 0, and check if they are rotation of each other

Proof for the method is welcomed.

Thanks in advance.