mesanu's blog

By mesanu, history, 9 months ago, In English

Thank you for participating!

1873A - Short Sort

Idea: flamestorm

Tutorial
Solution

1873B - Good Kid

Idea: mesanu

Tutorial
Solution

1873C - Target Practice

Idea: flamestorm

Tutorial
Solution

1873D - 1D Eraser

Idea: flamestorm

Tutorial
Solution

1873E - Building an Aquarium

Idea: flamestorm

Tutorial
Solution

1873F - Money Trees

Idea: mesanu

Tutorial
Solution

1873G - ABBC or BACB

Idea: flamestorm

Tutorial
Solution

1873H - Mad City

Idea: mesanu

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

»
9 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Problem H was awesome!

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

    its nice but pretty easy for an H

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

    When both Valeriu and Marcel would be in a cycle what would be needed to check the reaching time to the entry node? if Valeriu were in a cycle answer should be "NO". but here we are checking the reaching time to the entry node.

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

      if they were both in a cycle i think the answer would be yes since V would always have 2 options to choose from , its the node out of the cycle where he could be caught.

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      This Case is considered in the first test case itself. Previously I just read the question, so I thought they might have missed it.

»
9 months ago, # |
  Vote: I like it +64 Vote: I do not like it

You can avoid hard coding in problem C.

Value of cell $$$(i,j)$$$ is $$$\min(i,j,11-i,11-j)$$$.

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it -42 Vote: I do not like it

    dislike me >_<

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Another approach is to take min Chebyshev distance from (i, j) to the 4 middle squares.

    • »
      »
      »
      9 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Did you mean to invert the Chebyshev distance? I don't see how $$$min(x_2-x_1, y_2-y_1)$$$ would lead to the same pattern.

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

        5 — min( max(abs(x — 4), abs(y — 4)), max(abs(x — 4), abs(y — 5)), max(abs(x — 5), abs(y — 4)), max(abs(x — 5), abs(y — 5)), )

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

          Yes, that is to invert the Chebyshev distance. Also you don't actually need to take the smallest distance from all 4 middle points since the smallest distance it's the nearest corner of the center square.

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

            idk what you are talking about, there is no inverting, maybe look at the definition: https://en.wikipedia.org/wiki/Chebyshev_distance

            i just took chebyshev distance from all 4 middle points and took the distance to the closest one — if you know how to identify the closest corner without computing all 4 distances I would like to see that.

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

              Chebyshev distance is defined as

              $$$D_{Chebyshev} := max(|x_1-x_2|, |y_1-y_2|)$$$

              When I talk about inverting $$$D_{Chebyshev}$$$ over $$$k$$$ I mean to do $$$k - D_{Chebyshev}$$$. Since every distance in one end gets mapped to the other end. More formally $$$D_{Chebyshev}: \{0, 1, 2, ... , k-1, k\} \mapsto \{k, k-1, ... , 2, 1, 0\}$$$

              In our case $$$k=5$$$

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

                I see, it is inverted in that sense.

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

    Thank you for the formula. Could you please provide a more general formula that works for concentric matrices where the values decrease from the outermost layer to the inner layers? ("Do you think this formula consistently works for matrices where the values increase from the outermost layer to the inner layer min(i,j,n+1−i,n+1−j)) and thanks.

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

      yes

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

        I initially wanted to use the Chebyshev distance, but I became confused due to the uneven grid size. I then considered using the midpoint (4.5, 4.5), but that approach became quite messy. Do you have any suggestions ?thanks.

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

          take smallest distance from all 4 middle points

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

    I also did this.

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

    it can be also measured by using this formula if (mat[i][j] == 'X') total_sum += s[i * 11 + j] — '0';

    where predefined template string with values string s = "1111111111\n" "1222222221\n" "1233333321\n" "1234444321\n" "1234554321\n" "1234554321\n" "1234444321\n" "1233333321\n" "1222222221\n" "1111111111\n";

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

problem E and F gives me some real stress but overall the contest was fun!!

»
9 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Problem G's walk-through was so clear I could understand the concept in a split second!

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    totally agreed Want more this kind of tutorial in future #flamestrom

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For C, I asked chatGPT to provide me with a program to generate the matrix and then I used it. Happy to get skipped as the rating doesn't matter to me.

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    using chatGPT is legal tho

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

    That is smart, wish I'd have thought of that

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

      hello can you explain why direction of approach doesn't matter in B question like any proof if possible?

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

        What do you mean?

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

          B mei jaise greedy approach laga rhe hai na left to right jaate hue, so I'm asking right to left jaane pe same answer aayega and Better answer nahi aayega iski kya guarentee hai. I would love a proof of why Direction of approach does not matter.

          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            Are you talking about this contest’s B? My solution was just brute force where I tried everything. I reset the variable after each iteration.

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

              oh i'm really sorry i meant D (1d eraser)

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

                Well if you’re convinced that it works backward you can think of reversing the string and doing it backwards as the same thing as doing it forwards

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

                  no i am not convinced that it works forward

                  according to me the ans should be min(forward approach, back approach)

                  greedy gives me the idea to approach from one single direction but how can you say that both directions will give same answer

                  here your reversing logic doesn't apply as say i claim forward approach takes 3 operation and backward approach takes 2 operations then on reversing also answer will be same i agree(2) but this time it will be from forward approach

                  how can you claim that only by checking from one direction you will get a answer same as backward approach

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

                  Oh, I see.

                  Well, let's try to 'prove' that the forward approach always gives an optimal answer.

                  What my code is doing is it's going from 0 to n and checking if each character needs to be converted or not. If it does, start a window, otherwise move on to the next index. Notice that when we move on to the next index, we'll never come back to the previous one.

                  So why is this important? That means that when we see an element that needs to be converted, we have to start a window. You might say that there are multiple ways to start a window (for example if we want to convert i+1, we could start a window of size k>=2 at index i) so that an index is converted, but the most optimal way will always be when it's started at the index that needs to be converted, since that way more indices ahead can be affected.

                  If you're convinced that the forward approach is correct, you can see why the backward approach will also be correct from my above reply, thus showing that both approaches will give the same answer.

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

Can someone explain why in problem B, it's optimal to increase the smallest digit ?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    yes because if we notice that the ratio change of x+1/x (x is smallest digit) is large as compare to bigger digits so thats why it always gives ans..

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    if you add 1 to smaller number then you gain original product + (original — small). But if you add 1 to any other than smaller you gain -> Original product + (original — some other which is not smallest) . So first case will always be bigger

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Say you have (3,3,2,3):

    Let's pretend you need to find the largest possible product with all these elements except one.

    This is obviously (3*3*3), as 2 is smaller than 3, and (3*3*2)<(3*3*3). Now we know that the excluded value is 2.

    Now that we've got (3*3*3) as the largest product excluding the smallest value, we can add 1 to the excluded value, and now we've increased the product by (3*3*3).

    We went from (3*3*3)*2 to (3*3*3)*3.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Based on AM-GM Inequality, a set of numbers with specific sum will have largest product if all the numbers are equal. Increasing the smallest digit will make these digits be closers to their average. It is not a solid proof but rather an intuitive way to quickly realize it.

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

      hello can you explain why direction of approach doesn't matter in B question like any proof if possible?

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

    Small number repeats more in product than big number

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

    To avoid making product =0 ,since all numbers between 0 and 9 then if the number is 0 then it will be 1,of course if there is more than zero , the max product is 0 , otherwise we can proof by math that the (min(a)+1)×a(*) the rest of numbers is the maximum product

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    assume x=a*b*c*d

    then (a+1)*b*c*d-x = b*c*d

    basically, increasing a single number by one increases the answer by the product of all other numbers, so it's best if b,c,d are the largest possible, which means a is the smallest possible

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

    $$$(a+1)*bcde\ldots < (b+1)*acde\ldots$$$

    $$$\Leftrightarrow abcde\ldots + bcde\ldots < abcde\ldots + acde\ldots$$$

    $$$\Leftrightarrow b < a$$$

    If b is less than a, increasing b by one will result in a larger product.

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

    You can also think of it as multiples. Which is greater, the next multiple of the smallest digit (i.e. increasing the largest digit) or the next multiple of the largest digit (i.e. increasing the smallest digit)

    For example, let $$$a < b$$$.

    You can think of $$$a*b$$$ as a multiple of $$$a$$$ or as a multiple of $$$b$$$. It can be shown that the next multiple of $$$b$$$ (i.e. $$$(a+1)*b$$$) is always larger than the next multiple of $$$a$$$ (i.e. $$$(b+1)*a$$$) since $$$a*b + b > a*b + a$$$

»
9 months ago, # |
Rev. 5   Vote: I like it +11 Vote: I do not like it

$$$E$$$ can be solved in $$$O(n \log(n))$$$ and $$$F$$$ can be solved in $$$O(n)$$$.

For $$$E$$$, first sort the array $$$a$$$. The optimal value of $$$h$$$ is $$$\max_i(v_i)$$$ where $$$v_i=\min(a_{i+1}-1, \left \lfloor (x+PrefixSum([a_1:a_i]))/i \rfloor \right)$$$ if $$$v_i \geq a_i$$$ and $$$v_i=0$$$ otherwise (set $$$a_{n+1}$$$ as $$$\infty$$$ or handle the case $$$i=n$$$ separately).

$$$F$$$ can be done by sliding windows method.

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    don't you use sort in E?, which is already O(n log(n))

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    You can use binary search for finding solution. l = 0, r = 1e9

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

      but r = 1e9 get wrong answer. must use r = 2^31 -1 or r = 2e9 + 7. i used 1e14, 1e15 and 1e18 then i got wrong answer. it was so boring :>

      • »
        »
        »
        »
        9 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        we can also use r = max of all the array elements + 1e9.

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

        Why ?

        Its work fine for me , No need for this values .

        My submission 224465049

        And I think Binary Search is more simple than the formula and easier to work with for beginners.

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          I don't know. maybe the problem was from another thing. however this is my code who got wrong answer : 224488235

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

            Mid is Overflow

            1e18 / 2 = 5e17 which cann't stored in an int

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

              oh really? you are kidding! I knew that. i used define for contest who i don't forget using long long

              #define int long long

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

    F Can be done in O(N)

    using two pointer one on the current node and other at the first element of contigous part (which satisfy the condition).

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

Can someone explain why this code doesn't work for Problem E. I understood immediately that Binary Search would be used but my code fails on TestCase-7. TIA

https://codeforces.com/contest/1873/submission/224447874

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

    accepted solution by modifying your code. Your upper limit will overflow long long. worst case is 1 tile with 1e9 height and water also 1e9 , upper bound is 2*1e9 + 1 , use a bit more for edge cases.

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

    Try updating the method possible such that, you exit the loop (or return false) just after sum exceeds x, so that it doesn't overflow.

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

      calculating mid can overflow too

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

        Calculating mid can overflow if we use ll mid=(lo+hi)/2;.

        But, if we use ll mid=lo+(hi-lo)/2;, it shouldn't overflow.

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

      yes i agree, but why ???

      as the constraints are 10 power 9, in the worst case i am adding n 10power9's, so in my case w = 1e9 * 1e5 which is 1e14. this should not get overflowed right.

      https://codeforces.com/contest/1873/submission/224396755

      • »
        »
        »
        »
        9 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        You have set the upper bound as 1e+17.

        So, the value mid can have a large number (say 5e+16). (Here, it doesn't have to be less than 10 power 9, I believe.)

        Inside the function func, when computing h-a[i], if a[i] is small, then, h-a[i] can be large.

        Because of this, w += max(h-a[i],0LL); will keep increasing, and it might overflow eventually. I think when n is somewhere around 10 power 3 or more, it will overflow.

        (I haven't used c++ for a while) Just curious. How does an int datatype in c++ store such a large number ?

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

          i am defining my int as long long which can store numbers till 1e18. so i wont think any overflow will occur

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

    i got the same problem.i even doubt that this problem cant be solved by binary search

»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

For problem F: Given, (l≤i<r). I don't understand why l and r can be same.

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Author's right answer is 1 in this test: 2 15 9 6 1 3 .

    However, for 1<=i<r we can't find h[i] is divisible h[i + 1]. So I think this answer is 0.

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

    I didn't check the case where l1 and r1, because of this I had wa2:(

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

    most right one will always be picked if its apples value is less than or equal to k, so in this case minimum answer can be 1.

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

For E first i solved in Python and got AC but time was around 1400s.So for the fear of hacking i converted that code to C++ and submitted it but still the first AC time is being taken in account.so is the first ac soln final in div 4?

»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Video Editorial For Problem A to H

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    please make vedio editorials for atcoder regular contest.There are no english vedio editorial for that.

»
9 months ago, # |
  Vote: I like it +2 Vote: I do not like it

In f, we can use two pointers instead of binary search, so it can be reduced to O(2*n)

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

Great Editorial. Especially liked Problem G's illustration.

»
9 months ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

two liner solution for B.

(*min_element(v.begin(), v.end()))++; 
cout << accumulate(v.begin(), v.end(), 1LL, [&](int res, int x) { return (res * x);}) << '\n';
»
9 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Could someone help me, why this code is getting wrong answer in problem H https://codeforces.com/contest/1873/submission/224501501

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

    It fails for the below input

    	1
    	10 1 4
    	1 2
    	2 3
    	3 4
    	4 5
    	5 6
    	5 7
    	6 8
    	5 9
    	5 10
    	1 8
    	
    good:
    	YES
    	
    bad:
    	NO
    	
    
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem F,

Can someone explain if I take l = 2 and r = 2 as well, then how is 2<=2<2 ?

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

    pick l=2 and r=2 , you will find that no such i satistied l<=i< r . That means you don't need to check any h[i]. So you can collect fruit from a[l] to a[r] (that's a[2] actually) . The same thing works when you want to collect fruit from only one tree.

»
9 months ago, # |
  Vote: I like it +4 Vote: I do not like it

I found an exactly same problem as problem H (Mad City)

https://github.com/all1m-algorithm-study/uospc2021/blob/main/problems/Police_Thief/statements.md

This is from an intra-college contest held by University of Seoul in 2021.

There is no English statement, but if you use a translator you'll notice there are few differences.

Even the examples given in the descriptions are the same.

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

Thanks for a good contest, although i joined late the experience was enjoable

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

For E , i used the value of high as x + sum of array.

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

Problem E can be solved in $$$\mathcal{O}(n\log n + \log n\log (a_i+x))$$$.

First, we notice that the permutation of $$$a[i]$$$ does not matter at all.

So we can sort(a,a+n) first, and then when we want to calculate how much water we use when the height is $$$h$$$, we can use idx=lower_bound(a,a+n,h)-a, and then the water we use nowuse=idx*mid-s[idx-1].

$$$s[i]$$$ is the prefix of sorted $$$a[i]$$$, i from 0 to n-1. We can use this because for $$$idx\le i\le n-1$$$, we have $$$a[i]>h$$$, so the use of $$$i$$$ is $$$0$$$.

By using this way, we can avoid calculating max(0,...) with n times.

Since sort takes $$$\mathcal{O}(n\log n)$$$ and in every check in binary search we use lower_bound which is $$$\mathcal{O}(\log n)$$$, we have $$$\mathcal{O}(n\log n + \log n\log (a_i+x))$$$ in all.

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

In problem c:

auto position = [](int i, int j)->int 
{
    int output;
    if((i+j)<=9){
        output = min(i, j);
    }else{
        output = (9-max(i, j));
    }
    output++;
    return output;
};
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I use this equation : point = min(min(i,9-i),min(j,9-j)) + 1 it's the minimum distance to the edge + 1.

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

It was my best CF contest ever through my CP journey. I overcame my limit at last..

»
9 months ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

for problem G, as mentioned in the tutorial, we can see the problem as each B choose one direction(left or right) to eat the A's, so we can use dp.

dp[i][0] means if the i-th B choose to go left, the maximum A's that the 1-th, 2-th, ..., i-th B can eat. dp[i][1] is similar, it means the i-th B choose to go right.

therefore, we can get the transition equation: dp[i][0] = dp[i-1][0] + i-th B's position — (i-1)-th B's position — 1 (because if the (i-1)-th B go right and the i-th B wants to left, it will have conflict, so (i-1)-th B can only choose to go left) dp[i][1] = max(dp[i-1][0], dp[i-1][1]) + (i+1)-th B's position — i-th B's position (if i-th B wants to go right, we don't need to care about the (i-1)-th B's choice)

and here is the implementation https://codeforces.com/contest/1873/submission/224561489

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

One of those balanced contest that we wished for thank you

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

Can someone explain solution for problem G? Tutorial is unavailable((

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

can someone please explain why my code does't work for problem E, thanks!

https://codeforces.com/contest/1873/submission/224479403

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

    upper bound is too small, maybe you can use 1e12(long long).

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

please can someone suggests similar problems to F in which you do binary search on the answer plus some other computations?

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

    In problem F i have first searched for a segment of divisible no.s and then i have applied sliding window technique . The time complexicity was 2.n which is actually O(n). Try this approach.

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

Can anyone point out error in my code for Problem F. I am trying to do the O(n) approach. My code will return max_count as the answer.

sum=0, count=0, max_count=0;
for(int i=0;i<n-1;i++)
{
    if(h[i]%h[i+1]==0)
    {
        if((sum+a[i])<=k)
        {
            sum+=a[i];
            count++;
        }
        else
        {
            while(sum+a[i]>k)
            {
                sum-=a[i-count];
                count--;
            }
            sum+=a[i];
            count++;
        }
    }
    else
    {
        sum=0;
        count=0;
    }
    max_count=(max_count<count?count:max_count);
}
»
9 months ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

Problem C can be easily done by taking the nearest x distance and y distance (these are independent) from the 5-score zone [(4,4), (5,4), (4,5), (5,5)] (_0 based-index_). The answer is min(5-x, 5-y) per 'X' instead of hard-coding it:

#include <bits/stdc++.h>
#define ll long long
#define push push_back
#define fi first
#define se second
#define TC int t; cin >> t; for(int u=1; u<=t; u++)
using namespace std;


int main(){
   TC{
      int ans = 0;
      for(int i=0; i<10; i++){
         for(int j=0; j<10; j++){
            char c; cin >> c;
            if(c=='X'){
               /*
               (4, 4)
               (5, 4)
               (4, 5)
               (5, 5)
               */
               pair<int, int> point = make_pair(min(abs(4-i), abs(5-i)), min(abs(4-j), abs(5-j)));
               ans+=(min(abs(5-point.fi), abs(5-point.se)));
            }
         }
      }cout << ans << "\n";
   }
}

Submission: 224566541

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

Tutorial for G was so helpful!!!

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

Video Editorial (A-H) LINK TO YOUTUBE EDITORIAL

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

Not getting how to solve F problem, can anyone explain the intuition?

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

I request Div4's authors to make future rounds a little more challenging. This was on the easier side.

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

    Btw, I liked all problem statements as they were crystal clear! I hope to see such clear statements in all future rounds as well.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    That's why it's DIV4. To get more challenge you can always participate in other divisions.

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

great editorial for problem 1873G - ABBC or BACB thank you :)

»
9 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Can anyone tell me why my code is failing?

#define REP(i,a,b) for(ll i=a;i<b;++i)

void Cyan() {
    // Think Twice Code Once
    int n, k;
    cin >> n >> k;
    vi a(n), h(n);
    REP(i, 0, n) cin >> a[i];
    REP(i, 0, n) cin >> h[i];
    int j = 0, sum = a[0], prv = h[0], ans = 0;
    REP(i, 0, n) {
        sum += a[i];
        if (prv % h[i]) {
            j = i;
            sum = a[i];
            prv = h[i];
        }
        while (sum > k) {
            sum -= a[j++];
        }
        ans = max(ans, i - j + 1);
        prv = h[i];
    }
    cout << ans << endl;
}
»
9 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

For the last problem, I didn't notice the number of edges is n, I skipped the first line immediately assuming it just says there are n nodes. Then I thought maybe around 20 mins on this and was amazed how people can solve it while I was trying to prove it is a hard problem. It was like finding a bunch of induced cycles, which isn't an easy problem in general graphs. I can't blame that it wasn't explicit enough, since if I was reading the input format or the first line, it was clear there are n edges.

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

    I've also read the problem like this.

    In such version, we can solve it at least as follows (or maybe easier):

    • for each vertex, determine whether it lies on any cycle
    • for each vertex, find distance from Valeriu
    • for each vertex, find distance from Marcel
    • Valeriu wins if there is a vertex on a cycle that is closer to Valeriu than to Marcel
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think you are right. I thought too deep about it: I thought the winning strategy is to walk along an induced cycle, otherwise, marcel can at some point go along a chord of a cycle and catch Valeriu. Finding a winning strategy is difficult I believe, the question didn't ask for the winning strategy, though. I think the reason I've thought too much about it is that, I overlooked that every vertex that lies on a cycle, also lies on an induced cycle, so I didn't need to check if a vertex is on induced cycle, if it is on a cycle, certainly there is an induced cycle the vertex is on it. So, yes it was easier to decide if he wins but not easy to find a winning strategy.

      Also one last and less important point: the approach you mentioned in general graphs could be quadratic to #vertices, so if the number of the vertices is big (like in this case), it could fail if it has too many edges (well this case didn't have that).

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

        The first item (for each vertex, determine whether it lies on any cycle) can be performed with a single depth-first search, similar to finding articulation points or biconnected components.

        Finding distances is two breadth-first searches, one from Marcel and the other from Valeriu.

        So the solution is O(E) in total.

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

          That’s correct, and O(|E|) in dense graphs could lead to O(|V|^2) and if |V| is big, like 1e5, then it will be TL. But, of course for this particular question it doesn’t happen.

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

            When the graph is given explicitly, which is true in the majority of the problems, $$$O(|E|)$$$ is quite distinct from $$$O(|V|^2)$$$.

            If we can read it, which takes $$$O(|E|)$$$ already, we can certainly work with it in $$$O(|E|)$$$ as well.

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

              Fair point and applies for most of the cases. But notice that we can read a quadratic sized graph in sub quadratic or even linear time, if it is given by the edges which don’t belong to the graph. Basically by its complement definition. Can we still run it linear to size of V? Or modify it to be linear to V?

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Here's my simple O(n) approach using sliding window on F — Money Trees @mesanu :

224470856

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

How to understand "Because we have a tree with an additional edge, our graph has exactly one cycle."? I think we are only gived a simple graph and there may be more cycle.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    It follows from the statement "The roads are given that it is possible to get from any building to any other building going along the roads.". This means the graph is a connected graph. A connected graph with n nodes and n-1 edges can be proven to be a tree. There is edge left over after making the tree and adding it must create a single cycle (as every node is already connected).

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

In hindsight my bridge-finding algorithm seems like an overkill :) 224589798

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

    Could you explain the idea?

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

      If you don't understand anything just read the offical solution :))) It's much faster, simpler and more elegant.

      With the given conditions, every bridge in the graph does not belong to the cycle, and thus every non-bridge belongs to the cycle. After we traverse on the graph we will find the full set of vertices that belong to the cycle. Start traversing from Valeriu's positon until you reach one that is in the cycle (possibly Valeriu's original position itself) and calculate the distance between the vertices. As the tutorial above indicates, this is Valeriu's entry to the cycle. We then calculate the distance between that entry vertice and Marcel's. The answer is No if the former distance is not smaller that the latter, or both Valeriu and Marcel share the same starting position.

      For an implementation of the bridge-finding algorithm, see https://cp-algorithms.com/graph/bridge-searching.html#implementation.

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

        What i have done is very similar to yours, I used a bfs to find nodes in a cycle and then used another bfs to find the shortest distance both of them need to get in the cycle

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

H was beauty I was played in B ;-;, although i observed quickly that answer is always incrementing the smallest element but i wasnt able to prove it at the moment. What is the proof tho?

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

Can somebody explain Problem F using BS Please.

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

Can some please explain why I got wrong answer when the value assigned to 'hi' was 1e14 or 1e18?

https://codeforces.com/contest/1873/submission/224393419

This resulted in wrong answer in test case 4 but was accepted when I updated the value of 'hi' to 1e10.

Thanks.

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

    Because when 1e14 or 1e18 is multiplied by 2*10^5 (maximum size of array) an overflow will occur (long long maximum value is approximately 9*1e18)

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

A is a pulchritudinous problem. I solved it with Bogosort!

»
9 months ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

Why in problem H, in test 2, in test case 3, the answer is NO? Test case: 1 18 7 15 14 6 14 8 6 18 4 13 3 12 11 9 14 2 14 17 14 11 11 5 1 7 16 11 15 11 14 18 1 13 10 8 13 14 12 6 UPD: Sorry I missed one test case, the answer for test case above was YES

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

Yesterday i submit solution of F problem. It gave me AC. I had 6 solved problems and 340 penalty. Now i view i solved 5 problems with 142 penalty. But today when I got the rating I saw that my solution to problem F gave TLE. Is it fair?

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

    System testing, nothing much you can do about it

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

thanks for editorial,thanks for doing div 4.

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I applied sliding window in F but getting wrong answer. Can anyone help

while(t--){
    ll n, k;
    cin>>n>>k;

    vector<ll> v(n), h(n);

    for(int i=0; i<n; i++) cin>>v[i];
    for(int i=0; i<n; i++) cin>>h[i]; 


    ll l=0, r=1;
    ll cnt=0, tot=v[0];
    ll ans=0;

    if(n==1){
        if(v[0]<=k) cout<<1<<endl;
        else cout<<0<<endl;
    }

    else{
    while(r<n){
        if(h[r-1]%h[r]==0){
            tot+=v[r];    
            if(tot<=k) ans=max(ans, r-l+1);
        } 
        else{
            while(l!=r){
                tot-=v[l];
                l++;
            }
            tot=v[l];
        }

        while(tot>k){
            tot-=v[l];
            l++;
        }
        ans=max(ans, r-l+1);
        r++; 
    }

    cout<<ans<<endl;
    }
}
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

224598998 224600540 May I ask why the first submission cannot solve the problem while the second one can? The only difference between them is:

while (l < r) {
        int mid = (l + r + 1) >> 1, flag = 0;
        for (int i = x; i + mid - 1 <= y; i++)
            if ((LL)s[i + mid - 1] - s[i - 1] <= k) {
                flag = 1;
                break;
            }
        if (flag) l = mid;
        else r = mid - 1;
    }
while (l <= r) {
        int mid = (l + r) >> 1, flag = 0;
        for (int i = x; i + mid - 1 <= y; i++)
            if ((LL)s[i + mid - 1] - s[i - 1] <= k) {
                flag = 1;
                break;
            }
        if (flag) l = mid + 1;
        else r = mid - 1;
    }
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can also watch the video editorials I made on the problems E , F, G and H

Enjoy watching and let me know what you think about them!

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

for problem A, you can check if any of the letter is in the right position then you can return "Yes" else "No".

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

Finally I became Pupil after a one year of trying. Since i acheived my goal. I am done with these stupid contests. since anyway I feel there is no much difference anyway

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

why are they not rating the questions in the recent contests?

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

H problem Clearing the array vis[N] is the most important !

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

Could someone can take a look at my F: 224638271, thx. I look for all the continuous intervals that meet the conditions, then use binary search on the length of intervals, but got wa2.

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

1873F — Money Trees Sliding window approach

if current tree high is not divisible then we re-init it, also update ans, else try to reduce the window to match the condition.

void f() {
    int t, n, k; cin >> t;
    while(t--) {
        cin >> n >> k;
        vector<int> fruits(n), treeHigh(n);
        for(int &x: fruits) cin >> x;
        for(int &x: treeHigh) cin >> x;
        int totalFruits = fruits[0];
        int left = 0, ans = fruits[0] <= k;
        for(int i = 1; i < n; i++) {

            if(treeHigh[i-1] % treeHigh[i] != 0) {
                totalFruits = fruits[i];
                left = i;
                ans = max(ans, (totalFruits <= k) ? 1: 0);
            }else {
                totalFruits += fruits[i];
                while(totalFruits > k) {
                    totalFruits -= fruits[left++];
                }
                ans = max(ans, i - left + 1);
            }
        }
        cout << ans << "\n";
    }
}
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution for G.

The logic was intuitive. Going left to right, it doesn't make sense to use operation 1 the operation 2 and then operation 1 again(try simulating it through the test cases given). Our best possible score is achieved through a series of operation 1s followed by a series of operation 2s.

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

how is the time complexity in the 1873C — Target Practice is O(1) when you have 2 nested for loops iterating the input?

»
9 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Problem H Idea is simple but implementation bit complex.

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

can anyone tell me where my code fails

https://codeforces.com/contest/1873/submission/224537788

Here I simply find the nodes which are part of cycle and run a disktra to find whether b can reach any part of cycle before a if true then return 1 else return 0.

Solved Actually my code for finding cycles nodes is not correct.

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

Problem F can also be solved using Binary Search ... My code

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

Can someone explain the second last sample test case for problem H?

8 5 3

8 3 5 1 2 6 6 8 1 2 4 8 5 7 6 7

I think Valeriu can always escape Marcel by choosing node 3 or 4, whichever one Marcel doesn't choose.

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

G is the hardest problem I think, but solving it was gratifying

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

for H,what if there are 2 entrances of the circle?

»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I absolutely loved the editorial for problem G! Wow! It was so fun to read, and so easy to understand! It would be amazing if all editorials were like this: being longer is not necessarily bad if a longer editorial is better at explaining the solution than a shorter one.

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

What exactly I am doing wrong here in Problem E. I solved this on a pen and paper, and seems to me that the calculations are correct. I am first sorting the heights and then start filling up from the leftmost side of the tank. My submission My solution

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    At the end, you're adding x/n.. instead, you need to add x/(i+1) where i is the index of the largest coral that gets submerged. Also, you need to use a larger data type.. I modified your code.

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

      Thanks a lot brother. Gotta love the Codeforces community for helping learners grow.

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

Awesome round. Enjoyed how the editorial was written.

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

F can be done in O(n) using Sliding Window. Much more intuitive too imo.

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

https://codeforces.com/contest/1873/submission/224490319

why is my F failing i just updated len and the sum in one execution rather than using a binary search approach??

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

I tried solving "ABBC or BACB" problem with this code but I can't find the reason why my code is not working for 2 test cases ???(given below is my code) signed main() {
ios::sync_with_stdio(false); cin.tie(NULL); int size; cin>>size; while(size--) { string s; cin>>s; int n = s.length(); bool check=false; if(s[0]=='B' || s[n-1]=='B') check=true;

int acount = 0;
       int mn = n;
       for(int i=0;i<n;i++)
       {
           int end = i;
           if(s[i]=='A')
           {
               acount++;
               while(end<n && s[end]!='B')
               {
                    end++;
               }
           }
           int temp = end-i;
           mn = min(mn,temp);

           if(s[i]=='B')
           {
               if(i+1<n && s[i+1]=='B')
                check=true;
           }
       }

       int fck = 0;
       if(check)
        cout<<acount<<endl;
       else
       {
          cout<<max(acount-mn,fck)<<endl;
       }
    }
    return 0;

}

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

why the answer of test case "ABAAB" in problem G is 2

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

Awesome contest with awesome editorial !! Really had a great time solving this amazing problems

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

G can also be done using dp. for every 'B' we store the count of A's on its left and right and then we try every possible way of using those A's.. 225181389

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

Can't we do problem F in O(n)?

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

simplest solution of G ~~~~~

string s; cin >> s;
int mn = 1e9, cnt = 0, a = 0;

for(int i = 0; i < s.size(); i++) {
    if(s[i] == 'A') cnt++, a++;
    else {
       mn = min(mn, cnt); cnt = 0;
    }
}
mn = min(mn, cnt);
cout << a - mn;

~~~~~

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

I have implemented Problem H a little bit differently than the editorial if you are interested then check out my code.

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

for F this solution is somewhat dp if you prefer. My submission: 225711679 The idea is to first find each maximal segment. then check maximum size we can get starting from any i in that seg. in order to pass TL remember sum and where it ended for previous starting point and start from there and not from i.

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

Can someone help me understand why my solution for F gives WA judgement: https://codeforces.com/contest/1873/submission/225741996

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

For money trees problem my solution is giving TLE only if I use sort else without sort it gets accepted can anyone explain why sort here is giving TLE FOR INFO: if i remove sort and optimization part the solution gets accepted include <bits/stdc++.h> using namespace std; int mm=0; define ll long long void solving(void); int main() {

ll t;
cin >> t;
while (t--)
{
    solving();
}

} void solving(void) {

ll n, k;
cin >> n >> k;
ll a[n], h[n];
ll l = -1, e = -1;

vector<pair<ll, pair<ll, ll>>> v; // this will store <length of subarray satisfying the divisibility rule<e means starting,l means ending of subarray >> elements

for (ll i = 0; i < n; i++)
{
    cin >> a[i];
}

for (ll i = 0; i < n; i++)
{
    cin >> h[i];
}

for (ll i = n - 1; i >= 0; i--)     //this for loop makes vector v declared above
{
    //  cout<<e<<l<<endl;
    if (e == -1 && l == -1)
    {
        e = i; // first true
        l = e;
        continue;
    }
    if (h[i] % h[i + 1] == 0)        
    {

        e = i;
    }
    else
    {
        v.push_back({(l - e + 1), {e, l}});
        e = i;
        l = e;
    }
}

v.push_back({(l - e + 1), {e, l}}); // e means starting and l means ending

ll sum = 0;
ll lenght = 0;




sort(v.begin(), v.end(), [](auto &a, auto &b)
  { if(a.first >= b.first) return true; else return false; });   // sorting according to subarray length


ll maxi = 0;
ll ans = 0, mid = 0;
mm=0;
for (auto &i : v)    //for each subarray
{

if (maxi >= abs((i.second.second — i.second.first) + 1)) // optimization only if vector is sorted in decreasing order of subarray length break;

ll start = i.second.first;   
    ll end = i.second.second;    
    ans = 0;
    ll sum=0;
    int t=start;

    for (int h = start; h <=end ; h++)   // h means head and t tail of sliding window
    {  

       sum+=a[h];

       while(sum>k){

        sum-=a[t];
        t++;


       }


       ans=h-t+1;

      maxi=max(maxi,ans);
    }


    maxi = max(maxi, ans);
}

    cout << maxi<<endl;

}

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

Hey, Can anyone help me with this runtime error? I have tried debugging and wasted a lot of time. Any help is appreciated.

https://codeforces.com/contest/1873/submission/226134316

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    In function dfs() last else block you are popping from the set without checking if it is possible to pop from the set Here is your AC code

    You can always you assert to figure out the mistake in your code.

    EDIT -> The word set in the first para is actually the stack you are using. I called it set as I was thinking about memory and pointers. In the last statement, "use assert"

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

226968842

Can someone help me debug this code for problem F . I can't seem to find on which test case it fails.

Thanks in Advance :)

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

227178473 my dp with memoisation solution,store every preceding and proceeding B's and then use dp to choose the best possible combinations(note that:once u eat all the A's from right,u cant eat any left A's for all the B's proceeding that B).

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

In Problem E

why the concept mid=(low+high)/2; is not working?

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

problem/F

i have being trying to understand the editorial of this question. I can't understand how at the end when we cout<<r<<endl; how is r the maximun subarray. like the logic behind how this is happening. Can anyone explain y this is happening?

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

Could someone tell me for problem e why do we have to consider high = 2e + 7?

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

Problem F can also be solved in O(n) using sliding window approach. It is the modified version of the problem of Longest subarray having sum of elements atmost K. My submission — https://codeforces.com/contest/1873/submission/233766852

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

Can anyone please tell me the error in this code 237621263 for the 1873F - Money Trees.

I am first finding whether $$$h[i]$$$ is divisible by $$$h[i+1]$$$ for all $$$0 \leq i < n$$$. Then, for all the contiguous subsequences $$$[h_l,h_{l+1},…,h_r]$$$ and storing $$$l,r$$$, and the $$$sum$$$ in a map as a single entry for a sequence.

Now, for a sequence using two pointers $$$start$$$ and $$$end$$$, I am traversing the subsequence; if $$$a[start] > a[end]$$$, then increase the $$$start$$$ pointer and decrease the $$$sum$$$ by $$$a[start]$$$ otherwise decrease the $$$end$$$ pointer and decrease the $$$sum$$$ by $$$a[end]$$$ until the $$$sum \leq k$$$ condition is satisfied.

The above process is done for all the sequences, and the maximum length will be the answer.

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

In Problem F. Money Trees can anyone tell me why my this code is not passing test case 46 of test case 2 . https://codeforces.com/contest/1873/submission/238364394

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What does the phrase "Notice the order of operations doesn't matter." precisely means for the problem D

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

The tutorial of problem G is beautiful, it was very informative for me to learn how to approach a problem :)

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

243211598 i dont understand why counting sum is giving overflow on problem E.

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

Overall Good contest, No offense but I don't think problem G was kind of an Ad hoc problem. I solved it using DP. Later came to see your approach and the explanation is amazing.

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

Problem C can be solved using a triple for loop: since every "square" has a delta with the outer one of 1, that is constant, we can iterate trough the whole sub-square adding 1 to the final answer each time we find a 'X'. In this way, we will find an 'X' as many time as it worths.

int ans = 0;
for (int x=0; x<5; ++x)
    for (int i = x; i < 10-x; ++i)
        for (int j = x; j < 10-x; ++j)
            if (grid[i][j] == 'X') ++ans;

My sumbission as reference: 247543890

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

ik I'm late but in E, instead of computing value of 'tot' for every height(mid), why not just check if the height is greater than the height of longest coral, if it is, then instead of looping through all coral heights to calculate 'tot' we can calculate it by subtracting total volume of coral from total volume of aquarium. Total volume can be precomputed while taking input of coral heights.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

1873C — Target Practice (alternative way to it may be a bit convenient if we don't want to write that number matrix)

// By: TESFAMICHAEL TAFERE

include <bits/stdc++.h>

using namespace std;

int main() { ios::sync_with_stdio(false); cin.tie(nullptr);

int t; cin >> t; while (t--) { char s[10][10];

int count = 0;
for (int i = 0; i < 10; i++)
{
     for (int j = 0; j < 10; j++)
    {
        cin >> s[i][j];
      if (s[i][j] == 'X')
      { 
        if (i == 0 || 10 - 1 == i || j == 0 || 10 - 1 == j)
             count++;
        else if (i == 1 || 10 - 2 == i || j == 1 || 10 - 2 == j)
             count+=2;
         else if ((i == 2 || 10 - 3 == i) || j == 2 || 10 - 3 == j)
             count+=3;
         else if (i == 3 || 10 - 4 == i || j == 3 || 10 - 4 == j)
             count+=4;
         else 
             count+=5;
      } 
   }
}
cout << count << "\n";

}

return 0;

}

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem G becomes way easy you just have to find smallest consecutive A substring . The ans = Number of A(s) — Length of smallest consecutive A(s) substring . Submission = https://codeforces.com/contest/1873/submission/264596469

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem G was very good for the beginners and thanks for the lovely Editorial .

But the given implementation part (code) is bit complex and not easy to understand. I think I have written a code which is very easy to understand code out of all the solutions I've watched till now

Here's my submission link for those who are struggling in the implementation part : https://codeforces.com/contest/1873/submission/265911111

Approach is simple :

  1. If the string start with 'B' or ends with 'B' or if it has any two consecutive 'B' in it , then the answer is simply the sum of all A's in the string.

  2. Otherwise we have to eat the A's where it occurs more in a chunk , hence the chunk with minimum no. of A's would be ignore , so in this case we can simply print, Sum of all A's — (minimum number of A's in any chunk/group);