NOTE THE UNUSUAL TIMINGS!! Wish you positive delta!!

omg no green circle

I hope this round will be better and more interesting than before.

omg subtasks for A round

I think (500+750) is better than (500+500).

Delete this they will surely give it then

That's was a good constructive problem. I like those problems because even newbie can solve it and i have seen even master are sometimes not able to solve them. Try till you get the right approach.(It's just how i see them haha).

bruh imagine advertising cheating

Bro there is now way you are now reaching pupil after 1 year. You are surely doing something wrong. Please analyze it quickly or else it will be too late. 3 months are more than enough for pupil if you are serious that is.

Omg! Yellow round.

Actually, 22:35(UTC+8) is not TOO unfriendly for who are used to staying up late. It's better called friendly time to Australian coders.

I remember that once there were two contests held at about 15:35(UTC+8) and 18:35(UTC+8) on the same day.

Of course it's a very friendly time.I can't stay up late because my father don't allow me to do that:)

No! I prefer Downvoting you.

I down voted you, to show world doesn't work that way. :)

OMG, subtasks in problem A!

Good time for Chinese.

wow

prove your loyalty to codeforces

nice u got a reason to skip classes :)

True Mate.

After this contest, I have to disagree.

Problem A2 is scaring me. I wouldn't have participated if I cared about my rating.

Why Delay 10 min Sir ??

I have the same question.

Same question

Maybe rating update

10 minutes postponed!

Yes, postponed by 10 mins. Good luck!

Thanks! I thought my country decreased its standard time by 10 minutes

Mee too :D

Thank you for participating! Round 842 was great too!

Actually, I agree with you it's just a matter of time to solve this version if you have a solution for that gym problem and 144 participants solved that problem already I guess so it's easy for them.

true

You are not worried about $$$3\cdot10^5$$$-legged spiders, right?

• If $$$x = n$$$, the answer is trivially $$$n$$$ itself.

• If $$$x = 0$$$, this means that the most significant bit of $$$n$$$ must become 0 at some point. If this is the $$$a$$$-th bit from the right, then the first number to flip this bit is $$$2^a$$$ (single 1 followed by $$$a$$$ 0s). So the AND must include $$$2^a$$$ and we can see that $$$x$$$ AND $$$2^a$$$ is 0, so the answer is $$$2^a$$$.

• Now $$$x$$$ must have at least one $$$1$$$. Find the last $$$1$$$ in $$$x$$$, and let's say it's at position $$$\ell$$$. Because bit $$$\ell$$$ is a 1, this means it was never flipped while incrementing the numbers, suggesting that all bits to the left of bit $$$\ell$$$ remain unchanged. So the prefix of $$$x$$$ up to bit $$$\ell$$$ must be equal to the prefix of $$$n$$$ up to bit $$$\ell$$$. If there is a mismatch, the answer is $$$-1$$$.

• We can now write $$$x$$$ as some $$$prefix$$$ (which ends with a 1) followed by all 0s, and $$$n$$$ as the same $$$prefix$$$ followed by some $$$suffix$$$ (whose length matches the block of 0s at the end of $$$x$$$). There are two further cases to consider:

1. If the $$$suffix$$$ begins with a 1, then we have a problem. Since this bit is 0 in $$$x$$$, it must be flipped at some point. But flipping this 1 will also flip the 1 to its left, i.e., the last bit of the $$$prefix$$$. But we know that the $$$prefix$$$ cannot change, so this scenario cannot happen, i.e., answer is $$$-1$$$.

2. Otherwise, find the first 1 in the $$$suffix$$$. Let's say it's in position $$$c$$$ (from the right). This bit is 0 in $$$x$$$, so it must be flipped at some point. When this bit is first flipped, the bit at its immediate left (position $$$c + 1$$$) becomes 1, and everything after it becomes 0. This number is $$$x + 2^{c + 1}$$$, i.e., the common $$$prefix$$$ followed by all 0s except a 1 in position $$$c + 1$$$. Conveniently, applying AND between this number and $$$n$$$ will already yield $$$x$$$ (the only $$$1$$$ after the prefix is at position $$$c + 1$$$, which is a 0 in $$$n$$$), so this number is the answer.

My submission: 188732906. I converted the numbers to binary first, and worked from there, converting back when printing the answer (except when the answer was $$$n$$$ or $$$x$$$ itself).

Answer will always lie between n and INT64MAX and bitwise and from n to k >= bitwise and from n to k+1 therefore you can apply binary search . To find bitwise and from n to k you can search on net and get method easily .

no need to look at one prime number more than once during bfs (this helped me with test 12)

I suspect giant casework.

Also please update the rating of last educational round quickly

If bits set in one number is a subset of another number , then the answer is always possible.

Did you by any chance used a fixed-size frequency array? freq[200001] * n <= 10e5 = TLE... I should know from having fallen for it 5 times this contest.

I've thought Double linked-list and priority-queue could solve E, but got WA.

when I used vector to store the frequencies I got the TLE, but then changed to unordered_map it passed. not sure why vector[i] is slower than map[i] :(

Hint: the first subsequence is the whole array, the second is the whole array except only one number.

Let $$$s_1$$$ be the maximum sum over all subarrays and $$$s_2$$$ be the minimum sum over all subarrays, then the answer is $$$\max(s_1,-s_2)$$$.

Lower bound

Clearly you can change the sum of some subarray by at most 1 per operation, so the answer can't be lower than $$$\max(s_1,-s_2)$$$.

Upper bound

For simplicity we suppose $$$s_1>-s_2$$$.

Consider the following rules:

1. Adjacent positive elements are automatically merged into their sum. (The same for negative elements)

2. Zeros are automatically removed from the array.

It can be shown the answer won't change if we apply the rules.

After merging, we can repeatly try to change every element closer to 0 and apply the rules after each operation. It can be shown it's optimal. The sum of the greatest subarray will always reduce by 1 after each operation. (If we can't at some moment, then it's not the greatest subarray.)

If the answer is greater than $$$s_1$$$, then there exists a subarray with sum greater than $$$s_1$$$, which is a contradiction.

We will process elements left to right. When processing some element, we either create new operation or extend some old operation.

Intuitively, it makes sense that we would not have to using operations to both add and subtract from an element. So a simple $$$O(n)$$$ greedy works.

#include <bits/stdc++.h>
using namespace std;

#define int long long

int n;
int arr[200005];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	int TC;
	cin>>TC;
	while (TC--){
		cin>>n;
		for (int x=1;x<=n;x++) cin>>arr[x];
		
		int add=0,sub=0;
		for (int x=1;x<=n;x++){
			if (arr[x]>0) add=max(add,arr[x]);
			else sub=max(sub,-arr[x]);
			
			add-=arr[x];
			sub+=arr[x];
		}
			
		cout<<add+sub<<endl;
	}
}

Think about a sequence of prefix sums and observer how such operation affects this sequence of prefix sums.

If you analyze carefully enough, then you'll see that one of the operations just adds $$$1$$$ to any subsequence of prefix sums, and the other operations just subtracts $$$1$$$ from any subsequence of prefix sums.

So, AFAIK you just need $$$\max(0, \max(p_i)) + \max(0, \max(-p_i))$$$ where $$$p_i$$$ is the array of prefix sums.

I think subtask 1 is as easy as problem A...

You are right probably, it should be split.

By the way, the original contest is OI-style, so there two problems were combined as one, with different groups for each of the subproblems. For Codeforces, the problem was just retained as-is.

Yes, you are right, sorry for that :(

It's interesting that the round with the similar problem is also of Belarusian origin, but the authors came up with the idea independently AFAIK, so it's an unfortunate coincidence.

I did this too xD...