NemanjaSo2005's blog

By NemanjaSo2005, history, 3 months ago, In English

1900A - Cover in Water

Author: NemanjaSo2005

Hint 1
Hint 2
Solution
Bonus

1900B - Laura and Operations

Author: NemanjaSo2005

Hint 1
Hint 2
Hint 3
Hint 4
Solution
Bonus

1900C - Anji's Binary Tree

Author: Riblji_Keksic

Hint 1
Hint 2
Hint 3
Hint 4
Solution
Bonus

1900D - Small GCD

Author:NemanjaSo2005

Hint 1
Hint 2
Solution part 1
Hint 3
The rest of the solution
Bonus

1900E - Transitive Graph

Author:NemanjaSo2005

Hint 1
Hint 2
Hint 3
Solution
Bonus

1900F - Local Deletions

Author: NemanjaSo2005

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution
Bonus
  • Vote: I like it
  • +103
  • Vote: I do not like it

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

Problem B could be solved with XOR's as well. Here's a somewhat related problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=1232

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

    can you please provide me the solution method you are discussing about!!

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

I solved B using DP 234444052

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

    Hats off to you to waste your time hhhh

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

      I couldn't find the easier solution and I immediately noticed DP :skull:

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

Nice problems, I liked the contest. I had a different solution (which generalises to harder versions easily) for D though.

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

    Typo: you are writing a solution for problem D.

    Great solution though :)

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

    Nice solution (for D though)! Thank you!

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

      Oh yes @boboge, @Megalovania sorry about that, I was only using 2 brain cells last night. lol

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

    Wow hey your solution was the same as mine, I stored $$$\varPhi(d) * counts\ of\ multiples\ of\ d$$$ instead of counts only tho. Nice solution anyways!!!

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

      Can you please please explain me what does phi (N) means ?

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

        It is Euler's totient function. $$$\varphi(N)$$$ returns the number of positive integers $$$n\le N$$$ such that $$$n$$$ and $$$N$$$ are coprime, ie, have $$$\gcd(n,\,N)=1$$$.

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

          Can you please explain how does that helps here ?

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

            Well @NovusStellachan's explaination of the use of Euler's totient function is quite clear, can you explicitly state what you don't get about it?

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

              I am not able to understand how phi is helping us to calculate the answer

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

                If we sort the array then for each i, the answer get increased by an amount of:

                $$$(n-i)*\sum\limits_{j<i}gcd(a_i,a_j)$$$

                Calculating gcd for every pair (i,j) would result in a complexity of $$$O(n^2)$$$ so we need to efficiently calculate them

                Since

                $$$\sum\limits_{d|n}\varPhi(d) = n$$$

                Therefore

                $$$\sum\limits_{d|gcd(a_i,a_j)}\varPhi(d) = gcd(a_i,a_j)$$$

                Plug that into the fist expression and we got

                $$$(n-i)*\sum\limits_{j<i}gcd(a_i,a_j)= (n-i)*\sum\limits_{j<i}\sum\limits_{d|gcd(a_i,a_j)}\varPhi(d)$$$

                What does this mean? It means that we can iterate through all divisors $d$ of $$$a_i$$$, count how many multiples of d which have appeared, then add $$$count * \varPhi(d)$$$ to the sum of gcd, afterwards add $$$(n - i) * gcdsum$$$ to the answer.

                $$$\Phi$$$ can be precomputed and the simplest way of iterating through divisors of n have $$$O(\sqrt{n})$$$ complexity. We therefore achieve an overall complexity of $$$O(n\sqrt{MAX})$$$ in worst case scenarios which is enough to AC.

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

                  Thanks for the explaination sir

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

                  How do you type the math symbols so easily? Is it something built-in on CF or can I just do that everywhere with a specific keyboard settings? If so, how?

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

                  CF comments and posts have built-in Latex :D

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

    This is great. With your generalization, i could understand D more. (You should write D's solution laughs)

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

thanks for the tutorial with hints problem E was one of the best problems i have seen live in a contest

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

Great editorial ! It is always appreciated to have hint based editorials.

Btw I might have been a bit rash in my feedback. Considering the amount of solves by div2 contestants, E made the job a div2 E should do (also, the bonus task looks super cool!!). Also, after thinking a bit more about it, I think it's not that bad to have a div2 C which isn't adhoc as it gives all contestants the opportunity to solve "algorithmic" problems and not "1-observation" problems. I'm interested in others advice

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

really enjoyed the round, THANKS. Looking forward to more from you!!

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

I'm facing a problem with solving problems with number theory tags and focused on GCD, can I have a resource to learn from so I can pass this kind of problems faster please?

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

    Not really a resource but all you really need is prime decomposition of a number, the gcd trick used in D, the fact that numbers usually have up to O(m^1/3) divisors, the number of prime divisors is logarithmic, seeve, √N factoring. You can learn those by either looking it up, or solving number theory on codeforces/other platform.

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

bruh why is D so tough. Can someone simplify please..

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

    We assumed that trick with subtracting higher multiples was quite well known. Also, predicted raiting for D is 1900, which is not that much for a D.

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

I had a slightly different solution for D. I iterated over i from 1 to maxi in order to compute x[i] (which is defined in the editorial). To compute each individual x[i], I had a list of indices of numbers in the sorted array divisible by i and I started from the third element in this list all the way to the last element. Something interesting is that if you pick some value for C with an index in the interval (x, y] in the sorted array where x and y are the indices of 2 multiples of i with no multiples of i between them with an index in that interval, then the number of possible choices for a and b such that both are divisible by i will always be the same. So you can iterate through the list of indices of multiples of i and get the #of ways to pick A and B and multiply this by the length of the current interval that tells us the #of ways to pick C. A nice implementation trick is to add the index n-1 to the end of every list of indices of multiples in order to catch all possible values of C for all x[i]. Once you've computed that, the rest of my solution is the same.

234519989

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

Can someone help me understand the solution to Problem D? I have been trying to understand the solution for a bit but I just can't understand it at all. Can someone give a simpler explanation because my brain just can't understand the solution for whatever reason?

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

    Can provide a simple solution.

    I am not a native English speaker and I use translation software. If you have any translation questions, please feel free to reply to me :)

    The first step, as in the solution, is to find all divisors of all numbers in the range in $$$mlogm$$$ time, which can be preprocessed and stored through $$$10^5$$$ vectors. Note that this step precedes multiple rounds of testing. The second step is to sort the input array and enumerate $$$a_i$$$ from small to large as $$$b$$$, then $$$c$$$ can be selected arbitrarily after $$$b$$$, so the original problem can be converted into $$$\sum_{i=1 }^n\left((n-i)\sum_{j=1}^{i-1}\gcd(a_j,a_i)\right)$$$. That is, we now need to quickly find $$$\sum_{j=1}^{i-1}\gcd(a_j,a_i)$$$ for each $$$i$$$.

    The third step is to find that when $$$a_i$$$ is fixed, the result of $$$\gcd(a_j,a_i)$$$ must be a divisor of $$$a_i$$$. So enumerate all the factors $$$d$$$ of $$$a_i$$$ from large to small, try to check how many $$$a_j$$$ are multiples of $$$d$$$, and $$$d=\gcd(a_j,a_i)$$$, multiply this number by $$$ d$$$ , then add it to the answer.

    More specifically, we have an array $$$cnt$$$ in the range. $$$cnt_d$$$ represents how many numbers in $$$a_1$$$ to $$$a_{i-1}$$$ are multiples of $$$d$$$. Since it has been sorted, this Arrays can be maintained simply by enumerating factors during previous traversals.

    The following work will be better understood through an example. Consider the following sequence $$$2\ 3\ 6\ 7$$$. At this time, $$$i=3$$$, then $$$cnt_1=2$$$ (including $$$2$$$ and $$$3$$$), $$$cnt_2=1$$$ (including $$$2$$$) have been maintained. $$$cnt_3=1$$$ (including $$$3$$$). We enumerate the factors $$$d$$$ of $$$6$$$ from largest to smallest:

    When $$$d=6$$$, $$$cnt_6=0$$$, we do nothing.

    When $$$d=3$$$, $$$cnt_3=1$$$, which means that among the previous numbers, there is a number that is a multiple of $$$3$$$. Although we do not know who it is (in fact, it is $$$3$$$), because we Enumerate $$$d$$$ from large to small. At this time, $$$d=3$$$ must be the $$$\gcd$$$ of that number (in fact, it is $$$3$$$) and $$$a_i$$$ (although this is not actually completely correct, we will ensure the correctness of this soon) , we do $$$ans+=d*cnt_d$$$. And because the numbers in $$$cnt_d$$$ must also be in $$$cnt$$$ of all factors of $$$d$$$, and we only want these numbers to be counted in $$$d$$$, so we need to traverse all the factors of $$$d$$$ $$$d ^{'}$$$, do $$$cnt_{d^{'}}-=cnt_d$$$, thus ensuring correctness. In this example, we did $$$ans+=3\times1$$$, then traversed $$$1$$$ and $$$3$$$, and did $$$cnt_1-=cnt_3$$$ and $$$cnt_3-=cnt_3$$$, thus successfully converting the calculated $$$3 $$$ is removed from $$$cnt_1$$$ and $$$cnt_3$$$.

    When $$$d=2$$$, $$$cnt_2=1$$$, we do $$$ans+=1\times2$$$, $$$cnt_1-=cnt_2$$$ and $$$cnt_2-=cnt_2$$$.

    When $$$d=1$$$, we will find that $$$cnt_1$$$ has been reduced from $$$2$$$ at the beginning to $$$0$$$, so we do nothing

    Finally, we undo all modifications made during this process, i.e. restore $$$cnt$$$ to $$$cnt_1=2$$$, $$$cnt_2=1$$$, $$$cnt_3=1$$$. This can be achieved by creating a $$$\log$$$ sized backup of $$$cnt$$$ before calculating

    Note that the number of divisors of a number in the int range does not exceed $$$1600$$$ at most, and the amortized number should be $$$\log$$$ level, so the complexity is not a problem

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

      Why does cnt[1] also need statistics? From back to front, why do we need to subtract the factor of d? What will be the impact if we don’t subtract it? Do you have any examples?

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

        For your first question, $$$cnt_1$$$ certainly needs to be counted. Because there is a case $$$\gcd(a_j,a_i)=1$$$, they need to be added to the answer. I'm confused by this question and I'm not sure I fully understand your first question.

        For your second question, I can provide further explanation.

        Still based on the premise that $$$a$$$ has been sorted.

        For example, the current situation is $$$i=9$$$, $$$a_9=18$$$, and its factors are $$${18,9,6,3,2,1}$$$.

        Suppose we had $$$a_7=12$$$ before, and its factors are $$${12,6,4,3,2,1}$$$.

        Obviously, $$$\gcd(a_7,a_9)=6$$$, this $$$6$$$ should be part of $$$\sum_{j=1}^{i-1}\gcd(a_j,a_i)$$$ when $$$i=9$$$.

        So now we want $$$\gcd(a_7,a_9)$$$ to be evaluated, and only once, when enumerating up to a factor $$$6$$$ of $$$a_9$$$.

        By the way, we need to make it clear that $$$a_i$$$ is added to $$$cnt$$$ after calculating $$$\sum_{j=1}^{i-1}\gcd(a_j,a_i)$$$. This is very important.

        According to the definition of $$$cnt_d$$$, $$$cnt_6$$$ definitely includes $$$a_7$$$, but does not include $$$a_9$$$. When I traverse the factors of $$$a_9$$$ from large to small, $$$a_7$$$ will enumerate to $$$cnt_6$$$ is considered and calculated correctly, but if we do nothing, $$$a_7$$$ will be calculated again at $$$cnt_3$$$, $$$cnt_2$$$ and $$$cnt_1$$$. That is, if we do nothing, $$$a_j$$$ and $$$a_i$$$ will be evaluated at all divisors of $$$\gcd(a_j,a_i)$$$, which is obviously wrong.

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

        Sorry for still using translation software. Translating from Chinese to English is too easy to cause ambiguity. If you have any questions, please continue to ask :)

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

        The purpose of enumerating the divisors from large to small is to traverse to the "largest" common divisor.

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

          There seems to be something wrong with the translation of this sentence, if you are confused about it just ignore it :(

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

      As for the first question I raised, I misread it, and I would like to apologize to you. For the second question: For example, test sample 1 5 2 3 6 12 17

      When gcd is a multiple of 1: there are 10 situations When gcd is a multiple of 2: there are 4 situations When gcd is a multiple of 3: there are 4 situations When gcd is a multiple of 6: there is 1 situation

      Here I use the array f[m] to represent the number of cases when gcd is a multiple of m

      When we count from back to front: First calculate gcd which is a multiple of 6, ans+=i*f[i], ans+=6*1 ans=6 Next, it is calculated that gcd is a multiple of 3, but at this time multiples of 3 include 6, so ans += i*f[i] cannot be used directly. Need f[3]-=f[6] in front and then calculate ans+= i*f[i] again.

      Is my understanding correct?

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

        The effect of the translation software is not good. I can't guarantee that I understand what you said, but based on your final description, I think your basic counting idea is correct. Do you have instant software contact information? For example discord? If you still have questions, you can add me on discord "cap1tal_lol". Faster communication may reduce misunderstandings caused by translation software. If adding social software friends in this way is offensive to you, or is not allowed by codeforces, please forgive me and ignore what I said. If you have any questions about passing, you can continue to contact me :)

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

          i got the way you intended to do this problem , really amazing to be honest. for any further query i would like to communicate using discord but problem is we do not have discord servers in common so can you share one server link where i can join so that we can communicate from there ? -Cap1taL-

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

      Thanks, -Cap1taL-! You helped me finally solve this problem.

      Here is a clarification on the part that I was missing.

      To calculate $$$∑^{i−1}_{j=1}gcd(a_j,a_i)$$$ for a specific $$$i$$$, we should do the following:

      // "vector<vector<int>> divisors" stores array of divisors (from large to small) for all 1e5 numbers 
      int gcd_sum = 0;
      for (int d: divisors[a[i]]) {
          int gcd_cnt = cnt[d] - already_accounted[d];  // for how many values d is GCD
          for (int dd: divisors[d]) {
              already_accounted[dd] += count_gcd_equal_d;
          }
          gcd_sum += gcd_cnt * d;
      }
      

      Most definitions in this code are preserved from the original explanation by -Cap1taL-. dd is the same as $$$d'$$$. already_accounted[d] indicates the number of values in $$$a$$$ for which d is a divisor but not the greatest divisor (not GCD).

      Additionally, let's analyze the time complexity. Let's find out how many operations this cycle will do in the worst case:

      int ops = 0;
      for (int d: divisors[a[i]]) {
          for (int dd: divisors[d]) {
              ops++;
          }
      }
      

      The result is $$$2835$$$ operations if $$$a[i]=90720$$$. So, in the worst case, our program will perform $$$(8 \cdot 10^4) \cdot 2835 = 2 \cdot 10^8$$$ operations, which is feasible as long as you don't allocate memory in the loops.

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

      I understand the rest of the solution from the tutorial, but I do not understand how to do this "The first step, as in the solution, is to find all divisors of all numbers in the range in mlogm time". I am just a beginner. What I can think of is that we use seive to find all prime factors for each number, but I do not understand how to go from here to finding all factors.

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        int n;
        cin>>n;
        vector<vector<int>> d(n+1,vector<int>());
        for(int i=1;i<=n;i++){
        	for(int j=i;j<=n;j+=i){
        		d[j].push_back(i);
        	}
        }
        

        that cost $$$n\ln n$$$

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

Problem B, I try to test 1 1 11 in everybody AC code and all code print 1 1 1, that a wrong answer.

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

    for 1:

    1 1 11

    0 2 10 // turn 1 and 3 into 2

    2 0 8 // use 2 twos and 2 threes to make 2 ones

    0 2 6 // use 2 ones and 2 threes to make 2 twos

    2 0 4 // etc.

    0 2 2

    2 0 0 // two ones

    1 is possible

    for 2:

    1 1 11

    2 0 10

    0 2 8

    2 0 6

    0 2 4

    2 0 2

    1 1 1

    0 2 0 // 2 twos

    2 is possible

    for 3:

    1 1 11

    2 0 10

    0 2 8

    2 0 6

    0 2 4

    2 0 2

    1 1 1

    0 0 2 // two threes

    3 is possible

    therefore 1 1 1 is a correct answer

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

In problem C, I was able to identify the need for DFS. I wrote my code in both Python and C++. Tried both. But got TLE on pretest 2 in Python and TLE on pretest 5 in C++.

Python — https://codeforces.com/contest/1900/submission/234466578

C++ — https://codeforces.com/contest/1900/submission/234467214

Any kind of help is greatly appreciated.

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

    You used reference for the vector but you should also use it for the string. Your solution is quite nice! I think you are unlucky accepted submission

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

      Thanks for mentioning,i was not able to understand why i got tle on pretest 5.

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

      Really!!? I didn't get AC for a singular "&" sign??

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

        Yes, because the string was been copied every time the function was called. It leads to an O(n^2) time complexity.

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

    I got TLE on 6th pretest with Python. If someone can see the problem, please tell me:

    https://codeforces.com/contest/1900/submission/234478784

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

      Same with me, though when I tried solving it after the contest using C++, with similar logic and passing everything by reference/ making everything global. It passed.

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

      Hey I just checked your submissions and looks like you solved it using Python! Can you explain it to me what was the issue that you were facing before. I wrote a recursive dfs (without any memoization) and got TLE in pretest 6, maybe writing it some other way might have helped.

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

        I have examined other's solutions and wrote bfs based on their solutions. I didn't figure out the reason of failure of my own dfs solution :(

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

          Hey, I got the solution to this. There is a workaround to deep recursion functions in Python. It's a method generated by pajenegod. You can find a discussion about bootstrap here https://codeforces.com/blog/entry/91490 . It is a really useful script.

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

            Thank you for letting me know. I saved it for the future. Now we know why

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

Problem C.Anji's Binary Tree Solution Link : HERE

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

Anyone solved D using Mobius inversion?

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

      Can you please explain your approach too?

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

        Sorting the array gives the same value of the required sum

        The required sum $$$S$$$ is therefore

        $$$\displaystyle\sum\limits_{i=1}^{n} \sum\limits_{j=i+1}^{n} \sum\limits_{k=j+1}^{n} f(a_i, a_j, a_k)$$$
        $$$\displaystyle =\sum\limits_{i=1}^{n} \sum\limits_{j=i+1}^{n} \sum\limits_{k=j+1}^{n} \gcd(a_i, a_j) = \sum\limits_{i=1}^{n} \sum\limits_{j=i+1}^{n} (n - j) \gcd(a_i, a_j)$$$

        Applying the procedure described in this blog:

        $$$\displaystyle S = \sum\limits_{i=1}^{n} \sum\limits_{j=i+1}^{n} (n - j) \gcd(a_i, a_j)$$$
        $$$\displaystyle= \sum\limits_{k=1}^{M} \sum\limits_{i=1}^{n} \sum\limits_{j=i+1}^{n} (n - j) k [\gcd(a_i, a_j) = k]$$$
        $$$\displaystyle=\sum\limits_{k=1}^{M} \sum\limits_{i=1}^{n} \sum\limits_{j=i+1}^{n} (n - j)\, k \, [\gcd(\frac{a_i}{k}, \frac{a_j}{k}) = 1]$$$

        Applying mobius inversion:

        $$$\displaystyle= \sum\limits_{k=1}^{M} k \sum\limits_{d = 1}^{\lfloor \frac{M} {k} \rfloor} \mu (d) \sum\limits_{i=1}^{n} \sum\limits_{j=i+1}^{n} (n - j) \, [kd \mid a_i] \, [kd \mid a_j]$$$

        Let

        $$$\displaystyle \text{magic}(x) = \sum\limits_{i=1}^{n} \sum\limits_{j=i+1}^{n} (n - j) \, [x \mid a_i] \, [x \mid a_j]$$$
        $$$\displaystyle = \sum\limits_{j=2}^{n} (n - j) \, [x \mid a_j] \sum\limits_{i=1}^{j - 1} \, [x \mid a_i]$$$
        $$$\text{If }\, i_1, i_2, \dots i_m \text{ are the indices of multiples of } x \text{ in the sorted array }$$$
        $$$\text{magic}(x) = (n - i_1)(1 - 1) + (n - i_2)(2 - 1) + \dots (n - i_m)(m - 1) $$$

        Which can be calculated "on the fly", by factorizing each arr[i] and updating magic[f] where f is a factor of arr[i].

        Thus the required sum is

        $$$\displaystyle= \sum\limits_{k=1}^{M} \sum\limits_{d = 1}^{\lfloor \frac{M} {k} \rfloor} \mu (d) \, k \, \text{magic}(kd) $$$

        Calculating magic[x] by factoring in O(n * MAX_FACTORS): Submission

        Calculating magic[x] without factoring in O(M log M): Submission

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

infinite water source ftw

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

    Ikr? Minecraft players had an advantage in the problem!

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

D could solved in O(MlogM) without factorizing. Just do the normal trick of counting gcd pairs and count in the contribution of c.

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

    could you please explain?

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

      I will first explain the normal method to count gcd pairs. Typical problem is, given an array $$$a$$$ of length $$$N$$$ with value range $$$[1,M]$$$. Count the sum of $$$gcd$$$ of each pair of elements, formally $$$\sum_{i=1}^N\sum_{j=i+1}^Ngcd(a_i,a_j)$$$.

      Instead of iterating each pair of elements, we calculate the contribution from $$$1$$$ to $$$M$$$ as $$$gcd$$$ of a pair of elements. Define two functions:

      $$$g(i) = $$$ the count of pairs that $$$gcd$$$ is $$$i$$$.

      $$$h(i) = $$$ the count of pairs that $$$gcd$$$ could be divided by $$$i$$$.

      Suppose number of elements that could be divided by $$$i$$$ is $$$cnt_i$$$, then $$$h(i)=cnt_i*(cnt_i-1)/2$$$. By inclusion-exclusion principle, $$$g(i)=h(i)-\sum_{j>i\ and\ i|j}g(j)$$$.

      Iterate from $$$M$$$ to $$$1$$$, calculate $$$cnt$$$ and $$$h(i)$$$ with the harmonic trick.

      for (int i = M; i >= 1; --i) {
          int cnt = 0;
          long long h = 0;
          for (int j = i; j <= M; j += i) {
              cnt += c[i];
              if (j > i) h += g[j];
          }
          g[i] = 1ll * cnt * (cnt - 1) / 2 - h;
      }
      

      Now come back to the original problem.

      We need to calculate the contribution of each $$$i$$$ where $$$f(a,b,c)=i$$$. WLOG, suppose $$$a\le b\le c$$$. Suppose we are iterating all multiples of $$$i$$$ and reach $$$j$$$. We fix $$$j$$$ as $$$b$$$. All numbers smaller than or equal to $$$j$$$ and is a multiple of $$$i$$$ could be a choice of $$$a$$$. All numbers greater than or equal to $$$j$$$ is a choice of $$$c$$$. Notice here $$$c$$$ is not required to be a multiple of $$$i$$$. Then we have four cases: $$$a<b<c$$$, $$$a=b<c$$$, $$$a<b=c$$$, $$$a=b=c$$$.

      By calculating the count of $$$a$$$, and precalculating the count of numbers greater than each $$$b$$$, each case could be calcualted in $$$O(1)$$$. Then by a similar inclusive-exclusive calculation, the whole problem could be solved in $$$O(MlogM)$$$.

      Here is my code. https://codeforces.com/contest/1900/submission/234450747

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

        Thank you very much. This was really awesome and helpful.

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

        Great explanation! Seems like gcd convolution is just a generalization of this, but even knowing how to do gcd convolution, I was not able to solve the initial problem, so your commentary has really helped a lot :)

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

ABC was too easy this contest.

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

    and my rating dropped for not solving more than one question in the contest

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

Problem B. If all numbers are odd or all are even. Then [1,1,1] since you can make any of them after some operations. Else pick the index of the number which has the unique parity. [1,2,1] pick two, [2,1,2] pick one. [1,2,3] pick two.

Operatio on [1,2,3]

[1,2,2,3,3,3] -> [&1&,2,2,&3&,3,3] -> [2,2,3,3,2] -> [2,2,&3&,&3&,2] -> [2,2,2,2].

Magic as described by the author.

234542604

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

Hi , can smb tell me whats wrong with dfs that returns the answer in task C , because I have TLE in pretest 5.

include <bits/stdc++.h>

using namespace std;

define endl '\n'

int dfs(int x, int kount,string s, vector<pair<int,int>> v){ if(v[x].first==0 && v[x].second==0) return kount; int ans=1000000000; if(v[x].first!=0){ if(s[x-1]=='L') ans=min(ans,dfs(v[x].first,kount,s,v)); else ans=min(ans,dfs(v[x].first,kount+1,s,v));

}
if(v[x].second!=0){
    if(s[x-1]=='R')
        ans=min(ans,dfs(v[x].second,kount,s,v));
    else
        ans=min(ans,dfs(v[x].second,kount+1,s,v));

}
return ans;

}

void solve(){ int n; cin>>n; string s; cin>>s; vector<pair<int,int>> v(n+1); for(int i=1; i<=n; i++) cin>>v[i].first>>v[i].second; cout<<dfs(1,0,s,v)<<endl;; }

int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t=1; cin>>t; while(t--){ solve(); } return 0; }

P.S it works O(n) and n from the text is <=3*10^5 , I can't understand why it's TL

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

    it might be because the vector and string are not passed by reference, causing the program to make a copy of both of them, causing the time complexity to be O(n^2) instead of O(n).

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

can some one please tell why it is giving TLE on test case 5 and please correct it.

https://codeforces.com/contest/1900/submission/234547330

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

Problem D can be solved by mobius inversion formula.

$$$ \begin{align} \sum_{i = 1}^n (n - i) \sum_{j = 1}^{i - 1} \gcd(a_i, a_j) &= \sum_k k \sum_{i = 1}^n (n - i) \sum_{j = 1}^{i - 1} [\gcd(a_i, a_j) = k]\\ &= \sum_k k \sum_{\substack{i = 1\\k | a_i}}^n (n - i) \sum_{\substack{j = 1\\k | a_j}}^{i - 1} [\gcd(\frac{a_i}{k}, \frac{a_j}{k}) = 1]\\ &= \sum_k k \sum_{\substack{i = 1\\k | a_i}}^n (n - i) \sum_{\substack{j = 1\\k | a_j}}^{i - 1} \sum_{d | \gcd(\frac{a_i}{k}, \frac{a_j}{k})} \mu(d)\\ &= \sum_d \mu(d) \sum_k k \sum_{\substack{i = 1\\kd | a_i}}^n (n - i) \sum_{\substack{j = 1\\kd | a_j}}^{i - 1} 1 \end{align} $$$

Which can be solved in $$$O(n\log n + n \sqrt{m} + m\log m)$$$. Code: 234463754

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

Note that we need to solve

$$$\sum\limits_{i=1}^n(n-i)\sum\limits_{j=1}^{i-1}\text{gcd}(a_i,a_j)$$$

Use the equation

$$$ n=\sum\limits_{d|n}\varphi(d) $$$

We have

$$$\begin{aligned}&\sum\limits_{i=1}^n(n-i)\sum\limits_{j=1}^{i-1}\text{gcd}(a_i,a_j)\\=&\sum\limits_{i=1}^n(n-i)\sum\limits_{j=1}^{i-1}\sum\limits_{d|\text{gcd}(a_i,a_j)}\varphi(d)\\=&\sum\limits_{i=1}^n(n-i)\sum\limits_{d|a_i}\varphi(d)\sum_{j=1}^{i-1}[d|a_j]\end{aligned}$$$

Pretreatment Euler function so that we can solve the equation in time complexity $$$\mathcal{O}(n\sqrt{n})$$$

234478574

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

    Why do you need sqrt in complexity?

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

      Assume that $$$n$$$ equals to the range of $$$a_i$$$, we need to find out all the factors of $$$a_i$$$, check my code in the following link and you will get it ;)

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

        Yeah, I just meant you can precalculate divisors for each i (note that it's O(n log n) both time and memory complexity), then you can go through all divisors of a number (which are up to 128 for a numbers <= 10^5).

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

Thanks for the fast editorial !

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

Are the "Bonus problems" somewhere for us to submit them??

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

.

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

Hey! guys, I'm new to competitive programming. I tried to implement anji's tree solution but I got a TLE, but when I passed the string by reference to the dfs function it worked Could someone explain to me how passing an argument by reference influence the run time. This is my code: https://codeforces.com/contest/1900/submission/234732141

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

Problems C and E are just... weird... Nothing really to solve, just implement standard algorithms.

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

Can anyone explain why this approach doesnt work for Problem D?

So i was iterating over A, and at index i i'm considering that to be middle value of triplet that is b. So as per question i need to find value of a and c now. I initialized currentIndexAns = 0 for this loop. Since a index has to be less than index of middle that is i for current loop. In an inner loop of i, i'm iterating A again. In this case if my inner loop index that is j. (j<i), then i will check if a[j]<=a[i], where i index is my assumed middle value, i will calculate its gcd(a[j], a[i]). And add it to currentIndexAns answer. After this i will have sum of all possible gcd values which can have i index as middle. Then i will multiply this currentIndexAns with count of indexes that is above i, so, j>i and a[j]>=a[i]. Let's call this count as countMaxLeftMiddle. Then i will multiply this, with currentIndexAns * countMaxLeftMiddle. To get contributions of triplets which have i as middle index.

Here is my code:

#include <bits/stdc++.h>

using namespace std;

class Solution {
    int gcd(int a, int b) {
        if (!a || !b)
            return a | b;
        unsigned shift = __builtin_ctz(a | b);
        a >>= __builtin_ctz(a);
        do {
            b >>= __builtin_ctz(b);
            if (a > b)
                swap(a, b);
            b -= a;
        } while (b);
        return a << shift;
    }

    public:
    long solve(int* a, int n) {
        long ans = 0, subPrblmAns;
        int greaterEqMidCntOnRight, mid;

        for (int i=0; i<n; i++) {
            mid = a[i];

            subPrblmAns = 0;
            greaterEqMidCntOnRight = 0;
            for (int j=0; j<n; j++) {
                if (i > j) {
                    if (mid >= a[j]) {
                        subPrblmAns += gcd(mid, a[j]);
                    }        
                } else if (i < j) {
                    if (mid <= a[j]) {
                        greaterEqMidCntOnRight++;
                    }
                }
            }
            cout << subPrblmAns << " " << greaterEqMidCntOnRight << endl;

            ans += (subPrblmAns * greaterEqMidCntOnRight);
        }

        return ans;
    }
};

int main() {
    int t, n;
    int *a = NULL;
    Solution sol = Solution();

    cin >> t;
    for (; t>0; t--) {
        cin >> n;

        a = new int[n];

        for (int i=0; i<n; i++) {
            cin >> a[i];
        }

        cout << sol.solve(a, n) << endl;

        delete(a);
        a = NULL;
    }
    return 0;
}
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

when you dont try E, because of stucking in d :(((

Seems easy for me the E one. (I solved it in one go)

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

I cannot understand this part in tutorial for E : The edge will have a weight equal to the size of the SCC that it is going into.

Why is that ? Shouldnt all the weights of edges be 0 ? and find the longest path by vertex numbers ?

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

In D how to create that divisor array in NlogN. i am doing it in NrootN.

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

    You precalculate all divisors for each number using something similar to sieeve.

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

Hi, I have a question related to the time limit in problem C (Anji's Binary Tree).

I got many TLE in submissions like 235439131, 235440112, 235441383. The idea was fine, but after reading some of the comments, I realized that removing some things like memset, global variables, and setting reference variables will get me to the AC (235443694).

I would like to know what kind of aspects I have to think when I want to use memset or other kinds of stuff. Why do the last submissions differ in seconds to each other? What are the technical aspects related to the stuff that I have used in the first submissions? Thanks!

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

    Memset is O(array_size) complexity. So using it for each testcase on array of size 300 000 for 50 000 testcases is just too slow. Always reset arrays by iteratting from begin to N as you know elements after it are unaffected. Rarely you might even need to keep elements you changed in a queue.

    Edit: Also, note that locally declared variables are not guaranteed to have all values set to 0, so they are even worse than forgetting to reset global ones.

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

Can someone Please explain why I am getting a TLE in this solution for problem C 234510811

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

even after lot of modifications and changes, I am getting memory limit exceeded on test case 3 where n = 200000, m = 200000.I think it is due to DFS3() call but couldn't think for it's substitute. This function calculates the maximum length simple path and then for that length path minimum value. this is my submission link.

There might be some other reason for TLE but I have gone through other submissions and they have also allocated same complexity of memory.( vectors and arrays for graphs )

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

Problem D can be solved without the constant of 128.

Firstly notice swapping the indexes doesn't influence the sum. Then swap the indexes to a sorted state.

Then, for each $$$g$$$, we want to know, $$$dp[g] = $$$ how many indexes tuples that $$$i < j < k$$$, that $$$\gcd(a[i], a[j]) = g$$$. Similar to the question, we first calculate $$$cnt[g] = $$$ number of tuples $$$i < j < k$$$ that $$$a[i] = a[j] = 0 \pmod{g}$$$, then minus $$$dp[2g] + dp[3g] + ... dp[\text{max multiplier} \times g]$$$ to $$$cnt[g]$$$

Because we are in a sorted state, we can work on those $$$pg$$$ for each $$$p = 1 .. \text{max multiplier}$$$.

Notice that, there are two cases. The first case is $$$a[i] < p g$$$. In this case, $$$pg$$$'s contribution to $$$cnt[g]$$$ is #$$$(i) * S(pg)$$$. $$$S(pg)$$$ is the number of tuples $$$(j, k)$$$ that $$$j < k$$$ and $$$a[j] = pg$$$. #$$$(i)$$$ is the number of index $$$i$$$s that $$$a[i] < a[j], a[i] = 1g .. (p-1)g$$$ (notice $$$i < j$$$ is obvious because we sorted it).

The second case is $$$a[i] = a[j] = pg$$$. In this case, the sum is $$$T(pg) = \Sigma_{l \in \text{first } pg \text{ index} .. \text{last } pg \text{ index} } (l - \text{first } pg \text{ index}) (N - l) $$$.

Both $$$S(pg)$$$ and $$$T(pg)$$$ are able to be precomputed by walking through the sorted array. So we can result a time complexity in $$$O(N \log N)$$$

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

In question 1 , in 5th test case

10

...#..#.

someone pls explain how the output is 2 ?

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

In Problem C, Test case 3: I can just change the string to LRLR by modifying R -> L and U-> R and reach Vertex 2, that takes 2 modification but Why the answer is 3? Can anyone explain that bit to me?

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

    2nd letter is letter on vertex with index 2. Not on 2nd vertex you reach.

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

    initial RULR(1 2 3 4) path and replace 1-L 3-R 4-L final LRLR modification done in (1 3 4) in your case, you are modifying node 2 which won't affect and increase in one operation You should draw tree clearly

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

Why the BFS soln is not working?? Isn't it O(n)

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

Can Anyone explain solution with code of F local deletions ??

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

include<bits/stdc++.h>

define ll long long int

define llq __int128 using namespace std;

define level 18

define mod 1000000007

define lim 100008

define lldb double

define ln "\n"

const int U = (1 << 30) — 1; // bit operator

int main() { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(0); ll t; cin>>t; while(t--) { ll n,m; cin>>n; string s; cin>>s; vectorans(n+1,0); ll sol=INT_MAX; vectorleaf; for(ll i=1;i<=n;i++) { ll x,y; cin>>x>>y; if(s[i-1]=='R') { ans[x]+=ans[i]+1; ans[y]=ans[i];

}
     else if(s[i-1]=='L')
     {
        ans[y]+=ans[i]+1;
        ans[x]=ans[i];
     }
     else{
        ans[x]+=ans[i]+1;
        ans[y]+=ans[i]+1;
     }

     if(x==0 && y==0) leaf.push_back(i);
  }
  // for(ll i=0;i<n;i++) cout<<ans[i+1]<<" ";
  for(ll i=0;i<leaf.size();i++)
  {
     sol=min(sol,ans[leaf[i]]);
  }
  cout<<sol<<endl;

}

}

Why this is wrong answer ,I am just updating distance from root according to given condition?? can any give me test case ?? @C Question

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

In Problem C, I used memorization to calculate the answer. Although being of time complexity of O(n), It is giving Time limit exceeded for n=10^5. Can someone suggest me the problem?

https://codeforces.com/contest/1900/submission/239971869

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

    You are passing string s in each recursion call and therefore it is actually $$$O(n^2)$$$. I recommend using global variables for stuff such as graphs or labels and preferably all arrays/vectors.