**UPD**: Code links are working now

Idea: s_jaskaran_s

**Hint**

**Solution**

**Code**

Idea: s_jaskaran_s

**Hint**

**Solution**

**Code**

Idea: ka_tri

**Hint 1**

**Hint 2**

**Hint 3**

**Solution**

**Code(C++)**

**Code(Python)**

Idea: s_jaskaran_s

**Hint 1**

**Hint 2**

**Hint 3**

**Solution**

**Code(Prefix Sum)**

**Code(Sparse Table)**

Idea: s_jaskaran_s

**Hint 1**

**Hint 2**

**Solution**

**Code**

Idea: nishkarsh and s_jaskaran_s

**Solution**

**Code**

Thanks for fast editorial.

What did I say wrong?

so quick editorial :) thnx

SuperFast Editorial

Multiply by 2022 is just interruption.

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

LOL, I didn't noticed that 2022 is divisible by 6 and just copy pasted the modular inverse code.

Shit Never really thought about that

OMG I thought 2022 % 6 != 0 so I just multiplied by 1011 / 3, still worked though :)

lol

Yeh!That's was little bit tricky but ultimately it was helpful for increasing the thinking level.Please provide proof that the greedy strategy works in task E

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]

that's not how proofs work.

Um_nik gives a pretty good explanation of this problem https://youtu.be/HrJhgj5pmdE?t=1981

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

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)

Yeah, feel free to down vote me cuz ur bad and don't understand simple math :(

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

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.Tight Constraints for C, Unordered map gave TLE

using a frequency array will work

Can you point out the mistack. I have used map and getting tle. 187515966 Edit: It work with array.

maps take O(logN) for searching a key

But array takes O(1) for retrival of data

Yes, I faced it too. In an attempt to remove tle I ended up with a bunch of WA and RE T_T

You should read neal's blog: Blowing up unordered_map, and how to stop getting hacked on it

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

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)

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

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

from problem B .

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.

Why the sequence 1*2+2*3+...(n－1)*n) is not generating an equation n*(n+1)*(n+2)/3??

just let n=2

ok, i couldn't get this on first sight.

I think problem B was so confusing

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.

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

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;

you need to take mod of (4n-1) and also you inverse of 6 in 3rd and 4th line

can u please give a working code based on my solution. :)

186997927

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?

(1/a) mod m=(a^(m-2)) mod m if m is prime.

Thanks :)

add them

Thx

kami, please tell me how i(i — 1) is Ei^2 — Ei?

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

wolfram alpha

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

Maybe it's just me, but it seemed like the constraints for C were very tight

It's not just you, but at least they did a great job at preventing $$$O(n\sqrt{n}\log{n})$$$.

Yes I had 10 wrong submissions :")

haaa!!! Simple Minded People. I had 16 wrong submissions

can someone please tell me how to solve modulo problems in c++ T-T

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.

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)

You should read "Competitive Programmer's Handbook". You will find lots of basic and essential topics for Competitive Programming.

c ?

C just taking the piss bro with the tle

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.

on problem D,

A sparse table is being used here. I don't know what it is. Any good resource for the same?

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

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

India top ❤❤❤

Why is your rating <1500 and it's showing that you are a legendary grandmaster? Is it some glitch of cf??

It is the Magic of Santa Claus.

magic didn't happened with me XD

cuz u stupid

Its happening to all bro go to your profile you'll be able to magic right of submission button

Lol got it now Hadn't noticed that yet

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 ?

I mean anyone use set to do create table in problem D ?

got TLE in C because of using map instead of array for storing prefix xor

another sad day..

same bro

There's another method for D that uses the largest square submatrix dynamic programming solution and binary search over $$$n$$$.

Method

Solution (using ranges for the binary search part) 186935611

Great solution..

For problem B

can anyone point out the shortcomings in my code? it was not returning the correct answer for n=1000000000

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.

Thank you so much T-T

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?

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.

How to rearrange the left side to anything?

How, what is the formular for $$$\sum_{i = 1}^n{i \cdot i}$$$ ?

(n*(n+1)*(2n+1))/6

Here is one proof: Your text to link here...

Try looking up in OEIS. https://oeis.org/A002412

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

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) :(

D was a lot easier than C this contest.

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)

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.

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

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

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

Oho.. Great. Thank you.. Finally got it

I made video Solutions for A-E.

Congratulations on becoming master.

Congratulations for orange man!

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

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

That's neat! Forgot that we only consider squares.

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

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

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.

Yes that would have been easier.

Can someone explain how we can check for arbitrary side length s if a required square exists?

I think that I solved D with complexity O(nm), am I wrong?.. Solution: 186936631

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

is it me or we can't open the codes?

Hm, I can't see them too

Yes, I am also not able to see the codes.

.

Deleted

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

ascendingly, were:

now, take the difference between each two adjacent values

take the difference between each two adjacent values one more time

I'm sorry, do that one more time :D

we see that the difference is constant, and this happened

the third timewe 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

and plugged in 4 values that I know to construct a system of 4-equations in 4 variables:

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

Why? First, observe why

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

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

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!

If we force the differences to be a sequence like [0, 0, 0, 1] we have this:

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.

it says, "you're not allowed to view the requested page" for codes

mathforces :))

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

fixedhere.CodeActually, 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;

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

Fixed, thanks

Could you explain further how I can use this formula to find the sum of the multiplication of some power terms?

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.

Constraints on C were too tight :/

Great Contest! Learned a lot about inverse modulo :-)

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

Panvel, in problem D, is not part of Mumbai.

ModuloForces

I came up with the pre computation technique as it can be func[1] = 1; func(n) = func(n-1) + i*(i-1) + i*i

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

Given that it is a cornerstone of the whole solution and not some widely known fact it is worth providing a proof...

You can find many proofs on the internet.

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.

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.

I think problem B was a really good greedy problem. Thanks for the fast editorial.

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.

omg errorgorn proof

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

mathforces

what does it mean, mathforce? i have same problem, cannot see the codes and says not allowed!

## 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;

}

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?

Stupid problem F.

Auto comment: topic has been updated by adedalic (previous revision, new revision, compare).Auto comment: topic has been updated by adedalic (previous revision, new revision, compare).Auto comment: topic has been updated by adedalic (previous revision, new revision, compare).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

Besides proof, the other important question is, how did you find it?

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.

Oh... You mean if we look at it as a polynomial of N instead of K.

Hopefully someone shows up with a proof.

Why is my hash table so slow？

(https://codeforces.com/contest/1731/submission/186902410)

Using this code will lead to TLE on problem C, but I think this code should pass.

187084936

Spoiler187085094

SpoilerThank you!

What will be the expected rating of the first 3 questions?

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 2n`

How do we know that the maximum possible XOR sum of any subarray is less than 2n?

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.

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

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

good contests,but boring problem c

In problem-C,why the maximum possible XOR sum of any subarray will be less than 2n?

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.

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

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.

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

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

My rule of thumb is if the time limit is less than 1e8 operations than the algorithm is ok.

okkay

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

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!

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

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.

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.

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.

I am trying to solve -> B. Kill Demodogs, but i am getting wrong output on 4th input

void 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 1000000000

Output 14154 44484 171010650 958928384

How to come up with formulas like in B ? It's confusing

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.

the explanation is good.

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

thanks buddy.

Can anyone please prove this submission? https://codeforces.com/contest/1731/submission/186970125

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.

1348*n*n*n overflows before you apply the modulo operation

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

Can anyone please explain to me the dp formula in problem E? I still didnt get it :(

# { (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)

Is there anywhere where I can learn the 2d RMQ implemented in solution 2 of problem D?

Can anyone clarify on polynomial interpolation in problem F?

You can start with easy example of polynomial interpolation. This problem — https://codeforces.com/contest/622/problem/F

Here 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

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.

187053184

UPDATE: Never mind I got hacked :)

Hey adedalic

Can 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

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/

can anybody help me to understand if a.b=x then why maximum value of a+b=x+1?

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`

.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

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

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!

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

Got it! Thanks

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?

Read the question again. 1<= ai <= n. So in your case, 4 shouldn't be there in the array

In problem B,

for calculating

some guys multiply it by 166666668. instead of dividing by 1/6.n(n+1)(4n-1)/6How it is working and what is the logic behind this?

166666668 is the modular inverse of 6 in mod 1e9 + 7

ohh got it Thanks for this.

Where can I read about "technique of polynomial interpolation" used in this question?

This might help

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

How to solve E using Möbius function? Can anyone provide hints or solution?

Somebody help me?My code WA on test 3,thanks! https://codeforces.com/contest/1731/submission/187155992

Sry,it is out of bounds on

`ll x=min(dp[k+1],m)/k;`

From where can i get code in java for these questions

In problem E how to show that s[k] is non-increasing?

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.

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

Thanks got it

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

It worked. https://codeforces.com/contest/1731/hacks/878656

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,

Has this contest gone unrated? My profile shows 0 change in rating.

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?

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,

mod by n1 (n1 = 1e9 + 7) is taken at many steps. Whereas my code

This gives wrong answer, can anyone help me?

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<b$$$ and are coprime). Thus, for every such pair we can have another pair with GCD $$$g$$$, i.e., ($$$a\cdot g$$$, $$$b\cdot g$$$). Hence, $$$dp[g]\ge dp[g+1]$$$ and $$$s[g]\ge s[g+1]$$$.

Proof that greedily choosing the maximum available group is optimal:

Suppose for some $$$m$$$ the maximum available group we can choose is with gcd $$$g$$$, assume an optimal solution $$$sol$$$ that does not choose $$$g$$$ exists, let's anyway still use a group from $$$g$$$ then proceed in descending order of GCDs making choices like in $$$sol$$$, we will reach some $$$k<g$$$ where choosing one more group of $$$k$$$ will exceed $$$m$$$.

At that moment we must choose at least $$$2$$$ more groups as part of $$$sol$$$, because if only $$$1$$$ group $$$last$$$ ($$$last<g$$$) is remaining for $$$sol$$$, this means that after choosing that group we will have chosen $$$g-1+m$$$ edges, which means that before $$$last$$$ we have chosen $$$g-1+m-(last-1)$$$, which means we already exceeded $$$m$$$ before choosing $$$last$$$, which is a contradiction.

Let's return to $$$k$$$ that we are currently stuck at, since $$$s[i]$$$ is non-increasing, for sure we can choose our last group from some $$$l$$$ ($$$l<k$$$), which means we introduced $$$2$$$ more groups ($$$g$$$ and $$$l$$$) but we removed at least $$$2$$$ other groups, which means solution can't get any worse by choosing $$$g$$$.

C can also be solved in $$$O(n \log n)$$$ using the Walsh-Hadamard transform.

How , What is this can you please explain?

An recursive segment tree might fail (?) for D. But my iterative one surprisingly works. Thanks to modern computer.

Problem Ratings (Difficultly) When?

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<queue< int >>, 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 lot

My GNU C++17 submission

Hello! How to proof that maximum value of

`a + b = x + 1`

in A problem?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......

In Problem 1731B i think In solution code you have to use void instead of int in solve function.

Right, but it doesn't matter

In problem F, what is the name of polynomial interpolation technique did you use in your code, sir?

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]

In problem D

`A minimum can be calculated in O(1) using sparse tree.`

Can anyone explain, how?