Editorial

15 months ago, hide # |

I see satyam343, I wait for a sweaty binary search problem

→ Reply

619

15 months ago, hide # ^ |

I'm guessing a counting problem

→ Reply

15 months ago, hide # ^ |

Is it 1998C - Perform Operations to Maximize Score?

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

→ Reply

15 months ago, hide # ^ |

Yeah, absolutely cringe and unbalanced div2C. Many reds spent a lot of time debugging it, only to hear from satyam343 afterwards, "just learn binary search".

→ Reply

15 months ago, hide # ^ |

I finally upsolved it after 2h+ of coding and debugging...

This is not only binary search, very implementation punishing also.

→ Reply

irmuun

15 months ago, hide # |

+11

As a tester, I tested.

→ Reply

Zeyush

15 months ago, hide # |

+81

why are there so many new accounts registered a couple minutes ago registering for div1? are they bots from ai companies / research groups?

→ Reply

15 months ago, hide # ^ |

-10

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

chuckles I'm in danger.

→ Reply

DenimFlame12

15 months ago, hide # ^ |

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

→ Reply

Error_Yuan

15 months ago, hide # |

+19

As a tester, this contest was a div2-only round when I tested it.

→ Reply

RGB_ICPC_7

15 months ago, hide # |

-26

omsincoconut Please suggest which topic I need to practice to participate in this round , if possible .

→ Reply

omsincoconut

15 months ago, hide # ^ |

+11

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

→ Reply

RGB_ICPC_7

15 months ago, hide # ^ |

-8

Ok sir

→ Reply

vishesh_codes

15 months ago, hide # |

Am i even eligible for div 2?

→ Reply

mariza_CY

15 months ago, hide # ^ |

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)

→ Reply

vishesh_codes

15 months ago, hide # ^ |

ohh, thanks for the help mariza

→ Reply

mariza_CY

15 months ago, hide # ^ |

No problem. Good luck if you participate!

→ Reply

marianoferesin

15 months ago, hide # |

As a tester, do not forget to turn on your computer before the round

→ Reply

yeetholmes619

15 months ago, hide # |

-18

As a contestant if I see a permutation construction B, I will skip :)

→ Reply

NiGhT-h-MaRe

14 months ago, hide # |

-10

Expecting increase

→ Reply

qaisB

14 months ago, hide # |

+13

Is the contest rated ?

→ Reply

dougalves

14 months ago, hide # |

As a tester, I can ensure that omsincoconut is not a real coconut.

→ Reply

AHMADUL

14 months ago, hide # |

Finally, the first rated round of this month!!!

→ Reply

future_zyl

14 months ago, hide # |

+17

I'm a Chinese senior high school student. I really want to participate in this contest, but the contest will last until 1:15 a.m. in China, while I have to go to school at 7:30 a.m. Should I sacrifice my spare time to join the competition?

→ Reply

Ormlis

14 months ago, hide # ^ |

+172

yes

→ Reply

hopium

14 months ago, hide # ^ |

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

→ Reply

fbrunodr

14 months ago, hide # ^ |

-26

Bro a master in high school that is crazy

→ Reply

chenxi2009

14 months ago, hide # ^ |

-7

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 :)

→ Reply

34z12000

14 months ago, hide # ^ |

-10

Based

→ Reply

askd

14 months ago, hide # |

I'm on like 3hrs of sleep but we gamble

→ Reply

UP84

14 months ago, hide # |

Site is way too slow,nothing is loading.

→ Reply

mohmmdali

14 months ago, hide # |

it's getting unbearable atm

→ Reply

cyclop5

14 months ago, hide # |

thank u for these soundtracks

→ Reply

bsdsdb

14 months ago, hide # |

+24

Arcaea Round

→ Reply

Itssme_Ayush

14 months ago, hide # |

someone just tell me how to do div2-c.

Scratched my head for more than an hour.

→ Reply

ChickenInKitchen

14 months ago, hide # ^ |

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

→ Reply

14 months ago, hide # ^ |

← Rev. 2 →

Yea true, either 1 or 2, 2 always works 1 can sometimes work and needs a check. Also we should mention that in sorted array, not any

→ Reply

14 months ago, hide # ^ |

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

→ Reply

Itssme_Ayush

14 months ago, hide # ^ |

and what will be the sequence?

→ Reply

14 months ago, hide # ^ |

← Rev. 3 →

Best by example in this problem:

2
1 2 3 4

My solution will be:

1 2 3 X 4;
with X = 1 + 3 + 4 - 2 = 6

Final output:

1 2 3 6 4

→ Reply

npc0x7

14 months ago, hide # ^ |

What if that second-last element is already present in b? Wouldn't that create duplicates?

→ Reply

14 months ago, hide # ^ |

Hint: it can't happens because my new X always > max(b). Try to think why?

→ Reply

GunZaaN

14 months ago, hide # ^ |

lets say we have 6 3 2 1

so the equation will be 6 = x-3+2-1

6 = x — (greater than 0 (as elements are distinct and sorted))

so x will always be greater than 6 which was the greatest element of all so no chance of clash.

→ Reply

esh_war2

14 months ago, hide # ^ |

instead of thinking a1 thinking of a2*n by rearrangement

→ Reply

14 months ago, hide # ^ |

+20

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

→ Reply

its_magic

14 months ago, hide # ^ |

Nice Approach!!

Btw, How did you get the intuition that this may work ?? (As an beginner I'm very curious :) )

→ Reply

14 months ago, hide # ^ |

I am sorry but I don't have any answer apart from experience/practice.

For me it is also a hit-and-miss, sometimes I spend hours thinking of some observations and fail :( :(

→ Reply

its_magic

14 months ago, hide # ^ |

Thanks

→ Reply

ChickenInKitchen

14 months ago, hide # |

how to solve E ? what are the questions you ask ?

→ Reply

YipChip

14 months ago, hide # ^ |

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

→ Reply

phsads

14 months ago, hide # |

← Rev. 2 →

+25

how to 1E

i got to the point where you can make a set of indices $$$i[1], i[2], ..., i[k]$$$ darker iff $$$i[u] - i[u-1]$$$ odd for all $$$u$$$ but idk how to continue from there

→ Reply

14 months ago, hide # ^ |

← Rev. 3 →

+10

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.

→ Reply

LearningMachine

14 months ago, hide # |

What was the second query supposed to be for Div2 D? Also, how come so many solves on F?!!

→ Reply

DuongNeverAlone

14 months ago, hide # |

I knew exactly what to calculate in Div1C, but couldn't know how to calculate it efficiently :(

→ Reply

14 months ago, hide # |

Who would have thought a scammy game ads could've been this hard of a problem?

Any hints for div2D?

→ Reply

dpsvoyager.16

14 months ago, hide # ^ |

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

→ Reply

timg8710

14 months ago, hide # ^ |

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.

→ Reply

SussykinWantsNatalia

14 months ago, hide # |

← Rev. 2 →

for 2F/1C I got some mathematical expression but couldnt simplify, so I generated F(N, K) = answer when you have K 0's, and via OEIS i realized that F(K) is a 3rd degree polynomial and just used brute + oeis to find the coefficients. How are you supposed to do it normally???

→ Reply

Aurorawlm

14 months ago, hide # ^ |

You answer is great.I never mind this way。

→ Reply

14 months ago, hide # |

Couldn't optimize D. I distilled it down to its optimal to either use all extras in lane 1 or all in lane 2, Couldn't think of a greedy heuristic to use to prune down to the optimal path so ended up being 2^n TLE. I'm guessing it has to do with the fact that the multiples are either 2 or 3, but ran out of thinking time

→ Reply

14 months ago, hide # ^ |

+14

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).

→ Reply

14 months ago, hide # ^ |

← Rev. 2 →

This makes sense. I think where I messed up was attempting to calculate the extras allocation too soon.

Your solution delays the decision by carrying over the extras further down the road to always make the decision where it matters. Thanks for the explanation.

→ Reply

Homelander2003

14 months ago, hide # ^ |

Why do you just assign the "extra" towards the lane where you find greater multiple down the line or the first multiple? Wouldn't you look over all the multiples and calculate effective multiple and decide overall which lane will be the best choice?

→ Reply

Dthapa

14 months ago, hide # ^ |

did he mean, if we have *2 *3 don't look down the line, just add accumulated players to *3?

→ Reply

14 months ago, hide # ^ |

yeah

→ Reply

Dthapa

14 months ago, hide # ^ |

Can you explain case 4? what do you mean by look down the line to find the first x in lane 1 or lane 2?

→ Reply

14 months ago, hide # ^ |

Basically to decide whether to move extras to lane 1 or lane 2, you want to see which one of them has a multiplication that comes first after that point. All of the steps are easy to prove so I would recommend trying to do that. If you need help you can ask me.

→ Reply

14 months ago, hide # ^ |

By the way, you can optimize case 4 so that it's not the bottleneck of your solution. There's two routes you can take for the same multiplier subcase: either you treat them as extras that doubled or tripled (and still keep the same non-commital aspect of "looking down the line"), or you preprocess "looking down the line". The first of these routes is actually very similar to your Case 3 (you don't commit people to one lane and just accumulate extras). Either way, you get an O(n) solution.

→ Reply

14 months ago, hide # ^ |

yeah bur O(n^2) easily passes and its easy to implement.

→ Reply

14 months ago, hide # |

← Rev. 2 →

I made a greedy solution guess for div2 D without proof and it passed pretest, now fingers crossed for system test.

Also I struggled with what question B was actually trying to say.

Edit : yikes !!! div2 D passed system test. I am not proud, but I will sleep happily now.

→ Reply

14 months ago, hide # ^ |

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?

→ Reply

14 months ago, hide # ^ |

yeah waiting for system tests first ha ha .. not sure it is going to make it

but my greedy was do brute force BFS for all possible state but at a layer only take max values in front of a gate.. so every layer of BFS can only have max 2 states. eg if possible state in front of gate were (5,3), (4,2), (1,19), (2, 10)

max in front of operation 1 is 5 and max in front of operation 2 is 19

so I only take (5,3) and (1,19) to next BFS level ..so my BFS don't explode to 2^n

not sure of correctness though .. fingers crossed

→ Reply

14 months ago, hide # ^ |

I see, all the best.

→ Reply

14 months ago, hide # ^ |

did not understand, please elaborate your approach in detail

→ Reply

14 months ago, hide # ^ |

← Rev. 2 →

you can check my submission for the code..

I will only give brief idea.. first idea was to do 2^n BFS .. basically at every step ... get all states ... so what are these states

eg. if 1st gate has A people and 2nd has B .. and operation on 1st gate is op1 and on second is op2 ... this state is denoted by {A,B}

then results after going through the gates will be op1(A) and op2(B) ... now diffs are d1 and d2 where d1 = op1(A) - A and d2 = op2(B) - B, these diffs are new people which appeared , and these need to be rearragned for remaining gates

now first assumption I made was we send all people to same gate .. so possible next states are {A+d1+d2, B} ( we send all new people to gate 1) and {A, B+d1+d2}

now if we do this completely every layer will have 2^(layer) states and overall 2^n

I made another assumption that I will pick only 2 states in a layer which gives me maximum people in front of a gate .. so now every layer has at max 2 states, which is what I did. example of this choice is in previous comment.

what I am not sure is why this assumption is correct, but because it passed given test cases I submitted to try my luck.

→ Reply

14 months ago, hide # ^ |

ok got it. i was thinking of the same approach but not with 2 states at each level/gate, i was thinking of trying all the possible distributions of the newly appeared persons that came out of the gate.

→ Reply

14 months ago, hide # ^ |

what is your idea of greedy?

→ Reply

Komekko

14 months ago, hide # ^ |

Suppose you are currently in i-th gate. Now consider closest gate j where i<j and one of its door has 'x'. Then you always have put your extra people on that lane. Because once you reach that gate you will have duplicate of extra people(so you can place it on other lane if you want) but if you were to put it on the other lane then you would only have the amount of extra people you made.

→ Reply

14 months ago, hide # ^ |

yikes I completely miss this idea... Thanks

→ Reply

14 months ago, hide # |

Div2 D was like its almost in my hands but i cant catch it haha

→ Reply

plie

14 months ago, hide # ^ |

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

→ Reply

14 months ago, hide # ^ |

What do you mean

→ Reply

plie

14 months ago, hide # ^ |

Can't I make a package after the round!

→ Reply

14 months ago, hide # ^ |

You can, but it will not be a part of the competition, its an independent submission

→ Reply

14 months ago, hide # ^ |

You cannot submit solution while system testing is pending/running. Simply wait till the system test is completed.

→ Reply

cheyun

14 months ago, hide # |

Why is test 1 of div1 b not an example

→ Reply

chenxi2009

14 months ago, hide # |

← Rev. 2 →

A contest with an interesting interective problem! I have solved my first Div.2E :)

→ Reply

virginMohito

14 months ago, hide # ^ |

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

→ Reply

DuongNeverAlone

14 months ago, hide # ^ |

Try to query 01010101... and 10101010... to find x and y.

→ Reply

miss_robot

14 months ago, hide # ^ |

Do you actually determine x and y from that? I queried 0000…0 and 01010…1 and just determined how many times each bit is set in x and y together.

→ Reply

DuongNeverAlone

14 months ago, hide # ^ |

In fact there are many possible x and y for this problem, and I found one of them. Then I directly calculate the final answer with those x y.

→ Reply

BenjaminJ

14 months ago, hide # ^ |

E can be solved using the C++ programming language.

#include<iostream>
int main(){int a,b=715827882,c,d,e;for(std::cin>>a;a--;std::cin>>c>>d>>e,std::cout<<(~(b|e)*3&d-2*b)+((b&~e)*3&c-d+~b)+2*e)printf(" 0 %d ! ",b);}

I hope this helps!

→ Reply

bhasinjai

14 months ago, hide # |

Hello guys, I have kind of just started. Can someone please tell after the contest ends where can I find the solutions for it...

and are there any good subreddits, discords or telegram chats that discuss the solutions after the contest is over

→ Reply

14 months ago, hide # ^ |

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

→ Reply

bhasinjai

14 months ago, hide # ^ |

thanks a lot!

→ Reply

cfkage

14 months ago, hide # |

How to solve C in div 2?

→ Reply

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

14 months ago, hide # ^ |

my thoughts

→ Reply

cfkage

14 months ago, hide # ^ |

thank you, your solution was easy to understand

→ Reply

14 months ago, hide # ^ |

Please read editorial as well , it can have a different / better solution

→ Reply

14 months ago, hide # |

← Rev. 2 →

I liked some of the problems.

A: very guessy problem, I think As can be much better than that
B: neat observation problem, B is definitely in its place
C: decent problem, spent a lot of time figuring how to make a new element unique
D: my approach failed and I was struggling to find my mistake. Btw, I think that under the given constraints the answer can be larger than uint64_t, which is very strange (just try n=30 and all gates x 3 x 3). UPD. No, it's not. It was a bug in my testcase

Not the worst contest. The statements were mostly clear and easy to understand.

→ Reply

14 months ago, hide # ^ |

+10

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.

→ Reply

14 months ago, hide # ^ |

← Rev. 2 →

how did you dp? dp[L][R][i] where L is number of people in lane 1 and R is number of people in lane 2 and i is the ith gate/level we are at.

1000* (3^29) can be the worst case for L and R which are maybe like ~1e15 so to calculate all dp states wouldnt that give a TLE?

→ Reply

14 months ago, hide # ^ |

← Rev. 2 →

Solution

Track the number of people going to the left gate, right gate, and also track a variable for people gained last round (call these people "assignable". There are only 4 types of possible gate combinations: (x,x), (x,+), (+,x), and (+,+). Observe the situation going from the final gate (call this gate n-1) to the front gate (call this gate 0).

At the final gate, a simple greedy reveals the best option (just assign everyone whichever gate gives you the most people). Call this choice c, and let dp[n-1] = c. How does this help us find the best option for any previous gate?

Observe the (x,+) and (+,x) cases. In these cases, assigning p people to a x2 gate gives us p extra assignable people when going to gate n-1, and 2p people for the x3 gate. Let's consider the (x,+) case for simplicity. If you want to assign people to the right side on the next step, it is actually optimal to assign p people to the left side first, gain p extra people from the x2 (or 2p for x3) than if you had directly assigned to the right side, and then use those p people and assign them in the step following. Doing so gains you p people on the left side and either maintains or increases the number of people on the right side by p, as compared to directly assigning everyone to the right side.

You can actually use the same logic to show that assigning to the x3 multiplier in (x2, x3) or (x3, x2) is weakly dominant to the strategy of assigning to x2 (you gain p extra people to assign to any side compared to x2, and you can then assign those people to the other side if needed). In these cases, dp[i] = (side with mult or better mult), regardless of the value of i.

This leaves us with the cases of (x,x) with the same multiplier and any (+,+) cases. Observe that no matter where we apply our people, the contribution of our p assignable people does not affect how many people we have later. This means we actually have to consider the next step to see what the optimal assignment is. In other words, dp[i] = dp[i+1] in this case.

By backtracking all the way to dp[0], we can then assign people correctly based on the dp shown.

Solution 2/Addendum to Solution 1

→ Reply

naivedyam_mishra

14 months ago, hide # ^ |

← Rev. 2 →

-14

why is my implementation wrong? I trusted the problem statement with the fact that it is guranteed that can have at least 1 such A such that a is the difference of the sums of B and C where both B and C have size n and are made from the array given in the problem. I did swaps to check for a valid one but it gave RTE on test 2 implying there was no such A :(

CODE-

pair<v,v> arr(v b){
    int n = b.size()/2;
    sort(b.begin(), b.end());
    v grp1(b.begin()+n, b.end()), grp2(b.begin(), b.begin()+n);
    int diff = abs(accumulate(grp1.begin(), grp1.end(), 0ll) - accumulate(grp2.begin(), grp2.end(), 0ll));
    if(!binary_search(b.begin(),b.end(),diff)) return {grp1,grp2};
    int sum1 = accumulate(grp1.begin(), grp1.end(), 0ll), sum2 = accumulate(grp2.begin(), grp2.end(), 0ll);
    loop(i,0,n){
        int newSum1 = sum1 - grp1[i] + grp2[i], newSum2 = sum2 - grp2[i] + grp1[i],  newDiff = (newSum1 >= newSum2) ? (newSum1 - newSum2) : (newSum2 - newSum1);
        if(!binary_search(b.begin(),b.end(),newDiff)){
            swap(grp1[i], grp2[i]);
            return {grp1, grp2};
        }
    }
    v alt1, alt2;
    loop(i,0,b.size()) (i&1 ? alt2.push_back(b[i]) : alt1.push_back(b[i]));
    int altdiff = abs(accumulate(alt1.begin(), alt1.end(), 0ll) - accumulate(alt2.begin(), alt2.end(), 0ll));
    if(!binary_search(b.begin(),b.end(),altdiff)) return {alt2,alt1};
    int altsum1 = accumulate(alt1.begin(), alt1.end(), 0ll), altsum2 = accumulate(alt2.begin(), alt2.end(), 0ll);
    loop(i,0,n){
        int new1 = altsum1 - alt1[i] + alt2[i], new2 = altsum2 - alt2[i] + alt1[i], newAltDiff = (new1 >= new2) ? (new1 - new2) : (new2 - new1);
        if(!binary_search(b.begin(),b.end(),newAltDiff)){
            swap(alt1[i], alt2[i]);
            return {alt2, alt1};
        }
    }
}

→ Reply

14 months ago, hide # ^ |

checked your code, the reason why it fails is that it tries to do missing = (large values) — (small values). However, there are some cases where missing can be one of the large or small values. The simplest example is 1 = 2-1, and there are others where it instead hits one of the large values like 6 = 5-3+6-2.

→ Reply

vgtcross

14 months ago, hide # ^ |

Btw, I think that under the given constraints the answer can be larger than uint64_t, which is very strange (just try n=30 and all gates x 3 x 3)

Remember that every person can only go through one of the gates in each pair, so in your example the number of people would triple for every pair of gates they go through. As there $$$30$$$ pairs of gates, the total number of people at the end would be $$$2\cdot3^{30}\approx4\cdot10^{14} \lt 2^{49}$$$, which easily fits in a (signed) long long.

→ Reply

14 months ago, hide # ^ |

-10

in your example the number of people would triple for every pair of gates they go through.

I understand it like this.

Gate1: (1, 1) -> (3, 3), $$$ \delta=4 $$$, adjust to (1, 5), we touch only new people when adjusting lanes

Gate2: (1, 5) -> (3, 15), $$$ \delta =12 $$$, adjust to (1, 17), we touch only new people when adjusting lanes

$$$...$$$

After Gate30 the number is much larger than $$$2^{64}$$$

→ Reply

vgtcross

14 months ago, hide # ^ |

← Rev. 2 →

Total number of people at the beginning: $$$1 + 1 = 2 = 2\cdot3^0$$$
Total number of people after gate 1: $$$1 + 5 = 6 = 2\cdot3^1$$$
Total number of people after gate 2: $$$1 + 17 = 18 = 2\cdot3^2$$$
Total number of people after gate 2: $$$1 + 53 = 54 = 2\cdot3^3$$$

Notice how the total number of people after each gate is $$$3$$$ times larger than before the gate. This must be true, as every person went through a x 3 gate. This means that after gate $$$n$$$ the total number of people will be $$$2\cdot3^n$$$. After gate $$$30$$$, we have $$$2\cdot3^{30} \lt 2^{49}$$$ people, which is not larger than $$$2^{64}$$$.

→ Reply

14 months ago, hide # ^ |

← Rev. 2 →

Indeed, thank you.

Just a bug in my testcase, unfortunately.

→ Reply

14 months ago, hide # ^ |

Today contest was surprisingly good ngl. C was just hard enough but not too hard.

While D is still beyond me, I try greedy but failed.

→ Reply

14 months ago, hide # ^ |

did you dp for D? if so what was your dp state?

→ Reply

14 months ago, hide # ^ |

I tried dp backwards by keeping the lane to which I allocate people (keep the lane with the largest multiplier if at the current lane multipliers are equal or there is only addition). The approach kept giving WA2.

After the contest I solved using forward dp with the state (left count, right count, current delta). Here you should carefully apply the delta only when you necessarily have to. That is when resulting deltas from applying the previous delta are different when the previous delta is applied to the left and to the right.

→ Reply

Ardelion

14 months ago, hide # |

Wow, 2F/1C was chatgpt-able

→ Reply

naivedyam_mishra

14 months ago, hide # |

← Rev. 2 →

-29

Why is Div 2C of all satyam343 rounds unrealistically hard? I think it should be at least 1800-1900 today.

→ Reply

Dominater069

14 months ago, hide # ^ |

+35

my predictors tell me:

B : 919, C : 1417, D : 1717, E : 2023

Not only is C <= 1800, but so is D

your skill issue is not the problemsetter's fault

→ Reply

ycperson

14 months ago, hide # ^ |

-10

I think your perspective is in the minority though. I also found C really difficult out of nowhere.

→ Reply

Dominater069

14 months ago, hide # ^ |

I did not give an opinion. I gave a fact. The rating of C (according to very reliable predictors) is estimated at 1400.

You can find it hard personally, but claiming its a hard problem overall is bullshit.

→ Reply

14 months ago, hide # ^ |

When you realize that C is trivial for large N, it becomes much easier. You really don't have to consider any n > 2.

→ Reply

14 months ago, hide # ^ |

I agree, I found B easier than A in the div1 round. I'm not sure if my solution for A (div2C) is correct.

→ Reply

14 months ago, hide # ^ |

how do these predictors work ?

→ Reply

Dominater069

14 months ago, hide # ^ |

i am not privy to the details, but they are mostly accurate (and CF ratings are usally way more messed up). One predictor is the TLE bot which is available in the Ericchto server.

→ Reply

14 months ago, hide # ^ |

oh ok , thanks for the reply.

→ Reply

Krrishchanchal

14 months ago, hide # ^ |

that bot's not working rn

→ Reply

14 months ago, hide # ^ |

← Rev. 3 →

To make it easier consider that all n > 3 are pretty straightforward.

Sort the array. Now you can separate the full array into two arrays, one called "negatives" and one called "positives", positives being the array of the largest elements.

Note that they are pairwise distinct, so the smallest difference between "positives" and "negatives" will be greater than or equal to (n^2) (you can prove this via pigeonhole principal). Meaning you can just greedily calculate the difference between these arrays and the difference will always be larger than the largest element.

The hardest part is handling the edge cases with a small "n"

→ Reply

14 months ago, hide # ^ |

I'll predict today div2C is 1400 — 1500. Dunno what is D tho... but for sure it's beyond me (1800+)

→ Reply

Proof_by_QED

14 months ago, hide # ^ |

Are you sure Round 979 C is hard? It is rated 1100

→ Reply

Seferoglu

14 months ago, hide # ^ |

I was unable to solve it and it really made me sad too(though I wasn't feeling very well tbh)

→ Reply

Think_Only_Once

14 months ago, hide # |

I got you omsincoconut, you are a big fan of bitmasks

→ Reply

14 months ago, hide # |

If you solve A-C slow you're projected as a specialist.

If you solve A-C fast you're projected as candidate master.

I think this is a bit too much variance for the exact same problems solved

→ Reply

theheatcoder

14 months ago, hide # ^ |

I made 3 wrong submission in A (skill issue) I was 1400th when I solved C and 2500 now

→ Reply

MayankBhakat

14 months ago, hide # ^ |

Na I solved ABC fast today.But my rating change is -1.I think D was gamechanger as usual

→ Reply

14 months ago, hide # ^ |

← Rev. 2 →

This is precisely what i'm talking about, you're a mid expert, and there are specialists who solved the exact same problems as you and lost significantly more rating than you

→ Reply

NeverSpot

14 months ago, hide # ^ |

Maybe I am wrong, but I am pretty sure that just Fast-Solving A-C will never make you a Candidate Master.

→ Reply

l_yzzz

14 months ago, hide # ^ |

A costs even more time than D for me..

→ Reply

14 months ago, hide # ^ |

I solved A-D with somewhat slow C/D (still beating the max you can get with ABC of 3000 points) and I didn't quite get CM performance (my perf was 1895). A-C fast is probably 1750-1800 performance if I had to guesstimate a range of where it would be.

→ Reply

14 months ago, hide # |

please give editorial soon, I think there was some neat idea for div2 E interactive problem because there were only 2 queries , but I couldn't think of any working solution during the contest :(

→ Reply

StelIawinD

14 months ago, hide # ^ |

Ask 0b101010101 and 1010101010

→ Reply

14 months ago, hide # ^ |

yeah I thought about it... but wasn't sure how to interpret the result.. I need better understanding of bit stuff -_-

→ Reply

14 months ago, hide # ^ |

I want to thank you for your hint and along with https://mirror.codeforces.com/blog/entry/140357?#comment-1254569

I was able to upsolve it.

→ Reply

StelIawinD

14 months ago, hide # |

+19

Arcaea is a great game. However this round is not so great as Arcaea.

But I gain rating from this contest, that's good enough.

→ Reply

RDDCCD

14 months ago, hide # |

+70

Next time please give a formulized form for fold. In E I was thinking you should fold everything on the left to the right, but it turns out that you can just fold part of it(which made 01110 can be done in one operation). Wasted half and an hour.

→ Reply

Flaviuuu

14 months ago, hide # |

+55

Looked at the leaderboard for 10 minutes.sumit876 Found this cheaters:

jgiitkgp (problem F) — 309822713 (100% cheater)

d_vaibhavi_singh (problem F) — 309844418 (I think its cheater i am not sure)

2mato_pota2 (problem F) — 309818888 (100% cheater)

sumit876 (problem F) — 309807587 (100000% cheater)

I bet there are a lot more in top 1000. Please take action against these cheaters!

→ Reply

iordache_

14 months ago, hide # ^ |

+10

A lot of people have the same beginning at least of code, written clearly by AI, saying "Compute modular inverse using Fermat's little theorem" or something like that

→ Reply

14 months ago, hide # ^ |

Its insane how these people are so dumb they didnt even erase the comments provided by chatGPT.

→ Reply

YipChip

14 months ago, hide # ^ |

It answered that why so many people passed F rather than E in the contest. When I have solved E, I found those who have passed F is more a lot.

→ Reply

Flaviuuu

14 months ago, hide # ^ |

Well, apparently chat gpt knew how to solve problem F :)))

→ Reply

MarcosK

14 months ago, hide # |

+16

Tests for div1A are weak. My contest solution was the following:

put the largest $$$N$$$ values as positive and the rest as negative. If that sum is not valid, for each number between 1 and 40 (I chose this upperbound without thinking too much), try to add it to the array and brute force over all permutations to see if any of them is valid.

This approach breaks in many cases, like the following:

1
2
100 101 102 200

Hack

Also, for div1C I couldn’t get the O(1) formula for the answer on time, and after contest I asked ChatGPT and it gave me the formula right away :(

→ Reply

14 months ago, hide # ^ |

Can you hack mine too? I did the same first step but if it doesn't work I simply random shuffle until it works.

→ Reply

Raimond

14 months ago, hide # |

I think the checker for problem C testcases is not correct, please look at this submission

309853299 It says "wrong answer More than one number not found in b". but b = {20, 1} and my answer is a = {19, 20 1}, so i don't think the feedback is right.

→ Reply

Raimond

14 months ago, hide # ^ |

← Rev. 2 →

NVM, I found what's wrong, sorry

→ Reply

ZaGOYDA

14 months ago, hide # |

-114

Do you understand, that this round was a complete failure? C has maximally ugly solution that isn't supposed to be in Div2 C and D isn't much better. One author can't make a good round bcs he just can't discuss problems with anyone and they are were bad.

→ Reply

14 months ago, hide # ^ |

+11

Not true, they can discuss problems with the coordinator and testers.

→ Reply

GNBElover

14 months ago, hide # ^ |

+10

Get good bro

→ Reply

LearningMachine

14 months ago, hide # |

I really liked Div2 C:

In order to make sure that the new number being added is unique, it's simplest to try for something less than the smallest or larger than the greatest number in the array.
Since, 1 is the smallest number and it can be present in the input, we can really only go larger. The number is permitted to be upto 1e18, while input is limited to 1e9 so this is another hint of the possibility of doing this.

Now, consider that we have found our new number to be X. We can say try to say that:

(X + S1) - S2 = Amax

This is equivalent to the given condition by placing A1 = Amax and putting the terms of the two parts at odd and even indices.

Now, we can try to make X > Amax.

X = Amax + S2 - S1

Since, S2 is sum of N terms each of which is atleast 1, and S1 is sum of N - 1 terms, it is clear that S2 - S1 > 0 is possible. We just have to choose appropriate S1 and S2. It is simplest to choose the first N elements as S1 and the next N - 1 elements as S2. All that's left is rearranging them in the appropriate order.

An implementation is here: https://mirror.codeforces.com/contest/2078/submission/309808272

→ Reply

itsiftikar02

14 months ago, hide # |

In problem div2C for the array 1 20 my code outputs 1 20 19 on the 19th case of the test case 2 and the verdict is wrong answer

can someone explain please??

the submission link:

→ Reply

dinhvietcuong

14 months ago, hide # ^ |

your 19th answer is 2 3 1

→ Reply

yellow_13

14 months ago, hide # |

+10

Really enjoyed the problems, thanks to the problem setters. Was able to solve div2E just about 5 seconds after the contest ended, I didn't even realize that I was reading the output format incorrectly (I thought we have to put exclamation mark before printing answer, like how it usually is in interactive problems, should've read the statement more carefully :P)

→ Reply

YipChip

14 months ago, hide # ^ |

We both. LOL

→ Reply

toba

14 months ago, hide # |

For Div2F/Div1C, is there a way to guess the formula during the contest?

→ Reply

14 months ago, hide # ^ |

← Rev. 2 →

+22

F(l, r) = cnt_1 — cnt_0 (amount of ones — amount of zeroes), therefore, to calculate score, we're maximizing x(F(l,r)-x). This is achieved at x = F(l,r)/2.
In a string with X ones, there are (X a)(n-X b) subsequences with a ones and b zeroes.
We can easily find formulas for the sums of binomial coeficients, e.g. here

→ Reply

fisher199

14 months ago, hide # ^ |

Hmmmmm, could you describe your approach? I was able to progress a bit, but there seems to be no direct way to obtain a solution from just those identities.

Through some "proof by I made a bruteforce in python and the pattern seems to match", I was able to obtain the following unproven formula:

\begin{equation} \sum_{j = 0}^{\Delta}\binom{x}{j}\binom{n — x}{\Delta — j} = \binom{n}{x + \Delta} \end{equation}

This expression let's us calculate the number of subsequences with the corresponding delta (actually, I've swapped out the x's, so really here it's more like the number of 0s). However, I have been unable to progress from there since any associated expressions end up being to janky (like, we could use the sum over $$$\frac{\Delta^2}{4}\binom{n}{x + \Delta}$$$, but the division is just too out of place (and in any case, completely wrong) and I've yet to find a proper way to even simplify out the inner part).

→ Reply

14 months ago, hide # ^ |

+25

It's too much to describe in a single comment, but basically, first we realize that score(l, r) = floor(f(l,r)^2/4) (due to that x(c-x) thing i described earlier) and f(l,r) = cnt_1 — cnt_0.

Now, if we have X ones and Y zeroes (X+Y=n), we get sum over all possible ways to select ones and zeroes as SUM_i (<= X) SUM_j (<= Y) floor((i-j)^2/4) * C(i X) * C(j Y) (by iterating over all possible amount of 0s and 1s in out subsequence).

Now all you have to do is expand (i-j)^2 (handle even and odd separately), move things that depends on i out of the inner sum and use the fact that SUM_x C(x j) = 2^j, SUM_x [x*C(x j)] = j*2^(j-1), SUM_x [x^2*C(x j)] = (j+j^2)*2^(j-2).

→ Reply

fisher199

14 months ago, hide # ^ |

How would you handle the even and odd cases separately? It seems to me that if we try to split the sum in terms of it's even and odd counterparts for the $$$\Delta = |i - j|$$$, then we would lose the ability to use the aforementioned properties. But apart from that, your method is very clear, thank you!

→ Reply

14 months ago, hide # ^ |

← Rev. 2 →

+25

For even, floor((i-j)^2/4)=0.25(i-j)^2=0.25S^2

For odd, floor((i-j)^2/4)=0.25((i-j)^2-1)=0.25(S^2-1). This is because (i-j)^2 = 1 (mod 4) if (i-j)=1 mod 2.

If we group S^2 together, we're left with -1 * sum over i-j=odd. This is equal to the amount of subsequences with odd length (all subsequences with even length have an even difference between 1s and 0s, and vice versa), which is 2^(n-1).

→ Reply

Vipattim_Jayati

14 months ago, hide # ^ |

have a doubt why you are not considering j to be less than i

→ Reply

14 months ago, hide # ^ |

← Rev. 3 →

I do. The double sum goes over all i in [0, X] and j in [0, Y]. This does include both i less than j and i greater than j.

→ Reply

andreyDagger

14 months ago, hide # |

What was the intuition behind Div1E? How to explain that for single subarray answer is sum of two maximum prefix balances

→ Reply

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

14 months ago, hide # ^ |

← Rev. 3 →

+22

Basically at the start of the process you have range [0, 0], during the process you have a range of sums [l, r] and the events of having to create new operations to be used happens when the sum gets higher than r or lower than l. Graphically, you start at (0, 0), go to (1, a[i]), then (2, a[i]+a[i+1]) and so on while maintining the topmost and lowermost point you've reached. In the end, the cost will be how much you've streched the range so it's the topmost point you've reached (maximum prefix sum) minus the lowest point you've reached (minimum prefix sum).

Edit: added a badly handdrawn representation of what I mean on paint

→ Reply

14 months ago, hide # |

+16

please release editorial

→ Reply

tril0713

14 months ago, hide # |

+43

A super stupid solution to D1A/D2C

You always have to choose $$$n$$$ or $$$n+1$$$ numbers to add and the others to minus, let just choose these numbers by random. 309787629

while(1){
    shuffle(b);
    if(the result sequence is vaild) output and break;
}

→ Reply

AllenAlien0307

14 months ago, hide # |

Div2D I wonder why the greedy approach that adding the additional people into the nearest lane where mul[l] and mul[r] differ is right. Can anyone help me

Also editorial when

→ Reply

omikad

14 months ago, hide # ^ |

← Rev. 2 →

Let's say you had A people if left lane, B people in right lane before some operation, and that operation gave you L people total to be arranged. You put C people to left lane and L-C to right lane (where 0 <= C <= L):

Left lane: A people, some operation, C people

Right lane: B people, some operation, L-C people

Now lets say you see a next operation "+ X * 2" — other operation will follow the same logic. So after this operation you will get X+(B+L-C) new people to arrange:

Left lane: A people, some operation, C people, operation "+ X", 0 people — total this lane A+C people

Right lane: B people, some operation, L-C people, operation "* 2", 0 people — total this lane has B+L-C people

Remaining to arrange: X+B+L-C people

So if you had C=0, you would have X+B+L number of people to arrange, now lets say you take 0 <= D <= L people and put them to left lane:

Left lane: A people, some operation, 0 people, operation "+ X", D people — total this lane has A+D people

Right lane: B people, some operation, L people, operation "* 2", 0 people — total this lane has B+L people

Remaining to arrange: X+B+L-D people

If you compare this outcome (with C=0) to the outcome before (with any C) you can see that changing D to be equal to C these outcomes will be equal in number of people in left lane, equal in number of remaining people to arrange, and right lane is not worse (B+L >= B+L-C). So having C=0 and changing D you could have equal or better outcome compare to any other value of C

Other operations are the same, core trick is to delay arrangement and see which strategy dominates — there will be always one greedy best strategy

→ Reply

TheSensei

14 months ago, hide # |

← Rev. 2 →

In Div2 C, I am getting WA on pretest 2, (test case 19) which is n=1, a = {1,20}, and my answer is {19,20,1} ,which is correct according to me, but wrong according to test cases, 309845177, IMG1 IMG 2 IMG 3 PLEASE HELP !!!

→ Reply

mariza_CY

14 months ago, hide # ^ |

I think your output on testcase 19 is 1 3 2. 19 20 1 is your output on testcase 18.

→ Reply

14 months ago, hide # |

+12

omsincoconut, you put a confirmed cheater, Manasvi, in top 5. I think for at least the top 5, you could've checked their submissions. Would that be possible?

→ Reply

14 months ago, hide # ^ |

why do you think this user cheated ?

→ Reply

cfkage

14 months ago, hide # ^ |

+10

their code for C has AI variable names and comments

→ Reply

14 months ago, hide # ^ |

oh ok, thank you.

→ Reply

Fianchettic

14 months ago, hide # |

+13

I have a pretty straightforward solution for C which was accepted during the contest.

First we re-model the problem. We have a1=a2-a3+a4....-a(2n+1). We re-write this as a1+a3+a5+...a(2n+1)=a2+a4+a6+...a(2n). Let p=[a1,a3,a5,...a(2n+1)] q=[a2,a4,...a(2n)]. We sort b in descending order, push first n+1 elements into p and the last n-1 into q. Therefore our task is now reduced to finding an a(2n) such that a1+a3+a5+..a(2n+1)=a2+a4+a6+..a(2n).

Claim : a(2n)=(a1+a3+a5+..a(2n+1))-(a2+a4+a6+...a(2n-2)). We have to prove that a(2n) lies between 1 and 1e18 and also it is distinct from all a1,a2,..a(2n-1) and a(2n+1)

Since each of a1,a3,a5...a(2n+1) is greater than a2,a4,...a(2n) by construction, it implies that a(2n)>0. It is also not difficult to see that a(2n) would be upper bounded by 2e14.

To prove its distinctness, assume without loss of generality that a1 is the largest number. Re-writing the equation above we have a(2n)-a1=(a3+a5+..a(2n+1))-(a2+a4+...a(2n-2)). Since there are n-1 terms in each expression on the RHS and again by construction, we have each of a3,a5,..a(2n+1) is greater than a2,a4,..a(2n) the RHS>0 . Therefore, a(2n)-a1>0 or a(2n)>a1. Since a(2n) is greater than the largest of a1,a2,...a(2n-1),a(2n+1), it must be distinct from all numbers.

Therefore we have constructed a=[a1,a2,...a(2n+1)]

Note that the approach of push largest n elements into p and the next n into q would not have worked, mainly because we cannot prove that the number obtained would be distinct.

Apologies for the bad formatting

→ Reply

zhutianrui

14 months ago, hide # |

where can i find the solution ? thanks,qwq

→ Reply

14 months ago, hide # ^ |

editorial is not yet published, we will have to wait, which is very sad.

the link for editorial will be added to this post only .. not sure when.

→ Reply

TheSensei

14 months ago, hide # |

+10

My solution for Div 2F/ Div 1C, after some calculations, I found a simple formula for the sum of the scores over all non-empty subsequences s. The formula is ((a-b)^2 + (a+b) — 2)* 2^(a+b-4). here 'a' is count of '1's and 'b' is count of '0's, after this, the query part is very simple, just keep track of a and b, then calculate the answer using formula . CODE FOR REFERENCE.. 309928086

→ Reply

Fookin_Blinders

14 months ago, hide # ^ |

After some calculation? Yeah only if chat gpt does it for u

→ Reply

PallavOP

14 months ago, hide # |

cant find link to editorial?

→ Reply