Codeforces Round 895 (Div. 3)

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
5	adamant	158
7	awoo	157
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Hello Codeforces! Codeforces Round 895 (Div. 3) will start at Sep/07/2023 17:35 (Moscow time). You will be offered 7 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 7 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for wrong submission in this round is 10 minutes.

Remember, that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

take part in at least five rated rounds (and solve at least one problem in each of them)
do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Problems have been created and prepared by: Alexdat2000, FairyWinx, sevlll777, Vladosiya, и MikeMirzayanov.

We would also like to thank:

Vladosiya for the amazing coordination, and help with preparing and balancing a problemset.
MikeMirzayanov for Polygon and Codeforces platforms.
Ormlis for black-red testing.
zwezdinv, BledDest for red testing.
Sokol080808, diskoteka, Sweezy, vladmart, Kniaz, Tima, Riblji_Keksic, 74TrAkToR, pavlekn for yellow testing.
moonpie24, gs20036, Kolychestiy for purple testing.
martin0327, tnaito, no_mind, Pa_sha, SashaT9, ctraxxd, ezdp, BF_OF_Priety for blue testing.
NerfThis, _SADIEM_, YudoTLE, sayed_4 for cyan testing.

Good luck!

UPD: Editorial

Comments (159)

Show archived | Write comment?

NerfThis

14 months ago, # |

I enjoyed the problem set during testing, good luck to all the participants!

→ Reply

susanthenerd

14 months ago, # ^ |

Nice to know that.

_SADIEM_

-12

Problems' quality are just great and fun to be solved UwU

For all participants, May the odds be ever in ur favor❤️

← Rev. 2 →

UwU?

did u just say UwU?

As a tester , I can assure that this is the most balanced div-3 problemset I have ever faced and I recommend to read every problem

Pa_sha

+11

As a tester, I hope you will enjoy this incredible contest

shiv13

Thx, I am looking forward to it.

ezdp

I think the problems are nice. Good luck to participants!

calebmartim

Big chance to reach green tomorrow

I'll stop saying this... But thank you for the contest, I really enjoyed the problems

cxlian

Div.2 rounds will be more important

daoqi

I hope I don't get hacked again

Aucinilhyoegunh

I will try to solve all :>

iordache_

you will definitely get expert back :)

This exam is really harder than I thought, I could only solve 5/7 problems: ((

Bro istg i have figured out how E is solved ages ago I just can't implement aparrently

:((

BRO MY IDEA WAS EXACTLY THE SAME AT YOURS

SuperMo

can you give me a hint on c I'm getting TLE

what can you do if there is an even number different from 2 between l and r?

no_mind

+10

As a tester I recommend reading all problems. All problems are really fun, good luck!

ilovenandini

OMG , Janmashtami round

codack_mayank

Hope to become Cyan in this contest :)

miye

+23

d_sqaure

MY first unrated Div 3.

HHung_fan

Hope to reach 1000 in this contest.

hxano

This is no longer rated for me.. Weird bittersweet feeling

Dr.Mahareeq

I am excited to participate in this contest. Good luck for all participants.

spam_123

Last time, my sister was angry during contest and this time Shri Lord Krishna will be :(

request mike to not schedule a contest on karvachauth 😂

Good luck to everyone! I really hope that I get specialist back

mathmath33

very balanced contest, loved it.

ARMINIUS

$$$t$$$ test cases forces

Michal

problem C is such a troll problem

MJavad

NumberTheory-Forces

Tenz1n

Any hint on how to solve problem E?

Gwynbleidd_

-11

Segment Tree

Ohh ok THx, I was trying to solve this using difference array but was getting TLE

I thought about using prefix sums but it would have taken some time to figure out the correct way for it so instead I used segment trees with lazy propagation which was pretty obvious. Still messed up the code and got 2 WA's

piaolianggg

+13

It is quite easy. Just observe that if you have the XOR of the ones in the entire array and a XOR prefix array. Then when a query asks you to invert [l,r], that just means you set ones^=prefix[l,r], zeros^=prefix[l,r].

Because every element is its own inverse over XOR. So when you remove all the 1 elements, thats the same as adding all the 1 elements. So inverting [l,r] is just adding the XOR of that entire array to ones and zeros XOR.

Got it thnx. I first thought about 2 separate prefix xor array's one for ones and other for zeros complicating it that's why i aborted the idea and went with segment trees.

gurnam771

how u implemented segment tree, can u explain?

222304569

I stored the xor of 0's in the range and xor of all 1's in the range and for lazy updates whenever i find a range that is inside the needed range just swap the values and set its children to do lazy updates whenever they are visited. And before accessing any range check if it has to be updated or not, if yes then update its value and set its children to do lazy update whenever they are visited.

cool thanks and i presume st[node].second is xor of all values in range right?

ya insted of storing xor of all zeros i used xor of all values since you can get xor of zeros just by doing xor1 ^ xorall

SuryaManikanta

i think there is no need of lazy propagation just segment tree works fine but my code is giving wrong answer on first test case its giving 3 2 6 7 0 instead of 3 2 6 7 7 , can some one help me with this.My submission link thanks in advance

perkyfever

if (lx >= a && rx <= b) {
        swap(zero[k], one[k]);
        return;
    }

I think you cannot do just that since you are not removing outdated nodes below which you update from afterwards... You should tell your child nodes to swap as well which is basically a lazy propagation.

If you swap the values for a node it's children's values also have to be swapped

Papercut

It can be solved with sqrt decomposition too :)222263672

KokiCoder

It could be solved by using prefix Xor (same idea with prefix sum)

fonmagnus

I'm too lazy to implement lazy segment tree

sodriet

Just maintain the XOR of numbers with s[i]=='0', and XOR of numbers with s[i]=='1'. Then for each query of type 1, XOR the above 2 numbers with a special number based on the L and R given.

drugkeeper

great contest!

TheAcrux

How to solve E without using segment tree?

← Rev. 3 →

We can use a prefix XOR to get range XOR efficiently. Let us define variables g0 and g1, which is the initial XOR of all the 0s and 1s. Then we set up our prefix XOR array.

Notice that when doing 1 l r, we can just take the xor value and then g0 ^= res and g1 ^= res. This works because when we flip the bits, we flip the whole range of xor for those variables as well

query 2 is just printing g0 or g1.

Submission: https://mirror.codeforces.com/contest/1872/submission/222311808

Byte-Ghifo

You can use prefix Xor 222276789

Jaidhunibavsi

+19

Problem B explanation was not good, almost wasted 1.5 hours to understand

How to solve G? If we have at least >= 20 non-unit elements, the answer is obvious. However, i still don't understand how to find the answer if there are only k < 20 non-units, even in O(2^k) or something like this...

robostac

Two pointer / sliding window to test all segments with exactly k non-unit elements for each value of k.

gabriel88766

I did brute force in O(k^2) with all indexes l, r (less than 30 indexes in my solution)

Find the maximum sum(1,l-1) + sum(r+1, n) + product(l, r) and print l, r.

Sum and product can be calculated with prefix sum and prefix product

But what if the product is really huge, e.g. you have 30 indexes with value = 1e9?

← Rev. 4 →

I just print the index of the first and last number greater than 1 in this case

Suprisingly, I thought about everything i heard from you, but still was not able to build the solution. Clearly, something went wrong... Thanks for explanation :)

dream7

same here.I thought of all the things but still can't able to get to the proper solution/code.

Was it just me who wasted 5 min on problem A because of this:

Spoiler

what is wrong with it ?,for me it was clear and helpful.

Ntg's wrong with it except the fact that my brain decided to stop working for few minutes

How my brain processed Problem C:

Open

Pirate_King

same but problem E

ayush118

I didn't get C

ismoilmirzouz

I made video explaining problems A&B&C&D : https://youtu.be/g7OJ3GVzIhM

I thought it would be useful

Thanks for the contest. It was really amazing.

_Lactosi

I really liked the problemset

CallmeSourav

it feels so good after solving E.

Astroflexx

+22

Amazing contest! Problems were nice and fun to solve. Thanks to Alexdat2000 FairyWinx sevlll777 Vladosiya for the round.

Farr

amazing contest!! I feel G is much more easier than F. Maybe its just my skill issue on graph problem. haha

How did you solve G?

tbh, i think my solution is not correct, however it got AC, so here how its work.

you can simplify the problem into "Find subsegment with biggest difference of its sum and product"

if the multiplication of the element in the array is very large, lets say its over 1e9, then you always can choose segment (l, r), where l is leftmost not 1 element, and r is rightmost not 1 element.

if the multiplication of the element in the array is not very large, then it only has very few not 1 element (at most 60 element maybe, and the rest is "1", and you can ignore the "1" for product). Then you can do some bruteforce work to find which segment is most optimal

I think that works, thanks!

For F I copy pasted strongly connected components code. Now all the nodes are split into their own scc, we can find the minimum cost node in the component, then we need to move in that cycle and end at that node that we picked.

Submission: https://mirror.codeforces.com/contest/1872/submission/222333264

wow i really didn't think of that. Thanks!

My intuition for F was something like this :

It would be beneficial for us to sell animals which isn't feared by anyone first (because that animal must be afraid) so start sell the animal with 0 in-degree. For this we can use topological sort

Now we left eith the groups of cycle. For each group, we can see that all animals will be sold for $$$2c$$$ price except the last one. That's why to maximize the sum, we just need to find which animal is the cheapest in the cycle and sold it last

samadeep

great solution

I used the topological sorting after removing an edge at the optimal point to break cycles

anjkk01

Have someone did F with path compression ?

RecursiveCo

What do you mean by path compression? The DSU trick?

Yup

In that case, I did solve it with path compression but only because I frequently use DSU to track connected components. It isn't really necessary (but if you want to use DSU it's absolutely necessary).

muhammadhasan01

← Rev. 9 →

Quick Editorial:

Problem A

Problem B

Problem C

Problem D

Problem E

Problem F

Problem G

_implicit

How to come up with the formula for problem A?

WLOG (Without Loss of Generality) let us assume $$$a \leq b$$$, then it is optimal to pour $$$c$$$ from $$$b$$$ to $$$a$$$.

We can see that the differences of $$$b$$$ and $$$a$$$ decrease by $$$2x$$$ if we try to pour $$$x$$$ from $$$b$$$ to $$$a$$$.

We need to make the differences equal to $$$0$$$, then the intuitive way to find the formula is by using ceiling from the differences of $$$a$$$ and $$$b$$$ divided by $$$2c$$$

himanshubanerji

Ummm I still couldn't understand how you reached that formula >.< . Ummm can you explain why did we go about dividing 2c ?

anandchourasia007

In 1 operation, you are not just removing c from the larger vessel but also adding c to the smaller vessel. So, the difference reduces by 2c. You have to find how many operations are required.

Yath

Can we say in Problem F , that after eliminating nodes with indegree = 0 (There cost is counted as 2 * C[x] , we are left with only loops (can be different components) , with each node having indegree = 1. Now for each loop , we can just calculate the node that we should remove at the very last so that its cost is counted C[x] while the other ones' cost in the loop is counted 2*C[x] ??

stash

Yes, when there is loop, first you will remove the parent of element with smallest cost first such that element with smallest cost will get removed at last.

arpandesai0

In problem G solution is should be a[i] > 1.

Oops typo there, fixed.

In G you brute force if a(i)>1 <=48 , but to be safe I did for <=50

parag776

nice solution to G key point was product greater than some max value!!

Hey cf folks, looking for a coding friend who wants to upsolve with me, would really help if we could discuss answers after a contest gets over.

Also since the editorial is not out yet, can anyone explain me the intuition for problem C ?

If l != r and r is at least 4 then one of the numbers is 2 and the other is floor(r/2)*2-2, this works. If l != r and r is less than 4 there is no answer

Otherwise we need to find a divisor of l that is not 1 or l, we can bruteforce until sqrt(l) or use the Sieve of Eratosthenes to factorize l. If l is prime then there is no answer

Still not able to understand it >.< I guess I'll leave it at that

Apologies, I realized I didn't explain properly.

If l = r then the sum of a and b must be equal to l, so if l is prime there is no answer (suppose there was, then there exists c >= 2 that divides a and b and therefore divides l as well which can't happen.) Otherwise we can choose a = min divisor of l that is not 1, and b=l-a.

Otherwise, notice that a+b >= 4 because a and b are both at least 2. So if r < 4, there is no solution. Otherwise there exists a solution. Consider a = 2. We can choose b such that b is even and a+b is either r or r-1, assuming l != r (we handled the other case above), which is where b = floor(r/2)*2 — 2 comes from.

ahmedyoussefg

In problem D, I changed n,x, y type from int to long long and it got accepted. How could this be possible? [n maximum is 10^9]

Wrong answer here

Accepted here

You have the line "using namespace std;" so when you call lcm(x,y) with x and y as int it ignores your custom lcm function and uses std::lcm(int,int) as that matches better, but that returns an int so it overflows.

A: The answer will be cd(abs(a-b), 2*c) because you have to move half the difference from the biggest vessel to the smallest one. and this will take you cd(abs(a-b)/2, c) moves.

B: Each trap forces you to be back past it after s-1 seconds. In that time you can move (s-1)/2 units to the right of that trap and sitll have time to return. Each trap puts on such restriction on your trip, so you just iterate over the traps and do ans = min(ans, d+ (s-1)/2)

C:If l and r are at least 4 apart, there is a multiple of 4 between them, lets call it k, and then k/2 is even, so we can set x= k/2 and y=k/2. If l and r are less than 4 apart, we can brute force all divisors of l, l+1, l+2 .. r. And then if d | l, we can return x = l — d and d. This will always find a solution, because if gcd(a,b) = g, and a+b = k, then g | k. So the answer will always be found among the divisors of the numbers between l and min(r, l+4)

D: You want to put the biggest elements of the permutation of multiples on x, and the smallest on multiples of y. You can ignore the indexes that are multiples of both. However, you can't calculate this naively. because n= 1e9. However, you can use triangle number sum n(n+1)/2. the number of multiples of x that are not multiples of y is n/x — n/lcm(x,y) = k. so do n(n+1)/2 — (n-k)(n-k-1)/2. To get the multiples of x, and do -(y-n/lcm(x,y))((y — n/lcm(x,y))+1)/2 to subtract multiples of y.

E: The array never changes, so we can calculate an XOR prefix array. After this we can calculate the XOR of all the ones-position in the array and all the zero-position in the array.

Then, whenever we are queried, we can just set ones^=prefix[l,r] and zeros^=prefix[l,r]. That is, we set our ones and zeros XOR counters to XOR the XOR of the element in [l,r]. The reason we can do this is because when we invert [l,r], we remove all the ones from 1, and add all the zeros. However, removing the ones is the same as adding the ones because every element is its own inverse under XOR. Same logic applies for zero

F: All the nodes with indegree zero, we can remove with no issues, because no one is afraid of them, so we lose nothing by removing them early. After we've done this, there might be new nodes with indegree zero, so we remove those as well (and add to answer in the order we remove them).

After we've removed all the nodes with indegree zero, there will only be cycles left. This is because every node here has outdegree 1 (they are only scared of one other animal).

So we can go through the cycles and find the animal with the least cost, call it s Then we go through the cycle and remove all elements in order, starting with A[s], and ending with s. That way we get twice cost of all the animals except s (which has least cost, so this is optimal).

I implemented the same for F , can you tell me where I am wrong ?? https://mirror.codeforces.com/contest/1872/submission/222350254

IngaleAnkur10

Same here: can someone please check why my final answer is not even a permutation? Can someone please think of some test-case here? 222376285

hamidh100

Just checked out the problems and noticed that problem F was 99% same as abc256E

ibrahimwq

they are not literally same lol, in this problem you have to construct permutation

treasuryonly

Problem A: does not have to be an integer

Problem B: best illustration in contest

Problem C: even number, not 2, odd number, not prime, not 1

Problem D: sum top for x, sum bottom for y, duplicate LCM

Problem E: Lazy Segment Tree (but not enough time)

Problems are enjoyable! Thank you guys for the contest!

ME TOO

__SAK__

E can be solved without segment tree. Its just xor prefix array

alpha1215

I lost D due to a typo long long -> long T_T

NanYanNanChui

I solve C like this 222257731.I don’t want to discuss in categories(because I got Time limit exceeded :(

KienPS

For problem E, I tried to solve it using the segment tree here. I pre-compute the XOR of the entire array a and store the precompute XOR of those values where s[i] = 1 in the tree. So then XOR of those that are zeros in s equals to all ^ one. The time complexity should be $$$O(max(q, n)logn)$$$, but I got TLE. Can anyone tell me what I did wrong?

U don't need segment tree pre calculating XOR of the array just like a prefix_sum is enough. Just think that there's no an actual range update here due to XOR facts..

Oh thanks! I re-implemented and it got accepted!

For range updates you need to use lazy propagation, otherwise if you try to update all values in the range then cost for each update is O(n). If you are given q queries each of size n leading to O(n.q) so the TLE

Ah yes, I forgot the lazy propagation :(. Was spending too much time on thinking about what to store in the segment tree.

Rushdi

That's very good contest i liked how does E work i thought that E is segment tree but i did learn a knew thing while thinking that you can make prefix xor , thanks for the contest.

In E I did sqrt decomposition lol

codemohitpra2103

Can u share your code??

Does E require square root decomposition ??

it doesn't require but you can overkill with it just like I did

arutsudar

Proper Div 3 round after a long time.

NimaAryan

I didn't expect to learn something new in Div. 3 contests (the lemma about Functional Graphs, I skipped my theory classes :/), so thanks a lot.

manitianajay45

Video Editorial For problem A to G.

code_with_baby

Did somebody notice , that in todays G 1<=a[i]<=1e9 , but in examples they took a[i]=0 in some places .

lol where?Recheck,you saw wrong

stdfloat

My worst div.3, I solved only A-D(lately, beacuse of C) in contest, upsolved F. For me: C>D, E>F. But I couldn't solve F in contest. Hope better next time.

I'm not rly good at maths can someone plz explain how did he solve D by steps

Ryomen_Sukuna393

I want some hints for problem F. If we make a directed edge graph out of the given things, with

$$$a->b$$$

meaning b is afraid of a, it would mean we actually have to implement toposort when the graph is acyclic. The problem arises when the graph become cyclic.

In that case we observe that for a cycle say,

$$$a->b->c->d->a$$$

, if we start from anywhere, let us say, from d, and go in the reverse direction of the edges, (i.e d->c->b->a), we will get the

$$$profit = 2d+2b+2c+a$$$

. In other words, if we start at node x such that

$$$x->y$$$

is an edge in the cycle, the profit we get is : profit = 2(Sum of profits of all the nodes) - y. This hints that we need to keep track of all the cycles in the graph.

Further we observe that the In Degree of any node will not be greater than 1, It means that two cycles cannot have any node in common, and also any two cycles are disconnected (it can be proved by contradiction). So now the problem reduces to finding the strongly connected components of the graph (as the strongly connected components will only have cycles in them), and then to track the minimum of the nodes present in the cycle.

Is there any efficient way to do this?

MickeyIsAwesome

Hey you're on the right track. Don't make the question too complicated tho. As you said indegree and cycles are important information for this question. Take some of the given samples, and try to reduce them into solvable graphs.

Hint :- As each vertex has exactly one outgoing edge, so any cycle if present will be a simple cycle. Also each vertex will always have exactly one outgoing edge, so maybe solving for a cycle isn't that hard.

You'll get the solution if you try to find a way for the given samples. I solved sample 2 and 6 when I did the question.

khangai11

My solution is Change the problem like this: if we sell Animal i there is a cost sum(C[j], for all animal j that afraid of animal i). Using priority_queue you can sell the animal(i) whose cost is minimum currently. And update cost of animal a[i] and push this to priority_queue.

Kahn's toposort algorithm is still useful — it can give you an ordered list of nodes that aren't in cycles (so can be sold for 2*C). You can then just calculate the cycles for any nodes not in that list (using a simple dfs as there is only one option at each node).

xyggzsf

nekoyukino

I'm not 100% sure, but I think the real issue is that your n inside function init is greater than the N you used to declare arrays. This can lead to overflow problems and unknown errors, including Wrong Answer. Your submission got AC when your n is smaller than N.

Actually, your code always gets RE on my computer. It's a little strange why you didn't have this during contest, maybe because you didn't enable O2 optimization when you debugged locally? Specify -O2 can sometimes help expose some issues like overflow :D

Ansh_2003

I gave the contest and solve 2 questions but still i am unrated and the this contest is showing unrated for me i don't understand what is this if anyone has idea about this please tell me

proitdtdelre

Don't worry it will take some time to update the ratings

Kartik.

There was a hacking phase...now system testing will take place , after that they will update ratings. Probably wait for 3-4 hours

chenxiaoming

Hope to become an expert, good luck

dualthread

Cannot understand why people are jumping to segment trees to solve problem e. It's a div3 e, not div2 e!

sahaun

It's easier for me to think using segment trees.

Also it's not about solving problems the intended way. It's about being able to apply the tools available to you.

I agree!

I had like 45 minutes to implement and still didn't manage to do it somehow, I guess I'm not experienced enough with seg trees

rohit.2.3.5

Happy that I solved first 5 problems in this contest , but could have solve little faster to get good rank. Hope to be Cyan again after rating update.

MostafaM.Galal

Good contest hope pupils touch cyan their first time after rating

another_alwcod_nn

I put long long instead of long double when doing G (was working with log10) so got WA when rejudge, weak pretest :v but overall i enjoyed the contest.