Блог пользователя s_jaskaran_s

Автор s_jaskaran_s, история, 22 месяца назад, По-английски

UPD: Code links are working now

1731A - Joey Takes Money

Idea: s_jaskaran_s

Hint
Solution

1731B - Kill Demodogs

Idea: s_jaskaran_s

Hint
Solution

1731C - Even Subarrays

Idea: ka_tri

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

1731D - Valiant's New Map

Idea: s_jaskaran_s

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

1731E - Graph Cost

Idea: s_jaskaran_s

Hint 1
Hint 2
Solution

1731F - Function Sum

Idea: nishkarsh and s_jaskaran_s

Solution
  • Проголосовать: нравится
  • +120
  • Проголосовать: не нравится

»
22 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Thanks for fast editorial.

»
22 месяца назад, # |
  Проголосовать: нравится -29 Проголосовать: не нравится

SuperFast Editorial

»
22 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Multiply by 2022 is just interruption.

»
22 месяца назад, # |
  Проголосовать: нравится +72 Проголосовать: не нравится

Please provide proof that the greedy strategy works in task E

  • »
    »
    22 месяца назад, # ^ |
    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]

  • »
    »
    22 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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

  • »
    »
    22 месяца назад, # ^ |
    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)

  • »
    »
    22 месяца назад, # ^ |
    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:

    $$$property1:$$$ at any step, $$$dp[i]$$$ is a non-decreasing sequence. ($$$dp[i][k-1]$$$ $$$<=$$$ $$$dp[i][k]$$$).

    Proof by Induction

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

    As you notice from second property, transitions show it's optimal to take greatest element whenever we can.

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +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.

»
22 месяца назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Tight Constraints for C, Unordered map gave TLE

»
22 месяца назад, # |
  Проголосовать: нравится 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)6

from problem B .

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 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.

  • »
    »
    22 месяца назад, # ^ |
    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

    • »
      »
      »
      22 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    22 месяца назад, # ^ |
    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

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    wolfram alpha

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 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.me/contest/1731/submission/186917982

»
22 месяца назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +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.

»
22 месяца назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

C just taking the piss bro with the tle

»
22 месяца назад, # |
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.

»
22 месяца назад, # |
  Проголосовать: нравится +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).

»
22 месяца назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

India top ❤❤❤

»
22 месяца назад, # |
  Проголосовать: нравится 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 ?

»
22 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

got TLE in C because of using map instead of array for storing prefix xor
another sad day..

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
22 месяца назад, # |
Rev. 3   Проголосовать: нравится -8 Проголосовать: не нравится

For problem B

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

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

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +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.

»
22 месяца назад, # |
  Проголосовать: нравится 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?

»
22 месяца назад, # |
  Проголосовать: нравится +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) :(

»
22 месяца назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

D was a lot easier than C this contest.

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится -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)

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 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

»
22 месяца назад, # |
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

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +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

»
22 месяца назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

I made video Solutions for A-E.

»
22 месяца назад, # |
  Проголосовать: нравится +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)$$$.

  • »
    »
    22 месяца назад, # ^ |
    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.

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +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)$$$.

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 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.

»
22 месяца назад, # |
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.me/contest/1731/submission/186959618

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 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

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 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.

»
22 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
22 месяца назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
22 месяца назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

.​

»
22 месяца назад, # |
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.

  • »
    »
    22 месяца назад, # ^ |
    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.me/problemset/problem/622/F

    • »
      »
      »
      22 месяца назад, # ^ |
        Проголосовать: нравится 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!

      • »
        »
        »
        »
        22 месяца назад, # ^ |
          Проголосовать: нравится +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.

»
22 месяца назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

mathforces :))

»
22 месяца назад, # |
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
  • »
    »
    22 месяца назад, # ^ |
    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;

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 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} $$$

    • »
      »
      »
      22 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Fixed, thanks

      • »
        »
        »
        »
        22 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          22 месяца назад, # ^ |
          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.

»
22 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Constraints on C were too tight :/

»
22 месяца назад, # |
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

»
22 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

ModuloForces

»
22 месяца назад, # |
  Проголосовать: нравится +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...

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    You can find many proofs on the internet.

  • »
    »
    22 месяца назад, # ^ |
    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.

  • »
    »
    22 месяца назад, # ^ |
    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.

»
22 месяца назад, # |
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.

»
22 месяца назад, # |
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

»
22 месяца назад, # |
  Проголосовать: нравится +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?

»
22 месяца назад, # |
  Проголосовать: нравится +49 Проголосовать: не нравится

Stupid problem F.

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by adedalic (previous revision, new revision, compare).

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by adedalic (previous revision, new revision, compare).

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by adedalic (previous revision, new revision, compare).

»
22 месяца назад, # |
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.me/contest/1731/submission/186979120

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

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

    • »
      »
      »
      22 месяца назад, # ^ |
      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.

      • »
        »
        »
        »
        22 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        Hopefully someone shows up with a proof.

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why is my hash table so slow?

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

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

»
22 месяца назад, # |
  Проголосовать: нравится 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 2n

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

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +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.

»
22 месяца назад, # |
  Проголосовать: нравится 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...

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +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).

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

good contests,but boring problem c

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +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.

»
22 месяца назад, # |
  Проголосовать: нравится 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

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +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.

»
22 месяца назад, # |
  Проголосовать: нравится 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

»
22 месяца назад, # |
  Проголосовать: нравится 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

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится 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

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 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.

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 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.

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 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.me/contest/1731/submission/186917982.

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится 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<<endl;
return 0;
»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    22 месяца назад, # ^ |
    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)

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Can anyone clarify on polynomial interpolation in problem F?

  • »
    »
    22 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    You can start with easy example of polynomial interpolation. This problem — https://codeforces.me/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

»
22 месяца назад, # |
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.

187053184

UPDATE: Never mind I got hacked :)

»
22 месяца назад, # |
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.

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +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

    • »
      »
      »
      22 месяца назад, # ^ |
      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).

»
22 месяца назад, # |
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?

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится 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?

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 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.

    • »
      »
      »
      22 месяца назад, # ^ |
        Проголосовать: нравится +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$$$.

»
22 месяца назад, # |
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

»
22 месяца назад, # |
  Проголосовать: нравится +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,

»
22 месяца назад, # |
  Проголосовать: нравится 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?

»
22 месяца назад, # |
  Проголосовать: нравится +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<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$$$.

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How , What is this can you please explain?

    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Construct the prefix xor array and prepend 0 to it. Then xor of any subsegment in original array is xor of some pair of numbers of the prf xor array. Use FWHT to compute the polynomial f(x) where the coeff of x^a is how many ways can you select two indices i < j s.t. prfxor[i]^prfxor[j] = a. Then simply iterate on a and check if its valid, if it is then add coeff of x^a to ans.

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem Ratings (Difficultly) When?

»
22 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem D A minimum can be calculated in O(1) using sparse tree. Can anyone explain, how?

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

E can be solved in O(n) using mobius and sqrt stuffs. Link

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For problem F, here is a proof for why $$$\deg F(t) \leq 2$$$. This method requires some generating function technology. I may translate the solution to English.