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
I enjoyed the problem set during testing, good luck to all the participants!
Nice to know that.
Problems' quality are just great and fun to be solved UwU
For all participants, May the odds be ever in ur favor❤️
.
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
As a tester, I hope you will enjoy this incredible contest
Thx, I am looking forward to it.
I think the problems are nice. Good luck to participants!
Big chance to reach green tomorrow
I'll stop saying this... But thank you for the contest, I really enjoyed the problems
Div.2 rounds will be more important
I hope I don't get hacked again
I will try to solve all :>
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
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?
As a tester I recommend reading all problems. All problems are really fun, good luck!
OMG , Janmashtami round
Hope to become Cyan in this contest :)
Good luck!
MY first unrated Div 3.
Hope to reach 1000 in this contest.
This is no longer rated for me.. Weird bittersweet feeling
I am excited to participate in this contest. Good luck for all participants.
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
very balanced contest, loved it.
$$$t$$$ test cases forces
problem C is such a troll problem
NumberTheory-Forces
Any hint on how to solve problem E?
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
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.
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
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
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
It can be solved with sqrt decomposition too :)222263672
It could be solved by using prefix Xor (same idea with prefix sum)
I'm too lazy to implement lazy segment tree
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.
great contest!
How to solve E without using segment tree?
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://codeforces.net/contest/1872/submission/222311808
You can use prefix Xor 222276789
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...
Two pointer / sliding window to test all segments with exactly k non-unit elements for each value of k.
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?
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 :)
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:
mass of water poured in one move does not have to be an integer.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:
same but problem E
I didn't get C
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.
I really liked the problemset
it feels so good after solving E.
Amazing contest! Problems were nice and fun to solve. Thanks to Alexdat2000 FairyWinx sevlll777 Vladosiya for the round.
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://codeforces.net/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
great solution
I used the topological sorting after removing an edge at the optimal point to break cycles
Have someone did F with path compression ?
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).
Quick Editorial:
With a little bit of math, the answer is $$$\displaystyle\left\lceil\frac{|a-b|}{2c}\right\rceil$$$
For every trap $$$i$$$, let's define $$$x_i$$$ as the minimum room number such that we will be trapped on room $$$d_i$$$ if we go to room $$$x_i$$$.
We can then find that: $$$\displaystyle x_i = d_i + \left\lceil\frac{s_i}{2}\right\rceil$$$
Let $$$p$$$ be the minimum among all $$$x_i$$$ $$$(1 \leq i \leq n)$$$, then the answer is $$$p-1$$$.
Define $$$p_x$$$ as the divider of $$$x$$$ such that $$$x > p_x > 1$$$, then the answer is $$$(p_x, x - p_x)$$$.
We can find $$$p_x$$$ with Sieve of Eratosthenes, note that if $$$x$$$ is a prime then there is no answer.
Let $$$z$$$ be the LCM of $$$x$$$ and $$$y$$$, let's define $$$C_x$$$ and $$$C_y$$$ as the number of indexes that $$$x$$$ and $$$y$$$ will have such that there are no shared indexed between $$$x$$$ and $$$y$$$.
We can see that:
We can then put values $$$n,n-1,\dots,n-C_x+1$$$ for $$$x$$$ indexes and $$$1,2,\dots,C_y$$$ for $$$y$$$ indexes.
Let $$$\displaystyle F(x) = \frac{x \times (x + 1)}{2}$$$
Then the answer is: $$$F(n) - F(n - C_x) - F(C_y)$$$
Let us denote $$$A$$$ as the XOR of all the numbers in $$$a$$$ and $$$X$$$ as the XOR of all the numbers of indices $$$i$$$ of $$$a$$$ where $$$s_i = 0$$$.
Let us define $$$f(l, r)$$$ as the XOR of all indices of $$$a$$$ in range $$$[l, r]$$$.
Then in the first operation, we will have that $$$X$$$ is updated to $$$X \oplus f(l, r)$$$.
In the second operation, if $$$g=0$$$ then we can output $$$X$$$ otherwise we output $$$A \oplus X$$$.
We can use prefix XOR to compute $$$f(l, r)$$$.
For this types of problems, we can imagine a graph where there is an edge between node $$$u$$$ and node $$$a_u$$$.
Then there will be a number of components, inside of each component there will be exactly one loop.
We need to find the minimum cost node inside each loop so that we can put it in the last indexes of $$$p$$$.
There are obviously lots of answers, one of being is we can put all the nodes "outside" the loops first (we can use some sort of toposort for this), and then we can put the nodes inside the loops by carefully putting the minimum cost node in the last. We can do these for each components.
Notice that if all the multiples of $$$a$$$ is very large (we can set the max boundary as $$$10^{18}$$$) then it will always be optimal to multiply all of it, but here it will be more optimal to put $$$l=$$$ the smallest $$$i$$$ such that $$$a_i > 1$$$ and $$$r=$$$ largest $$$i$$$ such that $$$a_i > 1$$$.
If the multiples of $$$a$$$ is not large, then there will exist only a small numbers $$$i$$$ such that $$$a_i > 1$$$ (probably not going to be more than $$$100$$$ depending on the scenarios).
Let $$$S$$$ be the set of indices $$$i$$$ such that $$$a_i > 1$$$.
Let us define: $$$\displaystyle F(l, r) = \prod_{i=l}^{r} a_i - \sum_{i=l}^{r} a_i$$$
We can then bruteforce all pair of indices in $$$S$$$, then we need to find $$$(l, r)$$$ using $$$S$$$ such that $$$F(l, r)$$$ is maximized.
We can use prefix sum / prod for this.
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$$$
Ummm I still couldn't understand how you reached that formula >.< . Ummm can you explain why did we go about dividing 2c ?
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.
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] ??
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.
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
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.
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://codeforces.net/contest/1872/submission/222350254
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
Hi
Just checked out the problems and noticed that problem F was 99% same as abc256E
they are not literally same lol, in this problem you have to construct permutation
Problem A:
does not have to be an integerProblem B:
best illustration in contestProblem C:
even number,not 2,odd number,not prime,not 1Problem D:
sum top for x,sum bottom for y,duplicate LCMProblem E:
Lazy Segment Tree(but not enough time)Problems are enjoyable! Thank you guys for the contest!
ME TOO
E can be solved without segment tree. Its just xor prefix array
I lost D due to a typo long long -> long T_T
I solve C like this 222257731.I don’t want to discuss in categories(because I got Time limit exceeded :(
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.
I made video explaining problems A&B&C&D : https://youtu.be/g7OJ3GVzIhM
I thought it would be useful
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
Can u share your code??
link
Does E require square root decomposition ??
it doesn't require but you can overkill with it just like I did
Proper Div 3 round after a long time.
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.
Video Editorial For problem A to G.
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
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
I want some hints for problem F. If we make a directed edge graph out of the given things, with
meaning b is afraid of a, it would mean we actually have to implement
toposortwhen the graph is acyclic. The problem arises when the graph become cyclic.In that case we observe that for a cycle say,
, if we start from anywhere, let us say, from
d, and go in the reverse direction of the edges, (i.ed->c->b->a), we will get the. In other words, if we start at node
xsuch thatis 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 Degreeof any node will not be greater than1, 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?
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.
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).
.
I'm not 100% sure, but I think the real issue is that your
ninside functioninitis greater than theNyou used to declare arrays. This can lead to overflow problems and unknown errors, including Wrong Answer. Your submission got AC when yournis smaller thanN.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
-O2can sometimes help expose some issues like overflow :DI 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
Don't worry it will take some time to update the ratings
There was a hacking phase...now system testing will take place , after that they will update ratings. Probably wait for 3-4 hours
Hope to become an expert, good luck
Cannot understand why people are jumping to segment trees to solve problem e. It's a div3 e, not div2 e!
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
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.
Good contest hope pupils touch cyan their first time after rating
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.
Can someone please identify the problem with my submission for D? I'm pasting it below for easy reference. Thanks.
222341350
maybe overflow like issue? logic wise it seems correct
It was a very cool round, thanks to the creators!
Indians are rocking everywhere.
Good Luck Everyone for System Testing.
Why is this round being retested now?
I have got a skip on this problem : 222280755 for the problem 1872E
this template of code is shared with me and my friends as we all are in the same training
and the segment tree code is also a template, you can see my previous codes, all of them with the same template, so please give me the points back