Thanks for joining the contest!
Tutorial
Solution
1872B - The Corridor or There and Back Again
Tutorial
Solution
Tutorial
Solution
1872D - Plus Minus Permutation
Tutorial
Solution
Tutorial
Solution
Tutorial
Solution
Tutorial
Solution
why are we taking ceil in problem A?
because if we take floor or don't take anything we will not be considering the residue.
Residue here means , for example taking a = 5, b = 18, c = 5. Therefore after the first pour we will have a = 10, b = 13, c = 5
Now the residue is 3lt but since c = 5 we cannot pour another full bucket of c thus we will be pouring the residue ( remaining 3lt with c ) thus we have to take ceil to consider this residue or rather we could say in a case where the final water transfer of quantity less than the value of c
I hope you understood it
Does anyone have a solution to problem E through a segment tree?
I wonder, too.
I used sqrt decomposition
how?
Explanation: https://codeforces.me/contest/1872/submission/222551813 Code in C++: https://codeforces.me/contest/1872/submission/222487892
Excellent explanation of another solution method, thank you very much!
This is my submission using lazy segment tree.222476225
Hello why does my code output the wrong answer on test 2? https://codeforces.me/contest/1872/submission/246666885 It seems that we have almost the same solution
In your push function, you assign
add[v*2]
andadd[v*2+1]
to 1. However, it might be possible that it was already 1. In that case, the push function should cancel the effect andadd[v*2]
andadd[v*2+1]
should become 0. So changeto
or alternately
Thanksss
you can read more about lazy segment tree here: https://codeforces.me/blog/entry/15890
my solution: 222252960
This is my submission using segment tree.222537194
This might help 222282535.
u can use simple prefix array method to find the xor of a segment theres no need of a segment tree here , ps u can see my solution .
he didn't ask it tho
Yes, I know, I decided that during the contest, but it’s interesting to know another solution.
222359696 I had somewhat similar thinking process in D, however, my way of calculation led to imprecise numbers where there were lots of digits. But why exactly? Test 4 failed because there were differences in the 17th tenth lol.
In Python the
/
operator is float division, even if your result could be an integer, even something dumb like:When you do
int()
it's already too late! replace/
with//
, the integer division operator, in the score calculation in your solution, it makes your solution work.For problem G, let's say we want to find under what conditions it is optimal take the product of a subarray .
Suppose we have a prefix product equal to $$$p$$$ at index $$$i$$$ and we are considering joining this product to a $$$>1$$$ element at index $$$j > i$$$ to take the product. In the worst case, we have the array $$$A = [p, 1, ..., 1, 2]$$$ with $$$n - 2$$$ ones in between the first and last element.
For the product to be optimal: $$$2 * p > p + (n - 2) + 2 \Rightarrow p > n$$$, so the total product ($$$2 * p$$$) must be strictly bigger than $$$2n$$$ as mentioned in the tutorial.
For problem F, can someone please find the scenario where this submission is failing? 222376285
problem A ,why 2*c ?
It is because what we do is: we take d/2 from the greater one and add d/2 to the lesser one.
Good problem and fast editorial, Thanks for this contest!
%%%
We can make the bound even better ( although not needed ) for problem G. We shall first exclude all prefix and suffix ones to get new array. If we include all elements of this new array , the answer is atleast P ( product of all elements ) — 2 * 10^5*10^9 ( here by answer I mean product(subarray(l,r)) — sum(subarray(l,r)) as we are maximizing it.). Which means it is atleast P — 2^48. Now any subarray other than this full array will have product at most P / 2. so answer for any subarray is atmost P / 2. Now , P — 2 ^ 48 >= P / 2 implies P >= 2 ^ 49. hence we can check if P >= 2 ^ 49 ( instead of 60 . )
Alternate thought process of Problem A:
WLOG assume, a<b (otherwise swap a and b) let m = (a+b)/2, now we need to pour water from vessel B to vessel A such that both vessel contain 'm' unit of water. We can only think in terms of vessel B (vessel A will be automatically handled). So we need to transfer (b-m) water from vessel B (to vessel A). Each time we can pour almost 'c' unit.
So ans = ceil ((b-m)/c)
My submission:222221006
Silly me has written a lazy segment tree for E.
same here :(
problems were well balanced thank you for the contest
Editorial solution for problem G TLE on test 61
Fixed
I'm new to CP. I used codeforces for 10 days, a few months ago, to improve my implementation skills. But the thing is, I can't solve questions like C (the gcd one). Since I'm new to cp, I wouldn't mind if I can't solve the D or above problems. I really want to learn how to solve math problems. Like it's so hard. I feel like it's totally different from my college-level math. Though they are all very basic math problems, I can't solve them on codeforces or codechef. I try to solve a math problem (div2/3 A) but when I look at the editorial, it's just only an equation. Can anyone suggest some resources to learn how to solve these gcd, prime numbers, combinatorics, kind of math problems on codeforces?? I'm gonna take cp seriously from now.
Thank you!
https://cses.fi/problemset/ may be a good place to practice basic problems.
Thanks for the tutorial.
Another greedy solution for F https://codeforces.me/contest/1872/submission/222276481
222445465 does anyone know why i am getting runtime error in this code?
You are trying to access
prep[1000000]
but it is out of bounds ofprep
.prep
has a size of1000000
, which means it has indices0
to999999
still doesnt work. the thing thats weird is that, from testcase 1 to 7, it works perfectly well, but when it reaches 8, it stops working. what is this wizardry.
What do you mean by "doesn't work"? What did you change? What is the verdict?
Oh I think you meant to have $$$10^7$$$ instead of $$$10^6$$$ as the maximum size, since that's the maximum constraint.
So you need to change what I mentioned earlier and the size.
AC: 222452376
For G, there probably be a roughly prof: say we have a1(>1), 1, 1, 1,... (we have x ones), P1(products of remaining numbers), so if we left a1 the result will be a1 + x + P1, otherwise it's P1 * a1. Then a1+x+P1-P1*a1=(1-a1)*P1+a1+x, because P1 is large enough, and a1>1, a1+x+P1-P1*a1 will always < 0, so a1+x+P1 < P1*a1.
Why is there inconsistency in the rating change mentioned in friends standing and the friends rating change? My rating change displayed in the last column of friends standing and in friends rating change are different.
because that is given by rating predictor extension i believe which is not super accurate especially for div3 and div4 contests.
Interesting div.3 contest.
your solution doesn't deserve to be intended/official , it's a overkill
How to solve problem E if instead of finding XOR of elements we had to find sum?
Calculate the value of the bitwise XOR of the numbers ai for all indices i such that si=g
Here, instead of bitwise XOR, we had to calculate sum.
How to solve F if an animal was afraid of more than one animal?
1599 is like a clown. Please, give me one extra point༼ つ ◕_◕ ༽つ.
Wow, problem D has been explained amazing
Problem F can be solved using std::multiset. My solution is here
nice solution
Simple Neat and Clean code for Codeforces Round 895 (Div. 3)
krishnash1355
Solutions:
Problem A : 1872A - Two Vessels Submission A : 222226952
Problem B : 1872B - The Corridor or There and Back Again Submission B : 222235441
Problem C : 1872C - Non-coprime Split Submission C : 222275700
Problem D : 1872D - Plus Minus Permutation Submission D : 222260066
Problem E : 1872E - Data Structures Fan Submission E : 222285746
I don't understand A. Why is it 2*c, why not c, 3c, 4c??
We want $$$a=b$$$, then let's say $$$a<b$$$. So $$$a+x=b-x$$$ (take $$$x$$$ from bigger one to small one).
$$$2x=b-a \rightarrow x = \frac{b-a}{2}$$$.
Ok, in one operation you can only add $$$c$$$ to $$$x$$$, then answer is $$$\lceil \frac{x}{c} \rceil$$$.
$$$x$$$ may not be an integer, so use this trick: $$$\lceil \frac{x}{y} \rceil = \lceil \frac{k \cdot x}{k \cdot y} \rceil$$$, answer is $$$\lceil \frac{2x}{2c} \rceil$$$ or $$$\lceil \frac{4x}{4c} \rceil$$$ or $$$\lceil \frac{2n \cdot x}{2n \cdot c} \rceil$$$.
Example:
Lovely F :))
Really good problems, thanks authors
for problem E ,1e15 or 2^60 or 2^48 are very loose bounds .It seems to me that the solvers that passed the test cases didnot actually solve the problem.Nobody here has comeup with such bound .I actually want to understand the problem.
1e9 is biggest needed but even the cases pass upto 4e5
Why is sample test 3 for problem F correct?
3 4 5 1 2
With this output the money you get is 31, but if the output is:
4 5 1 2 3
The money is 32. What?
1 is afraid of 2
2 is afraid of 1
3, 4, 5 are afraid of 1
Maximum cost will be 31:
For 4, cost will be 2*1 = 2 -> because 1 is still not sold
For 5, cost will be 2*1 = 2 -> because 1 is still not sold
For 1, cost will be 2*9 = 18 -> because 2 is still not sold
For 2, cost will be 1*8 = 8 -> because now 1 is sold and 2 is not afraid of any animal
For 3, cost will be 1*1 = 1 -> because now 1 is sold and 3 is not afraid of any animal
Total = 2 + 2 + 18 + 8 + 1 = 31
Thanks, i read the statement wrong
why my code is giving wrong output?
Submission Link Problem G
In problem F, the tutorial says "As each animal is feared by at least one other animal." But in the problem statement, it doesn't say this. It only says "Each animal is afraid of exactly one other animal." Therefore implying some animals may be feared by multiple animals, which would then contradict the tutorial's statement.
Could you please clarify which is correct?
I solved problem F using the same logic as the editorial but am getting a MLE, could someone explain what is the bottleneck in this code 265848420
Hello. I want to know why the upper bound can be $$$2n$$$ in problem G. Can anyone tell me?
.