By s_jaskaran_s, history, 3 months ago,

UPD: Code links are working now

1731A - Joey Takes Money

Hint
Solution

1731B - Kill Demodogs

Hint
Solution

1731C - Even Subarrays

Idea: ka_tri

Hint 1
Hint 2
Hint 3
Solution
Code(C++)
Code(Python)

1731D - Valiant's New Map

Hint 1
Hint 2
Hint 3
Solution
Code(Prefix Sum)
Code(Sparse Table)

1731E - Graph Cost

Hint 1
Hint 2
Solution

1731F - Function Sum

Solution
• +120

 » 3 months ago, # |   +6 Thanks for fast editorial.
•  » » 3 months ago, # ^ |   +16 What did I say wrong?
 » 3 months ago, # | ← Rev. 2 →   -19 so quick editorial :) thnx
 » 3 months ago, # |   -29 SuperFast Editorial
 » 3 months ago, # |   +8 Multiply by 2022 is just interruption.
•  » » 3 months ago, # ^ |   +127 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
•  » » » 3 months ago, # ^ |   +61 LOL, I didn't noticed that 2022 is divisible by 6 and just copy pasted the modular inverse code.
•  » » » 3 months ago, # ^ |   -7 Shit Never really thought about that
•  » » » 3 months ago, # ^ |   +5 OMG I thought 2022 % 6 != 0 so I just multiplied by 1011 / 3, still worked though :)
•  » » » » 3 months ago, # ^ |   0 lol
•  » » » 3 months ago, # ^ |   0 Yeh! That's was little bit tricky but ultimately it was helpful for increasing the thinking level.
 » 3 months ago, # |   +72 Please provide proof that the greedy strategy works in task E
•  » » 3 months ago, # ^ | ← Rev. 2 →   -88 see it like we have some numbers of each type of grapes from 1 to n but ith type of grapes are in bunch of i-1 and buying ith type grape (bunch of i-1) costs, then how can you buy maximum grapes with limited money. buying bunch of higher number cost less per grape and that's why we will buy it first. [i/(i-1) will be less for higher values of i]
•  » » » 3 months ago, # ^ |   +45 that's not how proofs work.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +10 Um_nik gives a pretty good explanation of this problem https://youtu.be/HrJhgj5pmdE?t=1981
•  » » » 3 months 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
•  » » 3 months ago, # ^ | ← Rev. 2 →   -83 Isn't it kinda obvious? Suppose you have an optimal answer and in that answer you have x edges with gcd x+1 and y edges with gcd y+1. If instead you can get (x+y) edges with gcd x+y+1, you end up with the same number of edges, x+y, and cost x+y+1 < x+y+1+1. Therefore, the greedy leads to a better answer than the optimal one. (notice that you can always add one edge in the end, choosing 2 numbers with gcd 2)
•  » » » 3 months ago, # ^ |   -66 Yeah, feel free to down vote me cuz ur bad and don't understand simple math :(
•  » » 3 months ago, # ^ | ← Rev. 2 →   +28 I will show very simple proof with simulation of $(number$ $of$ $groups)$ * $(m)$ knapsack solution and some properties on the knapsack array that results taking biggiest group everytime is optimal.Let array we're working on $a[]$ = {$1, 2, 3, 3, 4, 4, 4... n$}. where every element denotes an avaible group of size a[i].and our knapsack array will be $dp[i][k]$ denoting subset with minimum size of prefix $i$ with $sum = k$. Transitions:for(i in [1, n]) dp[i] = dp[i-1] for(k in [a[i], m]) dp[i][k] = min(dp[i-1][k-a[i]]+1, dp[i][k]) $property1:$ at any step, $dp[i]$ is a non-decreasing sequence. ($dp[i][k-1]$ $<=$ $dp[i][k]$). Proof by InductionObviously, this property holds for $dp[0]$. At any step it will hold for $k>a[i]$ because they will be minimised by a non-decreasing sequence assuming $dp[i-1]$ was non-decreasing.Now we only need to show $dp[i-1][a[i]-1]$ $<=$ $dp[i][a[i]]$. Which is true because we know at some step $j < i$ step we minimised $dp[i][a[i]-1]$ with $dp[i][0]$ because we visited $a[i]-1$ at some point. and now we are minimising $dp[i][a[i]]$ with $dp[i][0]$.$property 2:$ We don't need minimise operation, we can directly assign $dp[i][k]$ to $dp[i-1][k-a[i]]+1$. Proof by InductionWe know array $dp[i-1]$ is sorted where $a[i-1]$ was either $a[i]$ or $a[i]-1$. So we are going from minimizing $dp[i][k]$ with $dp[i-1][k-a[i-1]]+1$ to minimizing it with either $dp[i-1][k-a[i-1]-1]+1$ or $dp[i-1][k-a[i-1]]+1$ which both are small or equal than $dp[i-1][k-a[i-1]]+1$ because $dp[i-1]$ were sorted so we can directly assign.As you notice from second property, transitions show it's optimal to take greatest element whenever we can.
•  » » 3 months ago, # ^ |   +3 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.
 » 3 months ago, # |   +14 Tight Constraints for C, Unordered map gave TLE
•  » » 3 months ago, # ^ |   +14 using a frequency array will work
•  » » » 3 months ago, # ^ | ← Rev. 5 →   0 Can you point out the mistack. I have used map and getting tle. 187515966 Edit: It work with array.
•  » » » » 3 months ago, # ^ |   0 maps take O(logN) for searching a keyBut array takes O(1) for retrival of data
•  » » 3 months 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
•  » » 3 months ago, # ^ |   -11 You should read neal's blog: Blowing up unordered_map, and how to stop getting hacked on it
•  » » » 3 months ago, # ^ |   +9 Actually, it won't help much in this problem. Even std::map gives TLE (due to the extra $log(n)$ factor) and here is the std::unordered_map (with the splitmix64 custom_hash) solution which gives TLE.
•  » » » » 3 months ago, # ^ |   +3 You are right! I didn't try it and thought that it will pass with the amortized $\mathrm{O}(1)$ operations of the unordered map.
•  » » 3 months ago, # ^ |   0 I have a doubt how o(sqroot of n*n) is working it should give tle as overall complexity is going around 10^11.5 if we include t(number of test cases)
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 It is guaranteed that the sum of n over all test cases does not exceed $2\cdot 10^5$.
•  » » » » 3 months ago, # ^ |   0 even so sum is less than 2⋅10^5. than but in solution editorial we are running in o(sqroot of n*n.We are completely running both loops
 » 3 months ago, # |   0 can someone explain how do you end up deriving this ∑i= 1 n (i⋅i) + ∑i= 1 n−1 (i(i+1)) = n(n+1)(4n−1)6from problem B .
•  » » 3 months ago, # ^ |   0 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.
•  » » » 3 months ago, # ^ |   0 Why the sequence 1*2+2*3+...(n－1)*n) is not generating an equation n*(n+1)*(n+2)/3??
•  » » » » 3 months ago, # ^ |   0 just let n=2
•  » » » » » 3 months ago, # ^ |   +1 ok, i couldn't get this on first sight.
•  » » » » » » 3 months ago, # ^ | ← Rev. 2 →   +2 I think problem B was so confusing
•  » » » » 3 months ago, # ^ |   0 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.
•  » » 3 months 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
•  » » » 3 months ago, # ^ |   0 Why my code is not workingll n; cin>> n;ll ans = ((n*(n+1))%mod*(4*n — 1))%mod;ans = (ans/6);cout<<(ans*2022)%mod << endl; return 0;
•  » » » » 3 months ago, # ^ |   0 you need to take mod of (4n-1) and also you inverse of 6 in 3rd and 4th line
•  » » » » » 3 months ago, # ^ |   0 can u please give a working code based on my solution. :)
•  » » » » » » 3 months ago, # ^ |   0
•  » » » » » » » 3 months ago, # ^ |   0 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?
•  » » » » » » » » 3 months ago, # ^ |   +1 (1/a) mod m=(a^(m-2)) mod m if m is prime.
•  » » » » » » » » » 3 months ago, # ^ |   0 Thanks :)
•  » » 3 months ago, # ^ | ← Rev. 2 →   +22 $∑i^2 = n(n+1)(2n+1)/6$ $∑i(i-1) = ∑i^2 -∑i = n(n+1)(2n+1)/6 -n(n+1)/2$add them
•  » » » 3 months ago, # ^ |   0 Thx
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 kami, please tell me how i(i — 1) is Ei^2 — Ei?
•  » » » » 3 months ago, # ^ |   0 Just open up the brackets: $\sum\limits_{i=1}^{n}{(i^{2}-i)}= \sum\limits_{i=1}^{n}{i^{2}}-\sum\limits_{i=1}^{n}{i}$
•  » » 3 months ago, # ^ |   0 wolfram alpha
•  » » 3 months ago, # ^ |   0 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
 » 3 months ago, # |   +34 Maybe it's just me, but it seemed like the constraints for C were very tight
•  » » 3 months ago, # ^ |   +31 It's not just you, but at least they did a great job at preventing $O(n\sqrt{n}\log{n})$.
•  » » 3 months ago, # ^ |   +1 Yes I had 10 wrong submissions :")
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +5 haaa!!! Simple Minded People. I had 16 wrong submissions
 » 3 months ago, # |   0 can someone please tell me how to solve modulo problems in c++ T-T
•  » » 3 months ago, # ^ |   +8 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.
•  » » 3 months ago, # ^ |   0 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)
•  » » 3 months ago, # ^ |   0 You should read "Competitive Programmer's Handbook". You will find lots of basic and essential topics for Competitive Programming.
 » 3 months ago, # | ← Rev. 2 →   -12 c ?
 » 3 months ago, # |   +17 C just taking the piss bro with the tle
 » 3 months ago, # | ← Rev. 3 →   0 On problem D, there is a 2d segment tree solution (i know it is worse than binary search with 2d prefix sum) which takes O(n⋅m⋅logn⋅logm⋅)). For every (i, j), you only check if you can create square with size bigger than current maximum value and increase maximum while possible. There are at most min(n,m) increases(1000 at max) so it is negligible.
•  » » 3 months ago, # ^ |   0 on problem D,A sparse table is being used here. I don't know what it is. Any good resource for the same?
•  » » 3 months ago, # ^ |   0 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 :)
 » 3 months ago, # |   +7 like seriously? it was just matter of using array instead of map and i could not solve till end bcz i thought it needs to be more optimized than n*sqrt(n).
 » 3 months ago, # |   -11 India top ❤❤❤
•  » » 3 months ago, # ^ |   0 Why is your rating <1500 and it's showing that you are a legendary grandmaster? Is it some glitch of cf??
•  » » » 3 months ago, # ^ |   +1 It is the Magic of Santa Claus.
•  » » » » 3 months ago, # ^ |   -14 magic didn't happened with me XD
•  » » » » » 3 months ago, # ^ |   -6 cuz u stupid
•  » » » » » » 3 months ago, # ^ |   +1 Its happening to all bro go to your profile you'll be able to magic right of submission button
•  » » » » » » » 3 months ago, # ^ |   0 Lol got it now Hadn't noticed that yet
 » 3 months ago, # |   0 In problem D,regard of convert it into 0 and 1 , can we find prefix min and check that smaller than m for each binary search value of m ?
•  » » 3 months ago, # ^ |   0 I mean anyone use set to do create table in problem D ?
 » 3 months ago, # | ← Rev. 2 →   0 got TLE in C because of using map instead of array for storing prefix xor another sad day..
•  » » 3 months ago, # ^ |   +1 same bro
 » 3 months ago, # |   0 There's another method for D that uses the largest square submatrix dynamic programming solution and binary search over $n$.MethodSolution (using ranges for the binary search part) 186935611
•  » » 3 months ago, # ^ |   0 Great solution..
 » 3 months ago, # | ← Rev. 3 →   -8 For problem B #include 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
•  » » 3 months ago, # ^ |   +4 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.
•  » » » 3 months ago, # ^ |   0 Thank you so much T-T
 » 3 months ago, # |   0 How to come up with the right side of this equation after having found the left side?$\sum_{i = 1}^n{i \cdot i} + \sum_{i = 1}^{n-1}{i (i + 1)} = \frac{n(n + 1)(4n - 1)}{6}$Or how to google it?
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 rearrange left side to form 2*i*i + iNow 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.
•  » » » 3 months ago, # ^ |   0 How to rearrange the left side to anything?How, what is the formular for $\sum_{i = 1}^n{i \cdot i}$ ?
•  » » » 3 months ago, # ^ | ← Rev. 7 →   +1 (n*(n+1)*(2n+1))/6Here is one proof: Your text to link here...
•  » » 3 months ago, # ^ |   +5 Try looking up in OEIS. https://oeis.org/A002412
•  » » 3 months ago, # ^ |   0 My intuition here was to look at a ratio between your desired sum and $1+2+...+n$. Then notice a constant increment in this ratio and derive both $\sum{i*i}$ and $\sum{i*(i+1)}$ from there
 » 3 months ago, # |   +20 You played very dirty game with 2022 in problem B, idiot me just can't see it. I went for modular inverse of 6 rather than doing (2022/6) :(
 » 3 months ago, # |   +25 D was a lot easier than C this contest.
•  » » 3 months ago, # ^ |   -18 I disagree with that, honestly I tried to write up a DP solution, failed, and looked at it for 1 hour and a half to no success (I knew I might have needed some data structure but I don't have a template for 2d segtrees)
•  » » » 3 months ago, # ^ |   +11 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.
•  » » 3 months ago, # ^ |   0 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
 » 3 months ago, # | ← Rev. 3 →   +1 Problem C: "Number of subarrays with a given XOR sum can be calculated in O(n)". How this can be solved ?? This line is just put in tutorial without any explanation
•  » » 3 months ago, # ^ |   +6 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
•  » » » 3 months ago, # ^ |   +3 Oho.. Great. Thank you.. Finally got it
 » 3 months ago, # |   +11 I made video Solutions for A-E.
•  » » 3 months ago, # ^ |   +6 Congratulations on becoming master.
•  » » 3 months ago, # ^ |   +6 Congratulations for orange man!
 » 3 months ago, # |   +1 How to solve problem D with sparse table? From custom invocation, the maximum size of a vector with $512$ MB memory limit is just $10^7$, meanwhile the size of sparse table in this problem can even reach $10^8$ (when $n = m = 10^3$, the size is approximately $n \cdot m \cdot log(n) \cdot log(m) \approx 10^8)$.
•  » » 3 months 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 ($>512$ MB) in custom invocation.
•  » » 3 months ago, # ^ |   +22 You can get rid of one $\log$ using the fact that we are interested only in squares. Just let $m[i][j][k]$ be the minimum in square $(i, j) - (i + 2^k, j + 2^k)$.
•  » » » 3 months ago, # ^ |   +1 That's neat! Forgot that we only consider squares.
•  » » 3 months ago, # ^ |   0 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.
 » 3 months ago, # | ← Rev. 2 →   0 Can someone help me know what's wrong in this code..? For ques B, I have used the same formula from which the given formula is derived.. https://codeforces.com/contest/1731/submission/186959618
•  » » 3 months ago, # ^ |   0 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
•  » » 3 months ago, # ^ |   0 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.
•  » » » 3 months ago, # ^ |   0 Yes that would have been easier.
 » 3 months ago, # | ← Rev. 2 →   0 Can someone explain how we can check for arbitrary side length s if a required square exists?
 » 3 months ago, # | ← Rev. 3 →   +3 I think that I solved D with complexity O(nm), am I wrong?.. Solution: 186936631Idea is to solve 1d version of problem: For all elements of a row / column calculate maximum length K of segment starting at it that all numbers inside are >= K.And you just apply that for rows, then apply for columns in a table of results.And this subproblem can be solved with linear min in moving window (with deque).
 » 3 months ago, # |   +6 is it me or we can't open the codes?
•  » » 3 months ago, # ^ |   +3 Hm, I can't see them too
•  » » 3 months ago, # ^ |   0 Yes, I am also not able to see the codes.
 » 3 months ago, # | ← Rev. 2 →   +3 .​
 » 3 months ago, # | ← Rev. 3 →   0 Deleted
 » 3 months ago, # | ← Rev. 4 →   +53 Another solution (with motivation) for B (the solution is not recommended, but the technique used in it may be very useful in other instances):When I looked at the problem, the first thing that popped into my mind is that the solution would be some formula in terms of $n$, because of the constraints. I was too lazy to think.The first thing I tried was some brute force to collect some values. My brute force was classical dynamic programming to find the maximum-sum path in a grid. The values I got for $n \in \{ 2, 3, \dots, 7 \}$ascendingly, were: $\{ 7, 22, 50, 95, 161, 252 \}$now, take the difference between each two adjacent values $\{ 15, 28, 45, 66, 91 \}$take the difference between each two adjacent values one more time $\{ 13, 17, 21, 25 \}$I'm sorry, do that one more time :D $\{ 4, 4, 4 \}$we see that the difference is constant, and this happened the third time we took a difference. From here, we can note that our solution is a polynomial of the third degree. This method is called the method of differences.. Now, what I did in-contest was declare that my answer is $p(x) = ax^3 + bx^2 + cx + d$and plugged in 4 values that I know to construct a system of 4-equations in 4 variables: $p(2) = 7, p(3) = 22, p(4) = 50, p(5) = 95$and then dumbed down the equations on Wolfram-Alpha, and got the values for $a$, $b$, $c$ and $d$, coded it and got AC. But that was too slow.Note that from the values above, and the fact that for any $k + 1$ values $(x_1, y_1), (x_2, y_2), \dots, (x_{k + 1}, y_{k + 1})$, we can know for sure that there exists a unique polynomial of degree $k$ satisfying these values, we can know for sure that $p(x) = \frac{(x-3)(x-4)(x-5)}{(2-3)(2-4)(2-5)} \cdot 7 + \frac{(x-2)(x-4)(x-5)}{(3-2)(3-4)(3-5)} \cdot 22 + \frac{(x-2)(x-3)(x-5)}{(4-2)(4-3)(4-5)} \cdot 50 + \frac{(x-2)(x-3)(x-4)}{(5-2)(5-3)(5-4)} \cdot 95$Why? First, observe why $p(2) = 7, p(3) = 22, p(4) = 50, p(5) = 95$(for example, for $x = 2$, we can note that all fractions except the first one become $0$, and the first fraction becomes $1 \cdot 7$, and so the answer is $7$). Second, observe that $p$ is a polynomial of the third degree, and there can only be one such polynomial satisfying these four values, so it is the polynomial we are looking for :D.This method is called Lagrange Interpolation. And, this was very useful in a problem like this, since we can hard code about 10 values (a guess for a sufficient number of values) for the polynomial, and this code will automatically evaluate the polynomial for you using the same method (just change in the global vector of pairs of $x$ and $y$ values, and everything will be fine). Note that more correct values will not — at-all — harm or corrupt the polynomial.Note that if you plug in $k$ values, both precomputation and evaluation are done in $O(k^2)$, so if $k=10$, we do 100 operations per test case, which is not much.
•  » » 3 months ago, # ^ | ← Rev. 3 →   +3 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
•  » » » 3 months ago, # ^ |   0 I do not quite understand how the method of differences directly concluded the polynomial you have. I mean, I do understand where the coefficients $7, 15, 13,$ and $14$ come from, but I do not understand where $\binom{x}{1}$ and $\binom{x}{2}$ 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!
•  » » » » 3 months ago, # ^ |   +3 If we force the differences to be a sequence like [0, 0, 0, 1] we have this: 0 0 0 1 0 0 1 1 0 1 2 1 1 3 3 1 4 6 4 1 you can prove that each row is a row of the pascal triangle, and we take (X choose difference of columns) as the column is fixed. This works because the resulting sequence depends on all the orders of differences using only the operation +, so it's a sort of a linear system and we can isolate the contribution from each of these positions.
 » 3 months ago, # | ← Rev. 2 →   +6 it says, "you're not allowed to view the requested page" for codes
 » 3 months ago, # |   +2 mathforces :))
 » 3 months ago, # | ← Rev. 2 →   +54 In F, one of the major parts is calculating $\sum_{i=1}^{k} i^p$ for some $p$. Note that here $k$ is fixed.As $p$ is quite less in the problem statement, we can avoid interpolation.So suppose $S(k,p)=\sum_{i=1}^{k} i^p$. Now let's try to expand $(x+1)^{p+1}$.We know that $(x+1)^{p+1} = \sum_{i=0}^{p+1} {{p+1} \choose i} \cdot x^i$.Now it's not hard to observe that $S(k+1,p+1)-1=\sum_{i=0}^{p+1} {{p+1} \choose i} \cdot S(k,i)$$S(k+1,p+1)-1-S(k,p+1)=\sum_{i=0}^{p} {{p+1} \choose i} \cdot S(k,i)$So we get ${{p+1} \choose p} \cdot S(k,p) = (k+1)^{p+1}-1-\sum_{i=0}^{p-1} {{p+1} \choose i} \cdot S(k,i)$Now we know that $S(k,0)=k$.So if we move in increasing order of $p$(from $p=1$ to $n$), we can find $S(k,p)$ for all $p(0 \leq p \leq n)$. Do note that $k$ is fixed here. Code //here track[i] gives S(k_modified,i) track[0]=k_modified; for(ll i=1;i<=n;i++){ track[i]=binpow(k_modified+1,i+1,MOD)+MOD-1; for(ll j=0;j
•  » » 3 months 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;
•  » » 3 months ago, # ^ |   0 There is a small typo here. In the last line of the formula, it should be $\sum_{i = 0}^{p - 1} \binom{p + 1}{i}$ instead of $\sum_{i = 0}^{p} \binom{p + 1}{i}$
•  » » » 3 months ago, # ^ |   0 Fixed, thanks
•  » » » » 3 months ago, # ^ |   0 Could you explain further how I can use this formula to find the sum of the multiplication of some power terms?
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   +3 Suppose you need to evaluate something like $\sum_{x=1}^{k} (x-c_1)^{p_1} \cdot (x-c_2)^{p_2} \ldots (x-c_n) ^{p_n}$Suppose $T=\sum_{x=1}^{k} (x-c_1)^{p_1} \cdot (x-c_2)^{p_2} \ldots (x-c_n) ^{p_n}$You can expand all $(x-c_i)^{p_i}$ and multiply them altogether. You can represent $(x-c_i)^{p_i}$ by a vector(say $vec$) of size $p_i+1$ such that $vec[j]={p_i \choose j} \cdot (-c_i)^{p_i-j}$. Basically $vec[j]$ denotes the coefficient of $x_j$. Now suppose $poly$ is the final vector which you get after multiplying all vectors. So your answer is just $\sum_{i=0}^{len} poly[i] \cdot track[i]$, where $len+1$ is the size of vector $poly$. Here $poly[i]$ denotes the coefficient of $x^i$ in $T$.Note that $track$ is same as the one used in my original comment.You can refer to this submission for implementation details.
 » 3 months ago, # |   +6 Constraints on C were too tight :/
 » 3 months ago, # |   0 Great Contest! Learned a lot about inverse modulo :-)
 » 3 months ago, # | ← Rev. 2 →   0 Are you saying that n*m*log(min(n,m)) does not work in D? Well, in principle, yes, but then how does n*m*log(max work (from the entire table))? Isn't it the same thing in the worst case? I'm sorry if I don't understand something, maybe I'm stupid, correct me, here are 2 of my codes. Sorry for the template :) 186931737 186933967
 » 3 months ago, # |   +6 Panvel, in problem D, is not part of Mumbai.
 » 3 months ago, # |   0 ModuloForces
 » 3 months ago, # |   0 I came up with the pre computation technique as it can be func[1] = 1; func(n) = func(n-1) + i*(i-1) + i*ibut the problem is the size of any data structures can't exceed 10^7-10^8 and the TLE is also a problem . if anyone got it fix it ..
 » 3 months ago, # |   +8 A number has an odd number of divisors only if it is a perfect square. Given that it is a cornerstone of the whole solution and not some widely known fact it is worth providing a proof...
•  » » 3 months ago, # ^ |   +11 You can find many proofs on the internet.
•  » » 3 months ago, # ^ | ← Rev. 3 →   +40 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.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +3 An alternative proof: A number can be represented by its prime factorisation $x = {p_1}^{a_1} {p_2}^{a_2} ... {p_n}^{a_n}$. Then the number of factors are $(a_1 + 1)(a_2 + 1)...(a_n + 1)$. This product is odd only in the case when all the terms are odd. That happens only when for all $i$ it is the case that $a_i$ is even i.e it is of the form $a_i = 2 k_i$ . So we get $x = {p_1}^{2k_1} {p_2}^{2k_2} ... {p_n}^{2k_n}$. There you have your number to be a square.
 » 3 months ago, # |   0 I think problem B was a really good greedy problem. Thanks for the fast editorial.
 » 3 months ago, # | ← Rev. 3 →   +90 Why is the proof in the editorial of B so long and complicated?Here is a simpler proof.Label each cell $(i,j)$ by number $i+j$. We will walk on each cell of label $2$ to $2n$ exactly once. For a fixed label $L$, the maximum value is $(L-x)(x)$, this value is maximized when $x$ is closest to $\frac{L}{2}$. This gives us an upper bound on our answer as $\sum\limits_{L=2}^{2n} (L-\lfloor \frac{L}{2} \rfloor)(\lfloor \frac{L}{2} \rfloor)$. This upper bound is also achieved by our construction.
•  » » 3 months ago, # ^ |   +16 omg errorgorn proof
 » 3 months ago, # | ← Rev. 2 →   +3 For some reason, when I click on editorial submission link, it says "You are not allowed to view the requested page". Is that a bug or something?Edit: Its fixed now, Thanks adedalic for fixing it
 » 3 months ago, # | ← Rev. 2 →   -7 mathforces
•  » » 3 months ago, # ^ |   0 what does it mean, mathforce? i have same problem, cannot see the codes and says not allowed!
»
3 months ago, # |
+8

# include <bits/stdc++.h>

using namespace std;

long long fun(int n){ long long ans = 337; int temp = 1e9+7; ans = (ans*(n*(n+1)%temp))%temp; ans = (ans*((4*n-1)%temp))%temp;

return ans;

}

int main() { int n, t; cin>>t; while(t--){ cin>>n; cout<<fun(n)<<endl; } }

This is my code for B. It gives incorrect answer only for n = 1e9. What's wrong?

 » 3 months ago, # |   +49 Stupid problem F.
 » 3 months ago, # |   0 Auto comment: topic has been updated by adedalic (previous revision, new revision, compare).
 » 3 months ago, # |   0 Auto comment: topic has been updated by adedalic (previous revision, new revision, compare).
 » 3 months ago, # |   0 Auto comment: topic has been updated by adedalic (previous revision, new revision, compare).
 » 3 months ago, # | ← Rev. 4 →   +74 Found a closed formula for F but I didn’t prove it: answer = ((N-1)K^N -NK^{N-1}+1)K(K+1)/(6(K-1)) Here's an AC using that: https://codeforces.com/contest/1731/submission/186979120
•  » » 3 months ago, # ^ |   +21 Besides proof, the other important question is, how did you find it?
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +8 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.
•  » » » » 3 months ago, # ^ |   0 Oh... You mean if we look at it as a polynomial of N instead of K.Hopefully someone shows up with a proof.
 » 3 months ago, # |   0 Why is my hash table so slow？Using this code will lead to TLE on problem C, but I think this code should pass.
•  » » 3 months ago, # ^ | ← Rev. 4 →   0 187084936 Spoiler187085094 Spoiler
•  » » » 3 months ago, # ^ |   0 Thank you!
 » 3 months ago, # |   0 What will be the expected rating of the first 3 questions?
 » 3 months ago, # |   0 For Question C, the solution states this:For the given constraints for elements in the array, the maximum possible XOR sum of any subarray will be less than 2nHow do we know that the maximum possible XOR sum of any subarray is less than 2n?
•  » » 3 months ago, # ^ |   +1 Suppose the binary representation of $n$ has $k$ bits, then the max possible xor sum has $k$ bits, whereas $2\cdot n$ has $k + 1$ bits.
 » 3 months ago, # |   0 So,in problem C,why could we calculate the number of subarrays with a given XOR sum with o(n)?I don't know how I can figure it out in such a low complexity...
•  » » 3 months ago, # ^ |   +1 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).
 » 3 months ago, # |   0 good contests,but boring problem c
 » 3 months ago, # |   0 In problem-C,why the maximum possible XOR sum of any subarray will be less than 2n?
•  » » 3 months ago, # ^ |   +7 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.
 » 3 months ago, # |   0 In E, there is one more way to calculate the dp, using euler totient (phi) function, first calculate the normal euler totient function in sieve manner for the given n and storing it in array phi. Now observe that by definition prefix sum on phi[i], would store all pairs (x,y) less than i, such that gcd(x,y)=1. Now if gcd(x,y) = k, then gcd(x/k, y/k)=1, thus to find all pairs less than n whose gcd is k, it is simply phi_prefix[n/k], and since prefix array is non-decreasing, hence we can observe that this value would be non-increasing. Rest of the approach is now same as solution, following greedy approach due to monotone nature of packets array (s[i]>=s[i+1]). Implementation
•  » » 3 months ago, # ^ |   +3 I thought of the same solution. But note that the sieve works in $O(nloglogn)$ time complexity, instead of the $O(nlogn)$ mentioned in your code. Since the rest of the code is $O(n)$, this solution is actually asymptotically better than the one in the editorial.
 » 3 months ago, # |   0 In problem C, I don't understand, why it is enough to canculate only prefix xors and pair them with all perfect squares to check if their xor is less than 2n
 » 3 months ago, # |   0 Can anybody tell me how O((n^3/2)*T) works in problem C? I am always confused about what extent the time is in the acceptable range; O (N log N) or O(N(log N)^2) is pretty understandable that it would work, but n^3/2 seems a bit more
•  » » 3 months ago, # ^ |   0 My rule of thumb is if the time limit is less than 1e8 operations than the algorithm is ok.
•  » » » 3 months ago, # ^ |   0 okkay
•  » » 3 months ago, # ^ |   0 N^(3/2) being faster than Nlog^2N isn't rare. In the end, it might end up depending on the constant.
•  » » » 3 months ago, # ^ |   0 Oh! I wasn't aware earlier that N^3/2 can also be fast compared to N(logN)^2. Thanks for the clarification will keep that in mind!
 » 3 months ago, # |   0 in problem c, why is it : For the given constraints for elements in the array, the maximum possible XOR sum of any subarray will be less than 2n, explain please
•  » » 3 months ago, # ^ |   0 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.
•  » » 3 months ago, # ^ |   0 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.
•  » » 3 months ago, # ^ |   0 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 = 111000Now 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.
 » 3 months ago, # |   0 I am trying to solve -> B. Kill Demodogs, but i am getting wrong output on 4th inputvoid solve(){ ll n; cin>>n; int ans=3; for(int i=2;i<=n;i++){ ans+=i*i; if(i!=n) ans+=(i*i)+i; } cout<<(2022*ans)%n1; }Input 4 2 3 50 1000000000Output 14154 44484 171010650 958928384
 » 3 months ago, # |   0 How to come up with formulas like in B ? It's confusing
•  » » 3 months ago, # ^ |   0 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.
•  » » » 3 months ago, # ^ |   0 the explanation is good.
•  » » 3 months ago, # ^ |   0 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 + 30I 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)/6Replace 6 -> n, 5 -> (n-1), and you get: S(n) = 2*S2(n-1) + S1(n-1) + n^2Then, simplify the formula and multiply it by 2022. Here's my submission with the final formula 186941090
•  » » » 3 months ago, # ^ |   0 thanks buddy.
 » 3 months ago, # |   0 Can anyone please prove this submission? https://codeforces.com/contest/1731/submission/186970125
 » 3 months ago, # |   0 I wrote this code for 1731B but still on the last testcase when n = 10e9 I am not getting a correct answer Can somebody help me what i did wrong. #define mx 1000000007 ull n ; cin>>n ; n = n % mx ; cout<<((1348*n*n*n)%mx + (1011*n*n)%mx - (337*n)%mx)%mx<
•  » » 3 months ago, # ^ |   0 1348*n*n*n overflows before you apply the modulo operation
•  » » 3 months ago, # ^ |   0 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
 » 3 months ago, # |   0 Can anyone please explain to me the dp formula in problem E? I still didnt get it :(
•  » » 3 months 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)
 » 3 months ago, # |   0 Is there anywhere where I can learn the 2d RMQ implemented in solution 2 of problem D?
 » 3 months ago, # |   +3 Can anyone clarify on polynomial interpolation in problem F?
•  » » 3 months ago, # ^ | ← Rev. 2 →   +3 You can start with easy example of polynomial interpolation. This problem — https://codeforces.com/contest/622/problem/FHere we have to find $1^k + 2^k + 3^k + ... + n^k$ where $n$ is large but $k$ is small. Now you know that for $k = 1$ this value is a 2-degree polynomial in $n$ (specifically $n * (n + 1) / 2)$. For $k = 2$ it is a 3 degree polynomial and so on. So we know that the answer is a $k+1$ degree polynomial in $n$. We find the values of this polynomial at $k+2$ different points using brute-force and then interpolate to find the value at $n$.Similarly in problem F, you can infer that the final answer is a $n+2$ degree polynomial and then do the same
 » 3 months ago, # | ← Rev. 3 →   +3 On Problem D, using only Binary search and clever optimizations in the check function could get you an Accepted. I was surprised when this worked.187053184UPDATE: Never mind I got hacked :)
 » 3 months ago, # |   0 Hey adedalicCan anyone explain me in detail exactly why we are updating the cnt in Question C . I am not getting the logic behind the updation of cnt variable . This part [link](https://codeforces.com/contest/1731/submission/186975655#:~:text=%5Bcurr%5D%2B%2B%3B-,for%20(int%20j%20%3D%200%3B%20j%20%3C%20n%3B,%7D,-ll%20ans%20%3D)Thanks in advance
•  » » 3 months ago, # ^ |   0 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/
 » 3 months ago, # | ← Rev. 2 →   0 can anybody help me to understand if a.b=x then why maximum value of a+b=x+1?
 » 3 months ago, # | ← Rev. 3 →   0 s_jaskaran_s nishkarsh could you elaborate a little bit on "be a polynomial whose degree will be <= n+2" in the editorial to problem F because I am getting the degree for the polynomial as n.
•  » » 3 months ago, # ^ |   +3 Actually the degree is n + 1, so you will need n + 2 points to interpolate, the polynomial F is an n degree polynomial as you found, but the polynomial P(u) is an n + 1 degree polynomial of u. this is explained here
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 Yeah, I got it. Thanks!! I wasn't merging the terms of the P(u). I was only looking at the individual terms of F(t).
 » 3 months ago, # |   0 My code keeps on giving runtime error on test 13 for the problem D. Here is my code https://codeforces.com/contest/1731/submission/187076290 Please help me!
•  » » 3 months ago, # ^ |   0 Your code will fail for matrix of size 1 * 1. Because it will call check function with mid = 0 because of which there will be out of bounds array access in the statement ll sum = psum[i][j] — a1 — a2 + s; since i and j would be -1
•  » » » 3 months ago, # ^ |   0 Got it! Thanks
 » 3 months ago, # | ← Rev. 2 →   0 I do not understand these lines from the editorial of the C problem. For the given constraints for elements in the array, the maximum possible XOR sum of any subarray will be less than 2n, so the number of possible elements with odd divisors ≤2n−−√. Number of subarrays with a given XOR sum can be calculated in O(n). suppose we have array [2, 4] then their xor is 6 which is greater then 2*n(i.e 4)Can anyone give example to understand me myself better?
•  » » 3 months ago, # ^ |   +1 Read the question again. 1<= ai <= n. So in your case, 4 shouldn't be there in the array
 » 3 months ago, # |   0 In problem B,for calculating n(n+1)(4n-1)/6 some guys multiply it by 166666668. instead of dividing by 1/6.How it is working and what is the logic behind this?
•  » » 3 months ago, # ^ |   0 166666668 is the modular inverse of 6 in mod 1e9 + 7
•  » » » 3 months ago, # ^ |   0 ohh got it Thanks for this.
 » 3 months ago, # |   0 Where can I read about "technique of polynomial interpolation" used in this question?
•  » » 3 months ago, # ^ |   0 This might help
 » 3 months ago, # |   0 Can someone help me with the proof of problem B. How $\\ \sum_{i=1}^{n}i^2 + \sum_{i=1}^{n-1}{i(i+1)} = \frac{n(n+1)(4n-1)}{6}$ $\$ I know that $\sum_{i=1}^{n}i^2 = \frac{n(n+1)(2n+1)}{6}$ and $\sum_{i=1}^{n-1}{i(i+1)} = \frac{(n-1)(2+n(n-1)}{2}$ but when I combined them I had $n(5n^2-3n+10)-6$
 » 3 months ago, # |   0 How to solve E using Möbius function? Can anyone provide hints or solution?
 » 3 months ago, # |   0 Somebody help me?My code WA on test 3,thanks! https://codeforces.com/contest/1731/submission/187155992
•  » » 3 months ago, # ^ |   0 Sry,it is out of bounds on ll x=min(dp[k+1],m)/k;
 » 3 months ago, # |   0 From where can i get code in java for these questions
 » 3 months ago, # |   +3 In problem E how to show that s[k] is non-increasing?
•  » » 3 months ago, # ^ |   0 I have the exact same question. If you read this explanation here which uses totient function, it is obvious why it should be non-increasing. The dp[k] array which we initially create itself is non-increasing. But if you use the dp approach mentioned in the editorial (and not prefix-sum of totient function), I don't know how people figured it out. It would be great if someone could provide more intuition into this.
•  » » » 3 months ago, # ^ |   +6 Look at any pair $(x, y)$ ($1 \le x, y \le n$) with $\gcd(x, y) = g > 1$. It means we can write them as $x = g x'$ and $y = g y'$ with $\gcd(x', y') = 1$. Now let's make another pair $(x'', y'')$ where $x'' = (g - 1)x'$ and $y'' = (g - 1)y'$. Obviously $1 \le x'', y'' \le n$ and $\gcd(x'', y'') = g - 1$.In other words, from any pair $(x, y)$ with $\gcd(x, y) = g$ we induce a valid pair $(x'', y'')$ with $\gcd(x'', y'') = g - 1$. So, the number of pairs with $\gcd = g - 1$ is greater or equal to the number of pairs with $gcd = g$.
•  » » » 3 months ago, # ^ |   0 Thanks got it
 » 3 months ago, # | ← Rev. 2 →   +10 Current (unofficial) Rank 1: ttklwxx's submission fails on Ticket 16619 from CF Stress. Can someone hack it for me, or let me know if I constructed an invalid testcase? Thanks.Submission Link
•  » » 3 months ago, # ^ |   0
 » 3 months ago, # |   +8 In F, I think max degree of polynomial P(u) is n+1 instead of n+2 which is mentioned in the editorial. As by this article's first theorem under generalisation, $\sum_{k=1}^n k^a$ is a polynomial of degree a+1 and since the max degree of t is n so max deg(P(u)) = n+1.Ps: In the given solution I just replaced n+3 by n+2 and this solution also passed,
 » 3 months ago, # |   0 Has this contest gone unrated? My profile shows 0 change in rating.
 » 3 months ago, # |   0 In problem F shouldn't the degree of P(u) <= n, I can't understand why it is <= n+2, can someone explain it please?
 » 3 months ago, # | ← Rev. 5 →   0 In 1731B - Kill Demodogs, it is mentioned that(Note, you firstly multiply by 2022 and only after that take the remainder.)But in the solution 186975620 provided,  ll ans=((((n*(n+1))%n1)*(4*n-1))%n1*337)%n1; mod by n1 (n1 = 1e9 + 7) is taken at many steps. Whereas my code while(t--){ long long n; cin >> n; cout << (337 * n * (n+1) * (4*n-1)) % N << endl; } This gives wrong answer, can anyone help me?
 » 3 months ago, # |   +1 Full proof for $E$:Throughout the proof, will use the notations used by the editorial, i.e., $dp[i]=$ number of pairs with GCD $i$, $s[i]=$ maximum number of groups of $(i-1)$ edges where each edge has a weight $i$.Proof that $dp[i]$ and $s[i]$ are non-increasing:Any pair with GCD $g+1$ can be represented as ($a\cdot (g+1)$, $b\cdot (g+1)$) ($a  » 3 months ago, # | 0 C can also be solved in$O(n \log n)\$ using the Walsh-Hadamard transform.
•  » » 3 months ago, # ^ |   0 How , What is this can you please explain?
 » 3 months ago, # | ← Rev. 2 →   0 An recursive segment tree might fail (?) for D. But my iterative one surprisingly works. Thanks to modern computer.
 » 3 months ago, # |   0 Problem Ratings (Difficultly) When?
 » 3 months ago, # |   0 Please help me about this problem , I really want to learn the reason:My Question about memory limit on Problem D. I make a vector>, which for test case#13, is 1*1000000. so means 4 million byte, or 4MB around. why does it go above 256MB?? what is the mystery here? Thanks a lotMy GNU C++17 submission
 » 3 months ago, # | ← Rev. 2 →   0 Hello! How to proof that maximum value of a + b = x + 1 in A problem?
 » 3 months ago, # |   0 In problem c why are we doing curxor till i xor with all perfect square ... I i know that x^x = 0 so if there will be any perfect square that will be cancel out and other part will be left as given in code cnt += m[curr ^ (i * i)]; what is this cur^ (i*i) acutally giving......
 » 3 months ago, # | ← Rev. 2 →   0 In Problem 1731B i think In solution code you have to use void instead of int in solve function.
•  » » 3 months ago, # ^ |   0 Right, but it doesn't matter
 » 2 months ago, # |   0 In problem F, what is the name of polynomial interpolation technique did you use in your code, sir?
 » 2 months ago, # |   0 For problem C, can you help me by informing what is the reason behind TLE if we use unordered_map?unordered_map: 190264192 [TLE]vector as map: 190264312 [AC]
 » 2 months ago, # |   0 In problem D A minimum can be calculated in O(1) using sparse tree. Can anyone explain, how?