UPD: Code links are working now

1731A - Joey Takes Money

Idea: s_jaskaran_s

1731B - Kill Demodogs

Idea: s_jaskaran_s

1731C - Even Subarrays

Idea: ka_tri

1731D - Valiant's New Map

Idea: s_jaskaran_s

1731E - Graph Cost

Idea: s_jaskaran_s

1731F - Function Sum

Idea: nishkarsh and s_jaskaran_s

• 17 hours ago, # ^ | What did I say wrong?

• 34 hours ago, # ^ | Multiply by 2022 saves you from getting stuck with modular-division/overflow-problems in Problem B because you can just divide 2022/6 = 337 instead of calculating modular inverse of 6

  • 33 hours ago, # ^ | LOL, I didn't noticed that 2022 is divisible by 6 and just copy pasted the modular inverse code.

  • 23 hours ago, # ^ | Shit Never really thought about that

  • 20 hours ago, # ^ | OMG I thought 2022 % 6 != 0 so I just multiplied by 1011 / 3, still worked though :)

• 35 hours ago, # ^ | ← Rev. 2 →   -82 The comment is hidden because of too negative feedback, click here to view it

  • 35 hours ago, # ^ | that's not how proofs work.

• 35 hours ago, # ^ | ← Rev. 2 →   +7

  • 34 hours ago, # ^ | ← Rev. 2 →   -9 Is there any other yt channels who upload solutions frequently after the contest ? I mean for every contest iam a beginner so they will help me while upsolving

• 30 hours ago, # ^ | ← Rev. 2 →   -68 The comment is hidden because of too negative feedback, click here to view it

  • 26 hours ago, # ^ | The comment is hidden because of too negative feedback, click here to view it

• 22 hours ago, # ^ | ← Rev. 2 →   +25 I will show very simple proof with simulation of * knapsack solution and some properties on the knapsack array that results taking biggiest group everytime is optimal. Let array we're working on = {}. where every element denotes an avaible group of size a[i]. and our knapsack array will be denoting subset with minimum size of prefix with . Transitions: at any step, is a non-decreasing sequence. ( ). Proof by Induction We don't need minimise operation, we can directly assign to . Proof by Induction As you notice from second property, transitions show it's optimal to take greatest element whenever we can.

• 18 hours ago, # ^ | Proof: Let's first note that we can find at least one pair of vertex with GCD(u, v) <= n / 2 and we cannot if GCD > n / 2. It is easy because there is (G, G * 2) for every G <= n / 2 and there is not else. We need to minimize the number of moves in the task. Let's greedy take pair with a largest GCD first, moving from n / 2 to 1. If at some step we took more (current > m), then notice that the last step (let's say k edges in this move) can be replaced by k - (current - m) so that it is exactly m. It is possible always because k - (current - m) < k and there is at least one such pair.

• 35 hours ago, # ^ | using a frequency array will work

• 35 hours ago, # ^ | ← Rev. 2 →   0 Yes, I faced it too. In an attempt to remove tle I ended up with a bunch of WA and RE T_T

• • 12 hours ago, # ^ | Actually, it won't help much in this problem. Even std::map gives TLE (due to the extra factor) and here is the std::unordered_map (with the splitmix64 custom_hash) solution which gives TLE.

• 36 hours ago, # ^ | the ans of b is 1*1+1*2+2*2+...(n－1)*n+n*n=(1*1+2*2+...n*n)+(1*2+2*3+...(n－1)*n)=n*(n+1)*(2n+1)/6+(n－1)*n*(n+1)/3.

  • 34 hours ago, # ^ | Why the sequence 1*2+2*3+...(n－1)*n) is not generating an equation n*(n+1)*(n+2)/3??

    • • 34 hours ago, # ^ | ok, i couldn't get this on first sight.

        • 34 hours ago, # ^ | ← Rev. 2 →   +2 I think problem B was so confusing

    • 30 hours ago, # ^ | If you understood that 1*1 + 2*2 + 3*3 + 4*4 + ... + n*n = n*(n+1)*(2n+1)/6. The sum of the series 1*2 + 2*3 + 3*4 + 4*5 + ... + (n-1)*n can be represented as the sum of the series (1*1 + 2*2 + 3*3 + 4*4 + ... + n*n) — (1 + 2 + 3 + 4 + ... + n) The sum of the second part is simply the sum of an arithmetic progression.

• 35 hours ago, # ^ | ← Rev. 2 →   0 Mostly used Oeis but zig zag path from start cell to end cell will be optimal if you observe few examples so a(n)=a(n-1)+n*(n-1)+n*n , from here you can derive

  • 23 hours ago, # ^ | Why my code is not working ll n; cin>> n; ll ans = ((n*(n+1))%mod*(4*n — 1))%mod; ans = (ans/6); cout<<(ans*2022)%mod << endl; return 0;

    • 22 hours ago, # ^ | you need to take mod of (4n-1) and also you inverse of 6 in 3rd and 4th line

      • 21 hour(s) ago, # ^ | can u please give a working code based on my solution. :)

        • • 18 hours ago, # ^ | In this solution I have not used the concept of modular multiplicative inverse. I am not able to use MMI in this problem. can u write the code for MMI?

            • 18 hours ago, # ^ | (1/a) mod m=(a^(m-2)) mod m if m is prime.

              • 18 hours ago, # ^ | Thanks :)

• 35 hours ago, # ^ | ← Rev. 2 →   +22 add them

  • 27 hours ago, # ^ | ← Rev. 2 →   0 kami, please tell me how i(i — 1) is Ei^2 — Ei?

    • 24 hours ago, # ^ | Just open up the brackets:

• 35 hours ago, # ^ | wolfram alpha

• 33 hours ago, # ^ | I just thought about the squares as actual squares. If you line them up the squares to create a side, one side will be n(n+1)/2. Now a trick I knew was that adding the next odd number will give you the next perfect square. So if we want another n perfect squares, we could add n ones n-1 threes etc… This can be arranged where the nxn square gains an additional length of one and the n-1 gains three etc. We can then add an additional square with side lengths 1 to n to make the side length of each square 2n+1(basically the side of n gains n+1, n-1 gains n-1 + 3 etc). Therefore, it can be computed as (n(n+1)/2 * (2n+1))/3. Hopefully my explanation is not horrible. My submission with the formula:https://codeforces.com/contest/1731/submission/186917982

• 36 hours ago, # ^ | It's not just you, but at least they did a great job at preventing .

• 35 hours ago, # ^ | Yes I had 10 wrong submissions :")

  • 34 hours ago, # ^ | ← Rev. 2 →   +5 haaa!!! Simple Minded People. I had 16 wrong submissions

• 35 hours ago, # ^ | usually you calculate the answer and after each operation,you get ans %= modulo. if you have a division, you can use the modular inverse and multiply by it.

• 35 hours ago, # ^ | Try to refer to these topics: 1)Modulo Inverse 2)Binary Exponentiation(used in implementation of Modulo inverse) 3)Identity- (a-b)mod M = (a-b+M) mod M , (Modulo subtraction)

• 35 hours ago, # ^ | You should read "Competitive Programmer's Handbook". You will find lots of basic and essential topics for Competitive Programming.

• 16 hours ago, # ^ | on problem D, A sparse table is being used here. I don't know what it is. Any good resource for the same?

• 11 hours ago, # ^ | There is a dp solution as well and your final time complexity becomes O(m*n* log(min(n , m)) . You can check my solution :)

• 35 hours ago, # ^ | Why is your rating <1500 and it's showing that you are a legendary grandmaster? Is it some glitch of cf??

  • 35 hours ago, # ^ | It is the Magic of Santa Claus.

    • 35 hours ago, # ^ | magic didn't happened with me XD

      • 35 hours ago, # ^ | cuz u stupid

        • 35 hours ago, # ^ | Its happening to all bro go to your profile you'll be able to magic right of submission button

          • 35 hours ago, # ^ | Lol got it now Hadn't noticed that yet

• 35 hours ago, # ^ | I mean anyone use set to do create table in problem D ?

• 35 hours ago, # ^ | same bro

• 35 hours ago, # ^ | Great solution..

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;cin>>t;
    while(t--)
    {
        long long int mod=1000000007;
        long long int n;cin>>n;
        long long int sq=(n*(n+1)*((2*n)+1))/6;
        
        for(unsigned long long int i=1;i*i<n*n;i++)
        {
            long long int p=(i*i)+i;
                sq+=p;
            
        }
        long long int ans=2022*sq;
        ans=ans%mod;
        cout<<ans<<endl;
        
    }
return 0;
}

• 35 hours ago, # ^ | Multiplying n*(n+1)*(2*n+1) is bigger than n^3. n^3 does not fit into long long, so therefore it's a wrong answer.

  • 35 hours ago, # ^ | Thank you so much T-T

• 35 hours ago, # ^ | ← Rev. 2 →   0 rearrange left side to form 2*i*i + i Now you only need to know the formula of sum of squares of 1 to n and sum of numbers of 1 to n which are pretty well known.

  • 35 hours ago, # ^ | How to rearrange the left side to anything? How, what is the formular for ?

  • 35 hours ago, # ^ | ← Rev. 7 →   +1 (n*(n+1)*(2n+1))/6 Here is one proof: Your text to link here...

• 34 hours ago, # ^ | My intuition here was to look at a ratio between your desired sum and . Then notice a constant increment in this ratio and derive both and from there

• 35 hours ago, # ^ | The comment is hidden because of too negative feedback, click here to view it

  • 34 hours ago, # ^ | Well to be fair I’ve done a similar problem before https://atcoder.jp/contests/abc203/tasks/abc203_d?lang=en. But I also found this problem to be easy so I don’t know.

• 34 hours ago, # ^ | Yes, very tight constraints on C. I usually don't think that much about implementation in ABC, but this has taught me a lesson that you should use vectors and arrays instead of maps and hashmaps

• 34 hours ago, # ^ | That's a problem. Can be solved using prefix xor-s. I can give an easier explanation of this technique. Let's forget about xor and think about sums. How many subarrays are there with a given sum? You just count prefix sums and for each prefix i you need to find the number of prefixes j (j <= i) such that pr[i] — pr[j] == sum. With xors it's done in a similar way

  • 32 hours ago, # ^ | Oho.. Great. Thank you.. Finally got it

• 35 hours ago, # ^ | Congratulations on becoming master.

• 34 hours ago, # ^ | Congratulations for orange man!

• 35 hours ago, # ^ | ← Rev. 3 →   0 Even when I flattened the input array to 1 dimension and used 1D sparse table on it, it still got MLE ( MB) in custom invocation.

• 35 hours ago, # ^ | You can get rid of one using the fact that we are interested only in squares. Just let be the minimum in square .

  • 34 hours ago, # ^ | That's neat! Forgot that we only consider squares.

• 35 hours ago, # ^ | I managed to squeeze such solution after this contest by using short instead of int (any values bigger than 1000 can be changed to 1000) and remembering only every other level of sparse table (so you have to look up 4 instead of 2 values each time), but that barely fits and feels not like what was intended.

• 35 hours ago, # ^ | You can't use normal division for modular arithmetic operation. You need to use modular multiplicative inverse, for any divisional operation when you are using MOD

• 34 hours ago, # ^ | Instead of using modulo inverse, you can just find out where to divide out the number first. Easiest way is in 2022, but I didn’t find this observation in contest.

  • 33 hours ago, # ^ | Yes that would have been easier.

• 35 hours ago, # ^ | Hm, I can't see them too

• 34 hours ago, # ^ | Yes, I am also not able to see the codes.

• 3 hours ago, # ^ | ← Rev. 3 →   +2 We can also extract the polynomial itself from the method of differences. Using the 0-indexed sequence {7, 22, 50, 95, ...} p(X) = 7 + 15 (X choose 1) + 13 (X choose 2) + 4 (X choose 3) Consider X choose 1 = X, X choose 2 = X * (X — 1) / 2 and so on. This might be some abuse of that naming in order to make it work for negative values, but it works. This method of differences is something that I (re)discovered by myself when playing around with sums of powers during high school classes. I wouldn't expect it to be mentioned in codeforces lol. My current opinion on it is that it's fun but not practical since lagrange interpolation seems way more practical when solving problems. Also, you can get one evaluation using lagrange interpolation in O(N) given that the points you took to interpolate are equidistant (as in for x in [0, 1, 2, 3, 4, 5, ...]). That's the whole idea of the following problem: https://codeforces.com/problemset/problem/622/F

  • 18 minutes ago, # ^ | I do not quite understand how the method of differences directly concluded the polynomial you have. I mean, I do understand where the coefficients and come from, but I do not understand where and and so on came from. With regard to the linear Lagrange Interpolation. I have never seen it that way, and it is a great idea. Thanks!

• 33 hours ago, # ^ | ← Rev. 2 →   +18 Actually, apparently P(x) always have degree 2. I just don't know how! So we just have to calculate for p=1 and p=2;

• 32 hours ago, # ^ | There is a small typo here. In the last line of the formula, it should be instead of

  • 32 hours ago, # ^ | Fixed, thanks

    • 32 hours ago, # ^ | Could you explain further how I can use this formula to find the sum of the multiplication of some power terms?

      • 31 hour(s) ago, # ^ | ← Rev. 2 →   +3 Suppose you need to evaluate something like Suppose You can expand all and multiply them altogether. You can represent by a vector(say ) of size such that . Basically denotes the coefficient of . Now suppose is the final vector which you get after multiplying all vectors. So your answer is just , where is the size of vector . Here denotes the coefficient of in . Note that is same as the one used in my original comment. You can refer to this submission for implementation details.

• 33 hours ago, # ^ | You can find many proofs on the internet.

• 33 hours ago, # ^ | ← Rev. 3 →   +37 It's pretty well known imo.You can pair up divisors d and n/d. Only way a divisor would by paired with itself is when n is a perfect square.

• 22 hours ago, # ^ | ← Rev. 2 →   0 An alternative proof: A number can be represented by its prime factorisation . Then the number of factors are . This product is odd only in the case when all the terms are odd. That happens only when for all it is the case that is even i.e it is of the form . So we get . There you have your number to be a square.

• 33 hours ago, # ^ | omg errorgorn proof

• 32 hours ago, # ^ | what does it mean, mathforce? i have same problem, cannot see the codes and says not allowed!

• 7 hours ago, # ^ | Besides proof, the other important question is, how did you find it?

  • 4 hours ago, # ^ | ← Rev. 2 →   0 The point is that by some reason the polynomial found is always of degree 2 and once you assume it's of degree 2 it's easy to find it because you know it needs to have roots 0 and k. So you're up to find "a" in ax(x-k) and you can find it with an easy case like x=1.

    • 2 hours ago, # ^ | Oh... You mean if we look at it as a polynomial of N instead of K. Hopefully someone shows up with a proof.

• 25 hours ago, # ^ | Suppose the binary representation of has bits, then the max possible xor sum has bits, whereas has bits.

• 25 hours ago, # ^ | I also struggled a bit to get it, so here's what I understood. You can iteratively compute the prefix XOR for the array and keep track of how many times each value came up before in a table (set t[0] = 1 to account for the empty prefix). For each of the n prefixes you XOR the current target value and check the table for previous prefixes. That works because the XOR between a prefix up to position x and a prefix up to position y represents the XOR on the [x+1, y] subarray, so you end up checking every subarray in O(n).

• 24 hours ago, # ^ | For proving this case, Suppose the number is, n=16, Binary representation of n is = 10000. Now using or | operation among some numbers which always less than or equal to n including this, maximumly we can get all bits set, that is 11111. Which is = 2*n-1.

• 22 hours ago, # ^ | I thought of the same solution. But note that the sieve works in time complexity, instead of the mentioned in your code. Since the rest of the code is , this solution is actually asymptotically better than the one in the editorial.

• 22 hours ago, # ^ | My rule of thumb is if the time limit is less than 1e8 operations than the algorithm is ok.

  • 21 hour(s) ago, # ^ | okkay

• 2 hours ago, # ^ | N^(3/2) being faster than Nlog^2N isn't rare. In the end, it might end up depending on the constant.

• 21 hour(s) ago, # ^ | maximum possible xor is all bits of n becoming 1. 2n will have one extra bit than n which will be greater than all bits of n becoming 1.

• 21 hour(s) ago, # ^ | let's take N = 32 as given in question all the elements will be less then n. Let's assume there is an element 32 and the next element 31 XOR of these elements will be 63 (<2*n) which is the maximum allowed XOR as all the allowed bits are turned on.

• 29 minutes ago, # ^ | You can understand with an example suppose you have n = 56, which means that the value in the array is 1<=a[i]<=56(as mentioned in the question). 56 = 111000 Now the maximum xor sum is 111111 which is 63 when we set all bits with 1. And 63 < 2n. The maximum value is always less than 2n. You can dry-run this with other numbers so you get a clear idea of it.

• 16 hours ago, # ^ | I just thought about the squares as actual squares. You have to kinda start with an assumption, so I’m going to assume we can somehow build an area of all the perfect squares into a rectangle(so the ans would simply be the length times width). If you line up the squares to create a side, one side will be n(n+1)/2. Now a trick I knew was that adding the next odd number will give you the next perfect square. So if we want another n perfect squares, we could add n ones n-1 threes etc… This can be arranged where the nxn square gains an additional length of one and the n-1 gains three etc. We can then add an additional square with side lengths 1 to n to make the side length of each square 2n+1(basically the side of n gains n+1, n-1 gains n-1 + 3 etc). Therefore, it can be computed as (n(n+1)/2 * (2n+1))/3. (Which is the same as n(n+1)(2n+1)/6). Hopefully my explanation is not horrible. My submission with the formula:https://codeforces.com/contest/1731/submission/186917982.

• 9 hours ago, # ^ | Here's how I did it: First, draw 6x6 field on a paper. Notice that the optimal solution is a zig-zag one. And then just write it down: 1 + 2 + 4 + 6 + 9 + 12 + 16 + 20 + 25 + 30 + 36 What can you notice here? I noticed that 1 + 4 + 9 + 16 + 25 + 36 = S2(6) is a sum of squares. Then, what you see in what's left? 2 + 6 + 12 + 20 + 30 I saw this: (1+1) + (4 + 2) + (9 + 3) + (16 + 4) + (25 + 5) = (1 + 4 + 9 + 16 + 25) + (1 + 2 + 3 + 4 + 5) = S2(5) + S1(5) Then, re-wrote total sum: S(6) = S2(6) + S2(5) + S1(5) = 2*S2(5) + 6^2 + S1(5) Remember (or just re-derive if you forgot, it's pretty straight-forward) the formula for S1(n): S1(n) = n(n+1)/2, and S2(n): S2(n) = (n + 3n^2 + 2n^3)/6 Replace 6 -> n, 5 -> (n-1), and you get: S(n) = 2*S2(n-1) + S1(n-1) + n^2 Then, simplify the formula and multiply it by 2022. Here's my submission with the final formula 186941090

#define mx 1000000007

ull n ; cin>>n ;
n = n % mx ;
cout<<((1348*n*n*n)%mx + (1011*n*n)%mx - (337*n)%mx)%mx<<endl;
return 0;

• 18 hours ago, # ^ | 1348*n*n*n overflows before you apply the modulo operation

• 17 hours ago, # ^ | Not able to fix interger overflow I tried using this code to avoid integer overflow but still i am getting error some where in code please help me out

• 16 hours ago, # ^ | ← Rev. 3 →   0 # { (x, y) where gcd (x, y) = d } = # { (x, y) where d|x , d|y } − # { (x, y) where gcd (x, y) > d } = # { (x, y) where d|x , d|y } — sum( # { (x, y) where gcd (x, y) = k*d } where k>=2)

• 56 minutes ago, # ^ | ctn is a variable that stores no. of subarray whose xor sum is a perfect square root. and curr variable is updated to fulfill this equation y = k ^ xor. Where xor is the prefix sum at the i-th position whereas the k is the perfect square roots/

• 9 minutes ago, # ^ | Read the question again. 1<= ai <= n. So in your case, 4 shouldn't be there in the array