FelixArg's blog

By FelixArg, history, 4 months ago, translation, In English

Thank you for participating! I hope you enjoyed the tasks.

One of the testers (redpanda) did a wonderful video analysis tasks A-C, I highly recommend watching it.

1982A - Soccer

Tutorial
Solution (74TrAkToR)

1982B - Collatz Conjecture

Tutorial
Solution (FelixArg)

1982C - Boring Day

Hint 1
Hint 2
Tutorial
Solution 1 (FelixArg)
Solution 2 (74TrAkToR)

1982D - Beauty of the mountains

Hint 1
Hint 2
Tutorial
Solution (FelixArg)

1982E - Number of k-good subarrays

Hint
Tutorial
Solution (FelixArg)

1982F - Sorting Problem Again

Hint
Tutorial
Solution (FelixArg)
  • Vote: I like it
  • +113
  • Vote: I do not like it

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

First. good problems I think.

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

    I'm sorry that the good problems failed to appear in the contest, hope that we can see the problems later:)

»
4 months ago, # |
Rev. 3   Vote: I like it -14 Vote: I do not like it

...

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

C. Most of the people have done this using dp. I didn't get the dp logic, but I tried it another way. For each position i, check the nearest position(let's say idx) on the right side which gives sum>=l (this can be done with lower bound and prefix sum, and also check if sum<=r). So you will have several i,idx intervals. Put them in a vector. Now all you need to do is find maximum non overlapping intervals, which is a standard leetcode problem.

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

    that's cool! simple sliding window would suffice too

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

      I can't figure out why my solution wrong? Please help me. My submission link. 267434800

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

        Please try this dataset: 5 6 8 5 5 1 2 5 The correct answer is 2 by 5+1 and 2+5, but your program outputs 1?

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

          Note that it does not input the number of test cases T.

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

            Can you please figure out which test case my code isn't passing .Here is the submission id. 267473714

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

              I don't quite understand Java programming, but your error seems similar to the original poster's error, both involving incorrect starting positions in a sliding window. For example, in this dataset (without T): 3 6 8 3 1 5, your output is 0, but actually 1 + 5 would achieve 1.

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

                thanks i got it

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

                can you tell me what is wong in my approach it seems correct to me https://codeforces.net/contest/1982/submission/267490137

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

                  This still seems to be an issue with handling the starting point, such as this group still lacking data for T: 5 6 8 4 1 4 1 9 The correct answer is 1, obtained by 1+4+1. However, in your program, when it first detects a sum greater than r, it encounters 4+1+4 during the process of moving the left pointer rightward, but since there is no value satisfying the condition within the [l, r] range, the left pointer moves to position 3, which is where the value 4 is located, instead of 1. This results in an incorrect answer of 0. In such problems, the left pointer typically moves to points that do not satisfy the current condition. Specifically, in this question, it should move to points that do not satisfy the condition of the interval sum > r, correct?

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

                  I understood what's the issue , and fixed the code , it's AC , but one thing i wanted to ask , that how do should i proove my greedy approach and check it is correct for every case , while doing greedy this is the mistake i do everytime i either do not take a case into consideration or i overthink cases and gets confused , btw thank you for your help

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

                  It is possible to write a brute-force program to generate some data and compare the results with a non-brute-force program. This might take some time, but it can be quite useful in certain situations.

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

            can you help me understand why my approach isn't working? I used a queue and accordingly performed operations. for the three cases- sum>r, sum<=r&&sum>=l , sum<l let me know if theres a tc where it fails. https://codeforces.net/contest/1982/submission/271534137

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

              The issue lies in the initial node judgment. For example, when n=3, l=4, r=5, and the array is 2 1 3, should your output be 0? The answer is 1, because the last element 3 is not within the range [l, r], so you did not update temp_sum.

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

        okay the problem is that when the sum > r you are sliding the left side which is fine but you are not taking care — if after all the sliding the sum ends up lower than "l" and now your "sum =0" at the begining will discard the sum which could have been used

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

    cool name.

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

Well done! Very fun contest and good problem set.

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

Thanks, it was a fun contest and nice problems + fast editorial

»
4 months ago, # |
Rev. 3   Vote: I like it -8 Vote: I do not like it

Can someone please tell me what is the flaw in the logic of my solution for C (like a corner test case on which it fails). It shows WA on 475th case.

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define  forn(i,n)      for(int i=0;i<n;i++)
#define  all(v)           v.begin(), v.end()
#define   rall(v)         v.rbegin(),v.rend()

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);        
    cout.tie(0);
    ll t,n,sum=0,ans=0,l=0,r=0;
    cin>>t;
    while(t--)
    {
        cin>>n>>l>>r;
        vector<ll> vec(n);
        forn(i,n)
        cin>>vec[i];
        sum=0;ans=0;
        forn(i,n)
        {
            sum+=vec[i];
            if(sum>=l and sum<=r)
            {
                ans++;
                sum=0;
            }
            else if(vec[i]>=l and vec[i]<=r)
            {
                ans++;
                sum=0;
            }
            else if(sum>r)
            {
                if(vec[i]<r)
                sum=vec[i];
                else
                    sum=0;
            }
            else;
            
        }
        cout<<ans<<'\n';
        
    }
}

Thanks for the help !

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

    Example : 1 3 5 6 1 2 4 Using your code, the output will be 0, but the output must be 1 because your code will compare vec[i]=4. Asn will not increase, but you must use two pointers so that you subtract vec[le]=1, so the sum will become 6 and increase by ans.

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

      Ohhh got it now. Thanks a lot bro.

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

      Your example is not valid, you are taking 1 3 5 6 1 2 4, if we try this then n=1, l=3, r=5. The cards will be only 6. 6 is greater than 5, hence 0 should be the output.

»
4 months ago, # |
Rev. 2   Vote: I like it +28 Vote: I do not like it

Why would you set $$$n=5\cdot 10^5$$$ to a $$$O(n\log n)$$$ data structure problem?

»
4 months ago, # |
Rev. 2   Vote: I like it -17 Vote: I do not like it

Great mathforces round! + fast editorial

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

Can anyone explain (?) me, In B,

Why k%(y-1) and not k%y ?

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

    because y/y = 1

    and to go from 1 to y you need y-1 operations

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

    The number in the last part of the problem changes as follows:

    2-3-...-(y-1)-1-2-3-...-(y-1)-1-2-3-...-(y-1)

    The reason why $$$(y-1)$$$ is followed by $$$1$$$ is that the number is automatically divided by $$$y$$$ when it becomes $$$y$$$.

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

    Imagine you have y = 3, for example. If you get x to be 1, you spend two (y-1) more operations to come from 1 to 3 (and then to 1 again)

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

    Because once you reach 1 the value of x repeats every y-1 operations.

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

Under what category does problems like 1982B - Collatz Conjecture come under?

I always fail at making proper observations to such problems.

Can anyone please suggest me a list of such past problems?

Btw, I solved 1982C - Boring Day using sliding window technique. Code is quite simple and easily understandable.

Code
»
4 months ago, # |
Rev. 8   Vote: I like it +35 Vote: I do not like it

In problem D, the generalized version of Bézout's identity is used. If you haven't already heard about Bézout's identity, it states that the equation $$$\begin{equation} \ ax + by = d \ \end{equation}$$$ has integer solutions if and only if $$$\displaystyle gcd(a,b)\mid d$$$.

There are two ways to prove this: you can either use the extended Euclidean algorithm, or prove it via an existence proof that can be extended for $$$n$$$ variables instead of just $$$2$$$ (see the generalized version's statement here)

Here's the proof for three variables (heavily inspired by the proof for two variables from MONT) which can be easily extended for an arbitrary number of variables:

Let $$$S = { ax + by + cz \mid a, b, c \in \mathbb{Z} }$$$. Consider the smallest positive element $$$d \in S$$$, $$$d=ax_0+by_0+cz_0$$$. We want to show that $$$d=gcd(a,b,c)$$$. It is sufficient to show that $$$d\mid gcd(a,b,c)$$$ and $$$gcd(a,b,c) \mid d$$$. The second part is true since all of $$$\displaystyle \frac{a}{gcd(a,b,c)}, \frac{b}{gcd(a,b,c)}, \frac{c}{gcd(a,b,c)} \in \mathbb{Z}$$$. For the first part, we need to show that $$$d \mid a,b,c$$$.

Let us do the following for each of $$$(a,b,c)$$$ (I will only do it for $$$a$$$): Assume that $$$d \nmid a$$$. Then $$$a=qd+r, 0<r<d$$$, and $$$r=a-qd$$$. $$$a$$$ is a linear combination of $$$(a,b,c)$$$ and so is $$$d$$$, which implies that $$$a-qd$$$ is too. Thus $$$r \in S$$$, and $$$r>0,r<d$$$. This contradicts our assumption that $$$d$$$ is the smallest positive element in the set. So $$$d \mid a$$$. Repeating a similar process for $$$b,c$$$ shows that $$$d \mid b, d \mid c$$$. Combining these, we get $$$d\mid gcd(a,b,c)$$$.

$$$\blacksquare$$$

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

    Small correction: $$$gcd(a,b)|d$$$

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

      Thank you, corrected!

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

        Also I don't think "The second part is true since $$$a, b, c | d$$$" is correct. For example $$$2x + 3y + 5z = 1$$$ does have integer solutions but neither a,b nor c divide 1. But the gcd part is correct because we can factor out $$$gcd(a, b, c)$$$ from $$$ax+by+cz$$$.

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

          Oops lol, I had meant to type $$$\displaystyle \frac{a}{gcd(a,b,c)}, \frac{b}{gcd(a,b,c)}, \frac{c}{gcd(a,b,c)} \in \mathbb{Z}$$$, but instead ended up typing $$$(a,b,c)$$$ and using $$$\mid$$$. Corrected this as well, thank you; please let me know if you find any other mistakes.

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

    I think you can just use the result of 2 variable to proof $$$n$$$ variable by induction, which would be more brain-dead to do so.

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

    Hey another small correction: "Then $$$a=qd+r,0<r<a$$$". Here it should be $$$0 < r < d$$$. Similarly for "Thus $$$r \in S$$$, and $$$r>0,r<a$$$".

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

    A solution to a Diophantine equation is not unique, because we can form an infinite number of solutions if we know one solution. If a pair $$$(x, y)$$$ is a solution, then also all pairs $$$(x+ kb/gcd(a,b) ,y− ka/gcd(a,b) )$$$ are solutions, where $$$k$$$ is any integer.

    what happens when $$$n$$$ variables instead of 2?

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

      That will also have infinitely many solutions since $$$c_1 x_1 + c_2 x_2 + ... + c_n x_n = 0$$$ has at least $$$1$$$ solution since $$$gcd(c_1,c_2,...,c_n) \mid 0$$$, and all scalar multiples of this solution will also be valid solutions. Then you can add any scalar multiple of any solution for $$$0$$$ to any solution for $$$c_1 x_1 + c_2 x_2 + ... + c_n x_n = d$$$.

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

        I mean for 4 variables suppose I have a solution (a,b,c,d) then how do you form other solutions?

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

          (Note that this doesn't use a given solution to form infinitely many solutions, but instead directly forms infinitely many solutions)

          I guess one option you have is to reduce it to a diophantine.

          Like, for example, say I had $$$5a+15b+10c+25d=5$$$. Set $$$a=b=1$$$, then we have $$$10c+25d=-15$$$ and $$$c=-5n-4,d=2n+1$$$. We can choose any values we want for $$$a,b$$$ since $$$5a+15b$$$ will always be a multiple of the greatest common divisor of the coefficients.

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

Problem C : Detailed Video Explanation (Greedy + Two Pointer) https://youtu.be/zAMyp0dXCKk

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

D is using something called Diophantine equation which I am very much unaware of
From where should I learn these things and is it as scary as it sounds like

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

    You will find it in math olympiad books.

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

      So should I just learn this identity and move on or should I go deep into this like looking for proofs and similar equations?

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

        I would say learn and move on (also do understand the proof imo, but it’s up to you)

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

    If you want to learn via Youtube. You can learn it from Vivek Gupta(As you are comfortable in Hindi). He has covered it

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

thanks for the fast editorial :)

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

can anyone tell me the test case where my code fails in prblm 3??

267372328

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

didn't aware the fact that gcd of set of integer S divides x iff x $$$\in$$$ span(S) 😭 cost me problem D

how people solve this without knowing this fact?

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

    Proof by AC works i believe.

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

    proved it to myself during the contest by trying out some small cases

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

I have been trying problem D for quite a while now, I am using a 2D sliding window approach to calculate the number of "ones" that each submatrix would have. I observed that the difference changes by (k*k — 2*numberOfOnes) for each submatrix and can be either a positive or a negative change.

However I do not understand where I am going wrong. Here is my submission https://codeforces.net/contest/1982/submission/267424514

Can someone please help point out the mistake or even a testcase where my solution would fail.

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

    If I read your code correctly, it seems like you are translating the problem into the coin change problem. i.e. you have coins of denomination $$$a_1, a_2,\ldots$$$, check if there is a way to produce change of value $$$x$$$.

    Firstly the translation is not right. For example if you have $$$x=1$$$ and coin values $$$\{2, 3\}$$$ the coin change problem says no, but the answer should be YES as you can go from $$$1\Rightarrow -2 \Rightarrow 0$$$.

    But even if the translation is correct it's well known such greedy method as you use will not work for all kinds of coin systems, it only works for a subset of coin system called "canonical" (I do not know much about it but it seems interesting). Here's an example that is not canonical (fails greedy): $$$a=\{3, 5\}, x=8$$$. So greedily adding $$$3$$$ gets you to $$$6$$$ which fails, but adding $$$3$$$ once then adding to $$$5$$$ gives $$$8$$$.

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

I did not understand the D solution with GCD. I came out with the solution of finding the difference of ones and zeros for each submatrix using prefix sums (not fast enough to code it in the contest time though).

What I thought is that if I have d1, d2, d3... dn, and I can find c1d1 + c2d2 + ... + cndn that is equal to D, than I can satisfy the conditions.

Anyone can give some link to the proof of the last equation?

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

    Bezout's lemma, you can look it up here- Wiki

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

    I have shown how to prove it in my comment above here.

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

      Hey, I saw your explanation and it makes sense.

      I had however used the following to check whether or not it will be possible to make the difference zero.

      vector<int>v;
      for(auto &it: reduceBy) {
          v.push_back(it);
      }
      while(diff > 0 && !v.empty()) {
          if(v.back() != 0) diff -= (diff/v.back()) * v.back();
          v.pop_back();
      }
      if(diff == 0) cout << "YES" << endl;
      else cout << "NO" << endl;

      here the reduceBy is a set which contains the different impacts we can have on the difference. This however gives me a wrong answer and I don't understand why.

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

    Thanks, guys! I haven't realized that the constants c1, ..., cn could be negative, so I was confusing this with the coin problem (determine if N is achievable with coins [c1, ..., cn]).

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

Can someone explain why my submission for problem D (267400465) gives runtime error? It works correctly on my local machine.

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

    It does not work on cf but works on your machine due to undefined behaviour, in the end you have done *(s.begin()) assuming there are elements in s but that may not be true, in this case it's undefined behaviour as far as I am aware since whatever value is there may be picked up or a seg fault could occur. In your particular case it could have randomly turned up correct on your machine but on cf it could have given a seg fault or the random value could have been 0 giving a mod by 0 error.

»
4 months ago, # |
Rev. 2   Vote: I like it -19 Vote: I do not like it

I am sorry, i got my mistake

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

    No the error is indeed correct. You have added an if statement in your loop with a break the lack of which made the error happen in the first place and is the reason your after contest submission is correct while during contest is not.

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

After the contest I have seen the GCD approach to solve problem D. However I don't understand what's wrong with the following approach:

I have used the following to check whether or not it will be possible to make the difference zero.

vector<int>v;
for(auto &it: reduceBy) {
    v.push_back(it);
}
while(diff > 0 && !v.empty()) {
    if(v.back() != 0) diff = diff % v.back();
    v.pop_back();
}
if(diff == 0) cout << "YES" << endl;
else cout << "NO" << endl;

here the reduceBy is a set which contains the different impacts we can have on the difference. Hence v is a sorted vector in increasing order.

This however gives me a wrong answer and I don't understand why.

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

    v = [3,2] diff = 5 5%2 = 1 1%3 = 1 but it is possible

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

      I apologize I forgot to mention that reduceBy is sorted in increasing order and as we are traversing from the last index, it would pass as v = [2,3] diff = 5%3 = 2 2%2 = 0

      I’ll update the original comment that reduceBy is a set and v would be sorted in ascending order.

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

        well increase v to be [2,3,4] and diff=5. Now it does not pass.

        What you are doing is greedily trying to reach 0, however in this problem the greedy approach is not valid since firstly you are not accounting for negative values of c: For example let v=[4,7] and diff=3 you would assume this is impossible but you can do 3+4-7 to reach 0

        Secondly it isn't necessary that the biggest number will indeed be reduced from diff to reach 0, think coin dp problem.

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

          That makes so much sense, and I feel dumb for not getting it myself. Thank you very much it’s clear to me why my submission was wrong.

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

In E there exists a solution with time complexity $$$O(T\log^2 n)$$$,using only DP. The main idea is trying to find every starting point of consecutive ones ($$$a_x=1$$$ if x is valid). You can see the implementation here.

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

    Can you please explain the states of your dp and recurrence relation. I have been trying to think of a dp solution from 3 hours but i am not able to.

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

Can someone please let me know me where my submission to problem C might be failing ?

267403795

edit: I got it..

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

Hi everyone!

Can someone please point out why my submission 267373128 might be failing on the 475th test case of Test 2 of problem C. The following is the approach:

  1. I used a greedy approach for the problem. I declared two variables named sum and cnt (both initially set to 0).
  2. Then I started iterating over the array and check if sum + a[i] < l, then increased sum by a[i] and moved on to the next element.
  3. Else if sum + a[i] >=l && sum + a[i]<=r, that means this is the case when Egor would win. So I incremented cnt, set sum = 0 and move onto the next element.
  4. Else, which means sum + a[i] > r, then I have used a nested if else. If a[i] > r, then Egor cannot win if this element is included, so I set sum= 0 and moved onto the next element. Else if a[i]<=r, set sum = 0, but this time did not move to the next element as this element can contribute to forming a sum which is in the range.

Any help will be appreciated!

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

    I also got the same WA on 475th case. Try your code for input n=3,l=5,r=6 and value of array as 1,2,4. The output should be 1 but my code was giving 0.

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

    In your 4th point, when a[i]<=r you can still win with that element if you move your left pointer to the right by some amount (possibly). That is to say, if I'm taking the sum from index 0 to index i and it's larger than r, I could take from index 1 to i and that could maybe work.

    Edit: a[i]<=r instead of >

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

in the first problem, the score if x1 > y1 and x2 > y2 and y2 > x1 in that case there is a possiblity that at some point the yt would have been equal to xt ??

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

    if x1 > y1 and x2 > y2 you could always increment x all the way and than y , remember we have to reach x2 and y2 eventually not that y2 is already there to hinder with x

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

hey , there are many telegram groups where solutions got leaked during contest please take some action. below is one groups where solutions and code was sharing during contest : https://t.me/codeforces_cp

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

    yup, i to know a few grps A to D were discussed and shared during the contest :(

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

    ur prefix sum condition is wrong . it should be :-

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

Ayo can someone help my code debug for Problem D. It says Wrong Answer on 4th Test Case. 242nd Token differ. 267451989

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

    The problem is when both i>0 and j>0 you need to add v[i-1][j-1]

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

      Thanks!! You a big help. Totally forgot about that

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

Yo, in qA, the third test case, why cant the 1st team score a goal and then the score would have been equal??

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

    Yeah, Maybe But the problem is asking for "NO" iff you are sure the goals were equal at one point of time

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

can someone please give the 475th test case for problem C with n l and r?

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

Can someone please check what is wrong with this submission for D ?

267454158

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

    You are missing a parenthesis when defining each pref1[i][j], just compare with the line above

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

I am getting a TLE(Case 10) in Problem C. https://codeforces.net/contest/1982/submission/267454949

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

    Your solution is O(n^2). Try to optimize it by using prefix sums

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

Could someone explain the editorial of E for me. It is still unclear for me, and what is the main point of the approach?

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

    Note that "Bit sequence" can be generated by following infinite process:

    void step(vector<int>& a) {
        int sz = (int) a.size();
        for (int i = 0; i < sz; i++) {
            a.push_back(a[i] + 1);
        }
    }
    
    vector<int> a = {0};
    while (true) {
        step(a)
    }
    
    

    i.e $$$[0] \to [0, 1] \to [0, 1, 1, 2] \to [0, 1, 1, 2, 1, 2, 2, 3]$$$ and so on.

    It's not hard to see that it's actually a bit sequence: on the $$$i$$$-th step, we record all integers from $$$[2^i, 2^{i+1})$$$. These integers have one bit for $$$2^i$$$, and the rest of the bits correspond to the number of bits in $$$[0, 2^i)$$$, which is indeed the current sequence. Therefore, on the $$$i$$$-th step, we clone our sequence with an increment to the end of the sequence.

    From this point of view, the periodic nature of this sequence is clearly visible. Imagine $$$x$$$ is a maximum integer, such that $$$2^x < n$$$. Then we can split the sequence $$$0...n-1$$$ into $$$0..2^x-1$$$ and $$$2^x...n-1$$$. As we can see, the second part is also a prefix of the sequence but with a +1 increment. Therefore, if $$$x > k$$$, we can just solve for the two parts independently and then sum up the answers (since no good segment crosses $$$2^x-1$$$). And if $$$x \leq k$$$, the answer is simply $$$\frac{n(n+1)}{2}$$$, except for the case when $$$x = k$$$ and $$$n = 2^{x+1}$$$, then it is $$$\frac{n(n-1)}{2}$$$. With these formulas, you can write a simple memoization solution. It's not hard to see that it works fast because there are $$$O(\log^2 n)$$$ special states, where $$$n$$$ is a power of two, and we are always recalculating from a special state and a state that lowers $$$n$$$ at least twice.

    Code: 267468663

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

      Nice Approach. But could you explain why you did k — 1 for the second array that is from [2^x to n — 1] ?

      Like I get it that for the array [2^x to n — 1], there is an 2^xth extra bit and just this set bit is added to the sequence [0 to 2^x — 1] and it becomes the same sequence. But why k — 1 ? Should it not be k + 1 as we increased one bit to the original problem ?

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

        Yes we increased one bit. Therefore condition turned to $$$bit(a_i)+1 \leq k \to bit(a_i) \leq k-1$$$.

        Like, after reduction to prefix we will actually have one bit more than on prefix. And in our world we want to count $$$\leq k$$$ therefore after reduction to prefix we need to count $$$\leq k-1$$$, so that with this extra bit it will be $$$\leq k$$$.

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

          Ohh, now got it. Thanks a lot.

          Also the TC will be o(log^3n) right ?

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

            It's $$$O(M \cdot (\log^2n + T\log n))$$$, where $$$M$$$ denotes $$$map$$$ runtime. But note that it can be easily rewritten without map to be clear $$$O(\log^2n + T\log n)$$$. Here $$$O(\log^2 n)$$$ to calculate answers for all cases where $$$n$$$ is a power of two, and after this single testcase will take $$$O(\log n)$$$. The upside of using a $$$map$$$ is that you don't need to think about those special states, you can just write all transitions as it is, and $$$map$$$ will optimize it for you, for the cost of $$$map$$$ runtime. In this problem constraints and TL are pretty generous luckily, therefore $$$map$$$ is safe to use.

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

This round helps a lot with my rating :)

The problem D is pretty interesting I think.

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

    True , generally i am not able to get to D but this time it was from number theory which i am pretty comfortable with , hence got it done....

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

      Well,I think the problem D is more likely to be some ideas added together. Actually, These ideas are pretty common if you do more maths problems :)

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

please explain how I can withdraw my earnings Nears?

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

In soccer question 3rd example the output should be NO but it's given yes .

for the test case 1 2 4 5 there will be a time when score will be 2 : 2 . so the output should be No , plz clarify my doubt.

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

Just wondering, what's the point of having multiple test cases in F if $$$t$$$ is so small ($$$t \leq 10$$$) and there are only three tests (#1, #2, #3) where $$$t > 1$$$? Personally, I prefer problems with only one test case, as I don't have to care about re-initializing variables.

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

    Could you explain Problem F. I am unable to understand the editorial.

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

FelixArg , My solution for D shouldn't have passed the Final system test cases, but it did.

  • I knew the current difference between type1Sum, and type0Sum. ( let's call it RequiredDifference )

  • I knew for each of the sub-rectangle of size k*k, what are achievable differences. Lets call them (d1, d2, d3 ... dk).

I knew that I had to do a1 * d1 + a2 * d2 + a3 * d3 + ... ak * dk = RequiredDifference

I didn't know how that gcd ( d1 , d2 ... dk ) | requiredDiff .

But I knew, for ax + by = z , then gcd(x, y) | z. So I used this two variable equation property and passed test cases. Refer to my solution.

The test cases were weak for D. Ideally my solution shouldn't pass. Thanks to djm03178, it was later hacked.

Also, I honestly felt helpless during the contest because I didn't know this property gcd ( d1 , d2 , d3 ... dk ) | requiredDiff.

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

    I wonder, does that solution have an actual counterexample? I'm stress testing a bunch of small cases but none are found yet. Anyways, to explain the TL hack, it looks something like this:

    $$$n=m=8$$$, $$$k=4$$$

    00000000
    00000000
    00000000
    00001111
    11110000
    11110000
    11110000
    11110000
    

    Expanding this pattern to $$$n=m=500$$$, $$$k=250$$$ makes 15281 distinct possible differences, so it's not feasible to perform gcd on every pair in 2 seconds. Since $$$k$$$ is even, the differences can only be even as well, so having an odd sum of $$$a_{ij}$$$ makes it impossible to find a possible way and therefore it can only realize that the answer is NO after running the whole loop.

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

      I got a counterexample, a=42 b=70,c=30, pairwise gcd are 14, 10,6 leaving out say 8 but gcd of all is 2 so all even numbers work.

      • »
        »
        »
        »
        4 months ago, # ^ |
        Rev. 5   Vote: I like it +3 Vote: I do not like it

        I mean, finding three numbers for the counterexample is easy, but making an actual test for that is another story, because of how hard it is to obtain only the desired values and not undesired ones with the 'windows'.

        I think I have a brief idea for this though. We can have large enough $$$k = n \lt m$$$, and control the difference with each column, so only each pair of columns of distance $$$k$$$ can affect the values and nothing else.

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

        Ohhh, I think it works but the other hack seems to be already doing the same thing. I didn't realize because the hacked solution has a slightly different approach, but I guess it essentially has the same condition.

        Here's the one I made:

        1
        14 16 14
        0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
        0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
        0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
        0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
        0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
        0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
        0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
        0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
        0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
        0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
        0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
        0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
        0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
        0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2
        0011110001111111
        0011100001111111
        0011100001111111
        0011100001111111
        0011100001111111
        0011100001111111
        0011100001111101
        0011100001111101
        0011100001111101
        0011100001111101
        0011100001111101
        0011100001111101
        0011100001111101
        0011100001111101
        
        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Damn I'll come back to this 6 months later when I am hopefully a little better equipped to learn this stuff, haven't dipped into hacking yet and coming up with test cases rather than numbers immediately feels much harder. Either way cool that you were able to come up with this.

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

Anyone Can please figure out which test case my code isn't passing on 3rd.Here is the submission id. 267473714

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

    See this Testcase

    4 11 11

    1 2 3 6

    Your program considering 1+2+3+6 > r then debunking all 1,2,3 and considering just 6 which gives 0 as answer.

    But what it should do is just take 1 in the first round and lose and take 2+3+6=11 on the 2nd Round which gives 1 as a answer

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

i tried to solve C problem by using prefix sum but i do not get what is wrong in my approach below i will attach my submission

https://codeforces.net/contest/1982/submission/267490137

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

include <bits/stdc++.h>

using namespace std; using namespace chrono;

define ll long long

define mod 1000000007

define nn "\n\n"

define pb emplace_back

define sz(x) int(x.size())

define all(x) x.begin(), x.end()

define watch(x) cout << #x << " = " << x << '\n'

define endl '\n'

int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

auto ssss = high_resolution_clock::now();
int T;
cin >> T;
for (int tc = 1; tc <= T; ++tc) {

    cout << "Test Case #" << tc << ":" << endl;
        int n , l , r;
        cin >> n >> l >> r;
        ll ans = 0 , sum = 0;
        vector<int> a(n);
        for(auto& x : a) cin >> x;

       int index = -1;
        for(int i = 0; i < n; ++i) {
         sum += a[i];
         if(sum >= l && sum <= r) {
             sum = 0 , ans++;
             continue;
         }
         else {
               index = (index == -1) ? i : index;
             i++;
             while(i < n && sum  <  l) {
                sum += a[i];
                i++;
             }

             while(index  < i && sum > r) {
                 sum -= a[index];
                 index++;
             }

             if(sum >= l && sum <= r) {
                sum = 0;
                ans++;
          index = -1;
             }
             i--;
         }
    }

    cout << ans << endl;       


    cout << nn;
}

auto eeee = high_resolution_clock::now(); duration duration_sec = duration_cast<duration>(eeee — ssss); cout << "Total time taken: " << duration_sec.count() << " seconds" << endl; return 0; }

Can anyone tell me why this code is not getting selected o 3rd ??

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

In problem C my code 267502094 is showing TLE on 17th test case. My logic is simply to iterate till the segment sum is >= l. If its becomes greater than r then i'll just take nly the first card of that segment and chose to lose the round... starting the next round from the next card thus. Help me in finding my mistake.

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

    just think of a case where l=1e6 and r=1e6 and the array be like 1.......(1e5) times and one more element at the end is 1e9 in this case your code will check and remove the first element step by step and by checking again whole segment to the last value will become o(n*n).

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

Hey, For problem C I was trying to write a dp solution in the contest but I was getting WA on test 2, eventually had to go without dp. Can anyone please help me in finding the error? I have wasted a lot of time finding a bug :(

Please help, my submission: 267511316

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

An alternative way to calcute the DP in E goes like this. P. S. the length of the text might seem daunting but it is because I tried to explain the logic behind every step.

Again, $$$dp(i, j)$$$ represents the number of subarrays for the first $$$2^i$$$ numbers if we can have at most $$$j$$$ bits. It is easy to notice that this formulation is equivalent to the number of subarrays formed by the numbers for which only the first $$$i$$$ bits can be non-zero. This might be useful for some for later intution. To make things a bit easier to write down, let's denote $$$g(x)$$$ as the number of subarrays contained in an array of length $$$x$$$, so $$$g(x) = \frac{x(x + 1)}{2}$$$.

If $$$j \geq i$$$, then the answer is simply $$$g(2^i)$$$, because no number smaller than $$$2^i$$$ has more than $$$i$$$ bits.

if $$$j=0$$$ then the answer is 1 because there is only one possible subarray (the one containing just a zero).

Now for the general case, $$$ 1 \leq j < i$$$, we need to notice something. The smallest number with more then $$$j$$$ bits will be one that looks like $$$1...1$$$ in binary, where there are a total of $$$j + 1$$$ bits (equal to $$$2^{j+1} - 1$$$). In this case all the subarrays formed by these numbers will be included in the dp. The number of these subarrays is $$$g(2^{j + 1} - 1)$$$. It is also important to note that these numbers form a sequence of continous good numbers which don't neighbour the other good numbers because of $$$2^{j+1} - 1$$$.

The number after $$$2^{j+1} - 1$$$ is $$$10..0$$$ or $$$2^{j + 1}$$$ where there are $$$j + 1$$$ zeros. We can notice that the number of subarrays formed by numbers where this lone bit is the highest one is just $$$dp(j + 1, j - 1)$$$, $$$j + 1$$$ because that is the number of zeros we have to work with and $$$j - 1$$$ because we need to account for the extra bit. In a similar fashion we include the numbers for which the $$$(j + 2)rd$$$ (0-indexed) bit is the highest one, the answer for which will be $$$dp(j + 2, j - 1)$$$. If we continue this pattern for every bit, we will have $$$dp(i, j) = g(2^{j + 1} - 1) + dp(j + 1, j - 1) + dp(j + 2, j - 1) + ... dp(i - 1, j - 1)$$$. The reason why we can sum up these states is because the sequence of numbers considered by each state are seperated by at least one bad number. E.g. $$$2^{j+1} - 1$$$ seperates the first sequence of numbers from the others. Similarly we can be sure that the numbers considered in the second term are seperated by the number $$$2^{j+2} - 1$$$ (the binary representation of this number is just $$$j + 1$$$ ones so this number is bad). For the third term the guaranteed bad number is $$$2^{j+3} - 1$$$, for the fourth its $$$2^{j+4} - 1$$$ and so on. This was also my intution for this dp. To somehow formulate the formula for dp such that all the terms are seperated by bad numbers. This dp yields a complexity of $$$O(log(n)^3)$$$ and it can be optimized to $$$O(log(n)^2)$$$ with prefix sums but it is not necessary to pass the TL.

You can use this DP to solve the rest of the problem in the same way as the authors did but my approach is a bit simpler in my opinion (though I think they are fundementally the same).

Step one: check if the smallest number with more than $$$k$$$ bits ($$$2^{k+1} - 1$$$) is greater than $$$n$$$, if that is true, then add add $$$g(n)$$$ to the answer and terminate.

Otherwise we go to the highest bit of $$$n$$$. Let's say that is the $$$b$$$-th bit. We add the subbarays not containing the bit to the answer, the number of which is $$$dp(b, k)$$$. Then, we reduce $$$k$$$ by 1 and $$$n$$$ by $$$2^b$$$ since every other solution will include the $$$b$$$-th bit. Now we go back to step one and repeat until $$$n$$$ is zero or code is terminated in step one. We can be sure that the numbers included in the subbarays for each step are not neighbouring because of similar reasoning to the DP. The biggest number considered in the range (which is just a sequence of $$$1$$$-s in binary), seperates them. If there aren't more than $$$k$$$ bits the code terminates at step one, so we can be sure that everything is nice and seperated.

Here is my code. code

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

    Thank you very much for the detailed explanation. dp(i, j) = g(2^(k + 1) — 1) + ... should be dp(i, j) = g(2^(j + 1) — 1) + ...

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

In problem D, it is mentioned that, checking D mod gcd(d1,d2,…,dq)=0 is sufficient to test the existence of the solution for the equation c1⋅d1+c2⋅d2+⋯+cq⋅dq=D. Is it any proved theorem or intuition? Can any one explain this?

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

problem c) https://codeforces.net/contest/1982/submission/267544904 why is it failing on other tests

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

Please someone explain what the below lines do in code of solution E?

if (s1 == e1 && s1 != 0){
	s_cur = (s1 + s2);
}
if (s2 == e2 && s2 != 0){
	e_cur = (e1 + e2);
}
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Am i the only one who found F very easy for its position?

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

I have been accounted for cheating in question B. I am really not aware that using third party websites as code editor is a violation. I just came to know that once I have received mail regarding plagiarism. I assure that this will not repeated and I kindly request not to skip me in the upcoming contests. I hope my request will be considered.

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

include<bits/stdc++.h>

define ll long long

using namespace std;

int main(){ int t; cin>>t; while(t--){ ll n,l,r; cin>>n>>l>>r; vectorv(n); for(ll i=0;i<n;i++){ cin>>v[i]; } reverse(v.begin(),v.end()); stackst; for(ll vl:v)st.push(vl);

ll sum=0,cnt=0;

while(!st.empty()){

sum+=st.top();

    if(sum>r){

       sum=st.top();


    }

if(sum>=l&&sum<=r){
    sum=0;
    cnt++;
}

st.pop();

} cout<<cnt<<endl;

}

} help me to get the corner case

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

Can someone share the greedy solution of problem C

Or you can show the mistake of my solution

Link to submission

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

please help me to understand why equation in problem D looks like that

c[1] * d[1] + c[2] * d[2] + c[i] * d[i] = D

shouldn`t it be:

c[1] * d[1] + c[2] * d[2] + c[i] * d[i] = -D

because D is equal heights of mountains without snowy caps — heights of mountains with snowy caps and we want D to be 0, therefore, when we go through an n X m matrix considering every k X k submatrix we count how many there are mountains without snowy caps and we add that quantity multiplied by some c[i], after that we substract quantitiy of mountains with snowy caps multiplied by c[i]

that means we want

D + NOT_SNOWY * c[i] — SNOWY * c[i] = D + (NOT_SNOWY — SNOWY) * c[i] = D + d[i] * c[i] to be equal to 0

hence

D + d[1] * c[1] + d[2] * c[2] + d[2] * c[2] = 0 => d[1] * c[1] + d[2] * c[2] + d[i] * c[i] = -D

where am I making a mistake?

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

Is there any other way to solve this problem besides the method provided in the editorial? If you are not from a math background, guessing that method is pretty difficult. Are there any other possible solutions, like using dynamic programming?

I realized that if we calculate the net difference of the types of mountains in each k*k matrix, then the question can be the same as finding the sum of h (total difference between the height of two types of mountains) using n(net difference between types of mountain in each k*k matrix) values, which can be added or subtracted to make the sum of h.

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

For E problem - In the given test case 576460752303423268 59 (The last one)

int mod = 1e9+7; The answer is just (C(n, 2)%mod + n%mod)%mod But I think my code is doing something wrong while calculating C(n, 2)%mod

And the final answer that I'm getting is 777901708. If anyone has solved it, can they tell me if there is some catch or a different method to calculate this?

PS: I took help from stack overflow for getting the (nCr % p) value for big values of n.

Thank You

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

Could I get some help please? The sample test case for small numbers seems to pass but not for big numbers ex: With input: 795569939321040850 56 it returns 332746568 instead of 741136395

Submission #: 267926843

Thanks!

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

can anyone please figure it out, whats wrong with this code? I implemented exactly the way it's given in the editorial . still getting WA in test case 4(426th token) submission:https://codeforces.net/contest/1982/submission/267948051

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

.

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

Can someone please figure out why my code isn't accepting? Here is the submission link

https://codeforces.net/contest/1982/submission/268111102

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

Good round

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

Can someone tell me how to do problem E using technique meet in the middle?

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

It is able to also do F using the formula that, if we treat $$$a_1, a_2, ..., a_n$$$ as array

$$$ \text{argmax}_{L} a_{1..L} = \text{sorted}(a)_{1..L} = X + Y $$$

where $$$X$$$ is the largest index $$$i$$$ such that for all $$$j \leq i$$$, $$$\text{argmax}_{k} (v_j = v_k) - \text{#}[x : x \leq v_j] = 0$$$, and $$$Y$$$ is the "tail", which is, if $$$a[X+1]$$$ is directly following $$$a[X]$$$ in the array, $$$Y$$$ is the $$$\text{argmax}_T \ \ {a_{X+1}=a_{X+2}=...=a_{X+Y}}$$$

The two parts of $$$X$$$ can be maintained in a lazy propagated walkable (binary searching) segment tree, and $$$Y$$$ can be also use another segment tree to find, or can build one without having lazy prop. Range queries can using BIT. I used two lazy prop (even though $$$Y$$$ don't need) so have to use fast IO to speed up sth, especially when outputing the 2e6 datas...

https://codeforces.net/contest/1982/submission/270269570

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

this is my java code using dp, it executes correctly for smaller inputs,but for larger inputs it results in Time limit exceed error. please help me . ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

private static String soccerTab( long score1, long score2, long maxScore1, long maxScore2 ){ 

    if( (score2 == 0 && maxScore2 == 0) && (score1 < maxScore1) ){
        return "YES";
    }
    boolean dp[][] = new boolean[(int)maxScore1+1][(int)maxScore2+1];

    dp[(int)maxScore1][(int)maxScore2] = true;

    for( int i = (int)maxScore1; i >= 0; i-- ){ // not setting to 1 0 , 5 0 testcase
        for( int j = (int)maxScore2; j >= 0; j-- ){
            if( dp[i][j] ){
                continue;
            }
            else if ( i == j ) {
                dp[i][j] = false;
            }
            else if( i == dp.length - 1 ){ //
                dp[i][j] = dp[i][j + 1];
            }
            else if( j == dp[i].length - 1 ){ // last row
                dp[i][j] = dp[i + 1][j];
            }
            else{
                boolean can1Win = dp[i + 1][j];
                boolean can2Win = dp[i][j + 1];
                dp[i][j] = can1Win || can2Win;
            }
        }
    }
    if( dp[(int)score1][(int)score2] ){
        return "YES";
    }
    else{
        return "NO";
    }

}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~``

thanks for the help!

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

can somebody explain in 1st problem why there can't be a moment in 3rd testcase where the scores can't be equal at all mean reaching from (1,2) to (4,5) 1 can first go to 2 so there will be a moment right??

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

    There can be a moment, you are right. The question is whether it's certain that there was such a moment. If there 100% was a moment, where the scores were equal, print NO, otherwise(like in 3rd case) if it isn't certain, print YES.

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

      okay okay so how does you make it certain ??

      I actually don't understand it still I can't understand why the editorial solutions works still

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

        For it to be certain, one of the teams had to have made a comeback. For example, if the score is 1:2, and when he returns it's 3:2. There is only one possible scenario and that is for the first team to score a goal and make it 2:2, and then score another goal and make it 3:2. In that scenario(which is the only possible one), there was a time where the scores were equal. If you write down a few more examples where a team made a comeback, you will see that in any scenario you come up with, at some point, their scores had to be equal. And in the opposite example where the team that was in the lead, stayed in the lead you can always find a scenario where they weren't equal at any point.

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

cool problems! thank you for tutorial

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

Can someone explain the time complexity of this 278748608

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