sevlll777's blog

Codeforces Round 895 (Div. 3) Editorial
By sevlll777, history, 8 months ago, In English

Thanks for joining the contest!

1872A - Two Vessels

Tutorial
Solution

1872B - The Corridor or There and Back Again

Tutorial
Solution

1872C - Non-coprime Split

Tutorial
Solution

1872D - Plus Minus Permutation

Tutorial
Solution

1872E - Data Structures Fan

Tutorial
Solution

1872F - Selling a Menagerie

Tutorial
Solution

1872G - Replace With Product

Tutorial
Solution
  • Vote: I like it
  • +82
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why are we taking ceil in problem A?

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because we need to be certain that d gets to 0. We need at most floor to make sure that d < 2 * c and then one more to be sure that d = 0.

    → Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    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

    → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    because if there is any fraction then this fraction alone needs one pour to be transferred

    → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it -19 Vote: I do not like it

    becouse we use the (a+b)/2 + 1 . That is equl ceil(a+b)/2

    → Reply
»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Does anyone have a solution to problem E through a segment tree?

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the fast Editorial.

→ Reply
»
8 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 3   Vote: I like it +21 Vote: I do not like it

    In Python the / operator is float division, even if your result could be an integer, even something dumb like:

    >>> print('{:f}'.format(100000000000000000000000/1))
99999999999999991611392.000000

    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.

    → Reply
»
8 months ago, # |
  Vote: I like it +31 Vote: I do not like it

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.

→ Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

For problem F, can someone please find the scenario where this submission is failing? 222376285

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

problem A ，why 2*c ？

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is because what we do is: we take d/2 from the greater one and add d/2 to the lesser one.

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I understand, because when we take c from the large and add c to the small, then calculating the difference again equals 2c. thank you

      → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good problem and fast editorial, Thanks for this contest!

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Silly me has written a lazy segment tree for E.

→ Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

problems were well balanced thank you for the contest

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Editorial solution for problem G TLE on test 61

→ Reply
»
8 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

B. The Corridor or There and Back Again

As we are supposed to return to room number 1, for the following test case the correct answer should be k=2 and not k=1

test case:

1
1
1 2

correct answer is k=2, 1st second : room 1 -> room 2 2nd second : room 2 -> room 1

as after 2 second the person is back to room 1, the maximum value should be k=2.

→ Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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!

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the tutorial.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

E task is 10 XOR out of 10

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem A, How does adding {+ 2c — 1} in the nominator calculate floor value?

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Another greedy solution for F https://codeforces.com/contest/1872/submission/222276481

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

222445465 does anyone know why i am getting runtime error in this code?

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are trying to access prep[1000000] but it is out of bounds of prep.

    prep has a size of 1000000, which means it has indices 0 to 999999

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What do you mean by "doesn't work"? What did you change? What is the verdict?

        → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          dang, i didnt know vectors can be that big, thank you for the help!

          → Reply
        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Hello , please help In the tutorial for 1872C, Under point number 1 it is mentioned that we only need to calculate shortest composite number in the interval [r,l] but in the question we are asked to report two non coprime numbers that sum to a number(that turns out to be composite) in the interval [r,l] so once i have calculated the favourable composite number how to calculate the values of a and b ? thanks

          → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    because that is given by rating predictor extension i believe which is not super accurate especially for div3 and div4 contests.

    → Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it -9 Vote: I do not like it

Interesting div.3 contest.

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    your solution doesn't deserve to be intended/official , it's a overkill

    → Reply
»
8 months ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

1599 is like a clown. Please, give me one extra point༼ つ ◕_◕ ༽つ.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow, problem D has been explained amazing

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problems were balanced.

→ Reply
»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem F can be solved using std::multiset. My solution is here

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In the tutorial for 1872C, Under point number 1 it is mentioned that we only need to calculate shortest composite number in the interval [r,l] but in the question we are asked to report two non coprime numbers that sum to a number(that turns out to be composite) in the interval [r,l] so once i have calculated the favourable composite number how to calculate the values of a and b ?

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this arithmetic progression formula useful here? Sn = n/2((2 * a)+ (n — 1) * d) I got wrong answer on testcase 4 here is my submission: https://codeforces.com/contest/1872/submission/222426491

→ Reply
»
8 months ago, # |
  Vote: I like it -6 Vote: I do not like it

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

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem D to get the purple indices . n=n/(x*y); can't we?

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't understand A. Why is it 2*c, why not c, 3c, 4c??

→ Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Example:

    if(a > b) swap(a,b);
ll koef = 50;
ll x = (koef / 2) * (b - a);
ll y = koef * c;
cout << (x + y - 1) / y;
    → Reply
»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Lovely F :))

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Really good problems, thanks authors

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1e9 is biggest needed but even the cases pass upto 4e5

    → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

There is another solution to problem F. I'm using the maximum spanning tree to find the maximum cost edges and after that, in that maximum spanning tree I use topological sorting to find which animal I can sell at first or which animal has minimal dependencies on other animals. Here is my code: 222724522

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone show how binary search can be used to find the solution for problem B? I'm quite new and haven't yet fully understood binary search and all its variants/applications. Many thanks in advance!

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Might not be the best one, but this is my solution to problem C. Basically I sieved and found all prime numbers up to 1e7, then for each prime p try to find another integer k so p * k is in the required range. The l == r case is added later as I keep getting TLE'd on test 4. It takes longer to code up and has a longer runtime, but is intuitive (at least to me) and gives me a refresher on prime sieving.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

whats wrong in my code for problem D ,in test case 3 it fails at one particular case . Can anyone tell whats the mistake ? https://codeforces.com/contest/1872/submission/223526983

→ Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why is sample test 3 for problem F correct?

Input
Output

With this output the money you get is 31, but if the output is:

Other output

The money is 32. What?

→ Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell why in G, 2.n or 2^60 would be sufficient?

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Explanation for problem G:

If we can brute force, we have to choose the indexes that are not 1 because taking from 1 doesn't make sense in multiplication. So we can choose all elements which are not 1 and check where the answer is maximum. The size of the array is 2*1e5 so by this we will have (2*1e5)^2 possibilities which is TLE.

If the value of a multiplication increases by a certain value, it is OK to do multiplication of all the number from left to right(excluding leading and trailing 1).

So what should the sum be to include all the numbers. Say we have a number 2 followed by 2*1e5 -2 1s and then some value x. If 2*x >= 2 + 2*1e5 -2 + x satisfies, we can always take the full segment. x comes out to be 2*1e5 and 2*x which is the multiplication comes out to be 4*1e5.

So if the multiplication increases by 4*1e5 at any point then take all the elements. If all elements are only 2(not count 1) which is smallest which can help in sum then we need around 18 elements.

So in the worst case we'll brute force over 18 elements or 18^2 segments to find answers for each segment and then take the maximum possible.

Implementation.

→ Reply
»
7 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Another approach for problem F.

Find all the cycles. Then for each cycle, find the start of that cycle. Then after finding the start of that cycle, reconstruct the tree of nodes that comes up to this node of the cycle.

Example:

Image url for example: https://pasteboard.co/Ms35TBDxcrow.png

Here I know that my cycle should that from 5 -> 6 -> 7. So before I take 5, I will reconstruct the entire node tree to 5. Which is 1 2 3 4 5 and similarly for each node in the cycle.

I used Kosaraju's Algorithm and transpose of the graph to calculate my answer which is an overkill.

Implementation

→ Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

why does my solution 227304800 of F work partially and in some case the answer is incorrect?

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why my code is giving wrong output?

Submission Link Problem G

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply