Editorial

[deleted], sorry for a mistake

you can register , but you will be "out of competition" that means unrated

I'm guessing a counting problem

Is it 1998C - Perform Operations to Maximize Score?

That time I was naive to think it's easy div2C...

As a div 2 participant. I'm scared to fight against bots atm.

chuckles I'm in danger.

Yes approx. 2300, but why are less than CM able to even register?

I can't tell you that. Just wait and see.

In div 1, 2 contests, div 2 is <1900 rating and div 1 is >=1900 (However, in div 2 only contests, div 2 is considered <2100)

yes

Just do, 2:15 am here! And yes I have classes tomorrow morning~

Bro a master in high school that is crazy

Bro I finish the competition by secretly bringing my computer and phone to schoo :) My teacher did not catch me :)

Sometime you have to pay for what you love :)

There is a solution that missing number is in position 2 and is bigger than all of the numbers in the array

Hint: sort the input array, you calculate the second-last element by sum(odd) — sum(even)

so I took all terms on one side a1-a2+a3-a4... .. now because order doesn't matter we only have two choices.. we can have a term with positive sign or negative sign missing

because we wanted everything to be different .. I thought we can remove a2 and its value will be a1 + (a3-a4) + (a5-a6) + (last term) .. now if this sequence was reverse sorted.. then this sum will be greater than a1 .. hence greater than every thing / different than everything

so that is what I did

Ask $$$n = 0101010101$$$ and $$$n' = 1010101010$$$, then calculate $$$sum - 2 \times n$$$, you will get $$$x \oplus y$$$.

My line of thought was the following:

We can simulate a subarray with the following code

long long openEven = 0, openOdd = 0, ans = 0;
for(int i = l; i < r; i++) {
	if(i % 2 == 0) {
		if(a[i] >= openOdd) {
			ans += a[i] - openOdd;
			openEven += a[i];
			openOdd = 0;
		} else {
			openOdd -= a[i];
			openEven += a[i];
		}
	} else {
		if(a[i] >= openEven) {
			ans += a[i] - openEven;
			openOdd += a[i];
			openEven = 0;
		} else {
			openEven -= a[i];
			openOdd += a[i];
		}
	}
}
return ans;

Then I realized that this is something to do with prefix sum balance of the subarray. The problem turns into finding the maximum prefix sum — minimum prefix sum of the subarray taking b[i] = i % 2 == 0 ? a[i] : -a[i] (there's a graph interpretation for this that I've learned and seen from quite a few past problems) and now it shouldn't be that hard for you.

it was greedy , idk why i coded and it worked :)

For each +X, we calculate its contribution to the total answer, which is the number of times clones of it at the end. We start with +1 to simulate the presence of two individuals at the beginning.

We maintain two variables, L_i and R_i, to track the maximum number of duplicates we can achieve when progressing through gates i to N, where we choose either the left or right gate at the ith gate, respectively.

If the ith gate is an addition (+), then: L_i = L_(i+1) (No clones are made, the same guys move to the next gate)

If the ith gate is a multiplication (* X), then: L_i = L_(i+1) + (X — 1) * max(L_(i+1), R_(i+1)) (Here, X — 1 duplicates are created, which can choose between the next gates based on which will maximize the number of future clones)

The updates for R_i are done in the same way.

Finally, sum the contributions of all + operations to compute the total answer.

You answer is great.I never mind this way。

My solution was just O(n^2) greedy. It's always optimal to either send all extra to lane 1 or lane 2. There are 4 cases,

Case 1: + x, in which case it is always optimal to send extras to lane 2.

Case 2: x +, in which case it is always optimal to send extras to lane 1.

Case 3: + +, in which case you just accumulate more extras.

Case 4: x x, in which case you either send extras to the one with the larger x, or look down the line to find the first x in lane 1 or lane 2 (similar logic if they are the same).

No way, greedy worked for D? I calculated and it got disproved in the given TCs, can you tell me what you mean by greedy here?

what is your idea of greedy?

And why can't they be sent after the competition?

how to solve E $$$??$$$.

they will publish editorials after some time , you can keep checking this post for the contest announcement https://mirror.codeforces.com/blog/entry/140357

they will attach the link to the editorial at the bottom of this post

and yes people share some ideas on youtube.. search for contest name ie 'Codeforces Round 1008' on youtube

my thoughts

https://mirror.codeforces.com/blog/entry/140357?#comment-1253756

The maximum for D is actually slightly under the limit.

The actual maximum is n=30 with a +1000 gate at the start, followed by 29 x3 gates. With 2 sides, your answer comes out to 2002*3^29 which is slightly above 1e17, while 64-bit integer limit is over 1e19.