74TrAkToR's blog

Codeforces Round #904 (Div. 2) Editorial
By 74TrAkToR, history, 6 months ago, In English

Thanks for the participation!

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +21
  • Vote: I do not like it

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

D can also be solved by using GCD convolution.

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

    That's true

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

    Can you please elaborate more

    I read this article, and checked your solution, but I am confused, especially about this part:

    for(i=0;i<=n;i++)
{
    b[i]=b[i]*b[i];
}
gcd_convolution_inv(b);

    Aren't we supposed to get the 'dp' array (the same one as in the official solution) after the first convolution? Why square it? Why inverse?

    → Reply
    • »
      »
      »
      6 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I guess $$$b_i$$$ correspond to the number of occurrences of i.

      So if that's true, normal convolution process on $$$C=A \times B$$$ is like doing transform on $$$A,B$$$ and let $$$C_i=A_i \times B_i$$$, then doing inverse transform on $$$C$$$.

      So if you want to calculate the number of pairs $$$(i, j)$$$ such that $$$\gcd(a_i,a_j)=k$$$, so this equals to doing an gcd convolution on the cnt array, that is the array b.

      So as what I said above, doing a gcd convolution on b is what the code do.

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

    It's a wonderful solution and it's better than the Editorial!

    → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i think i was tooo close to solve c. damn it , i will see it next time

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

    me too, bro, i've saw a similar problem in jscpc last year, but i forgot the progress

    → Reply
»
6 months ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

It says tutorial is not available, so I'll write about what I solved myself.

A: Digit sum can be found in $$$O(\log x)$$$. $$$y$$$ is at most $$$x + 2k$$$. Time complexity $$$O(k \log x)$$$.

B: If there are $$$a$$$ digit with $$$1$$$ in the $$$k$$$ smallest digits, you can shift them all to the $$$k$$$ rightmost position to make a multiple of $$$2^{k-a}$$$. Try for all $$$k$$$, utilizing prefix sum to not make time complexity $$$O(n^2)$$$. Time complexity $$$O(n)$$$

D: If there is an integer $$$x$$$ that $$$a_i$$$ and $$$a_j$$$ are both divisible by, then they are not good pairs, only if $$$x$$$ is present in $$$a$$$. However if $$$2$$$ and $$$3$$$ is present but $$$6$$$ is not, then you need to subtract duplicates in multiples of $$$6$$$. Therefore, you must use Inclusion-Exclusion, but exclusively on elements of $$$a$$$ and their multiples. Because $$$a_i$$$ is bounded by $$$n$$$, time complexity is $$$O(n \log n)$$$ due to the harmonic lemma.

EDIT: Tutorial is up. You might better link it to the contest as well

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

    and their multiples

    damn, how did i not see that D:

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

      Don't worry, I was bashing my head for 15 minutes on why my solution based on the mobius function doesn't work, then realized there are values outside $$$a$$$, fixed that, and bashed my head for another 15 minutes on why the solution is spitting $$$42$$$ on the last TC of examples

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

        Same. Realized after the contest that I was considering every gcd's. Should have considered the numbers present in the array only.

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

        I don't understand how you can generalize the mobius function for non-primes. Can you give explanation?

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

          Read the discussion under this thread. If that discussion was not enough and you need some in-depth stuff, that type of transformation is often called the 'divisor möbius transform' (or simply the dirichlet inverse). If we use the divisor möbius transform on $$$\mathbf{1}$$$, the vector containing $$$1,0,0,0,0,\cdots$$$, you'll get the möbius function. If you use it on some other vector, we will result in some other 'function', which can then be used in our Inclusion-Exclusion.

          → Reply
  • »
    »
    6 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Hi could you tell how to do that in O(n) for problem B. I got the idea like we need to move the ones from the last to zeros just before, but unable to implement it.

    I have seen one implementation (below) in which we only need to consider the movements of zeros, but not sure what are takeaways from this. 

    void solve(){
	int n; cin>>n; 
	string s; cin>>s; 
	int start = n-1, end = n-1; 
	ll ans = 0;  
	for(; end >= 0; end--){
		while(start >= 0 && s[start] != '0') start--; 

		if(start < 0) {
			cout<<"-1 "; 
			continue; 
		}

		ans += end-start; 
		start--; 
		cout<<ans<<" "; 
	}

	cout<<endl; 
}

    Thanks!

    → Reply
    • »
      »
      »
      6 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      you can store the positions of all the zeroes or maybe just iterate through the string to find the next zero and store that index ,say i, next time you need to find the index of a zero , start from i

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

      void solve() { ll n; cin >> n; string s; cin >> s; ll zero = 0; ll ans = 0; reverse(s.begin(), s.end()); ll cnt = 0; for (int i = 0; i < n; i++) { if (s[i] == '0') { ans += (i — zero); cout << ans << " "; cnt++; zero++; } else if (s[i] == '1') continue; } while (cnt++ < n) cout << -1 << " "; cout << endl; } Easy solution to problem B...

      → Reply
      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sorry, I accidentally clicked the wrong one.I'm new to this site and I'm not very familiar with it.

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

      What is your logic behind code? Thanks

      → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

fast editorial

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks for fast editorial ! pE too hard and interesting !!

→ Reply
»
6 months ago, # |
  Vote: I like it -7 Vote: I do not like it

what a hard div 2!

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

    I couldn't solve 2nd today, but I don't claim it to be hard or soft.

    → Reply
»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I didn't solve C . But I cant realise the solution . someone help me to understand !

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

    I missed it too. I don't understand how in the solution, they say that the minimum will either occur at position 1 or position m. What if we have: (1, 1) (1, 2) (m-1, m) (m,m). Then the minimum will be any value between 2 and m-1, and the maximum will be either 1 or m, both possessing value 2.(Assuming m > 3 for simplicity of the example).

    I also don't quite see how that is necessary for their algorithm to work? The whole line sweep thing doesn't seem to require that fact either, right? It just requires the minimum to be outside of all the current open segments?

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

      i don't get it too.. Can someone please explain the solution of C?

      → Reply
      • »
        »
        »
        »
        6 months ago, # ^ |
        ← Rev. 3   Vote: I like it +8 Vote: I do not like it

        Oh shoot, I think I get it now. Maybe this restating/re-explanation will help others: For a given solution, there are multiple valid configurations of segments that achieve the same minimum/maximum delta. But for any optimal configuration, you can always tweak it so that the minimum is at position 1 or m. Imagine for a second that we are given a sample optimal configuration, with a minimum value at some index y, and a maximum at some index z, where y < z. But the minimum doesn't occur at index 1, which is to say y != 1. Then, since the value at y is less than the value at 1, we must have some segments included in our problem that include 1 as a starting index, but have an ending index of less than y. Since these segments can not add to our maximum, since y < z, we can remove them from our configuration and we still have an optimal configuration. Thus if your minimum index is less than your maximum index, we can transform your optimal configuration to possess a minimum at 1. The same logic is true if we have a minimum index greater than our maximum index, only in this case, we can create an optimal configuration with a minimum value at m. Now, given that it is always possible to get an optimal configuration with either 1 as the minimum or m as the minimum, we can sweep through and try either as the minimum. We can also always have a minimal configuration where the value at 1 or m is zero, because if there's a segment that covers the maximum index and the minimum index, removing it has no affect, and if it just covers the minimum index and other indices that aren't maximum, it must be removed in order for us to have an optimal configuration with that minimum index. Now, the line sweep is a way of finding the peak position when we have a minimum of 0 at 1 or at m, so we have two sweeps for that. Hope this helps and isn't too much word salad! If I'm missing anything, would be happy to hear from someone more knowledgable on this stuff. This was my first programming competition and this stuff seems quite interesting!

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

          since the value at y is smaller than the value at 1(if I am not wrong). Good explanation bud.

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

          excellent explaination！thanks！

          → Reply
      • »
        »
        »
        »
        6 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        https://codeforces.com/contest/1884/submission/229341013

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

    I tried to put comments in the code explaining the problem maybe you can get it from here — https://codeforces.com/contest/1884/submission/229341013

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

What's wrong in this solution for problem D — 229186378 ? Any help is appreciated.

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I would have become CM today. Screw sets bro.

Submission for D using sets: (TLE >2000ms) https://codeforces.com/contest/1884/submission/229175001

Submission for D with array: (AC ~700ms) https://codeforces.com/contest/1884/submission/229192264

:(

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

    why use trees tho

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

      Convenience, habit, underthinking, etc. Should have seen that coming though.

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

        I feel you brother. You'll goin to be CM in today's next contest no worries.

        → Reply
»
6 months ago, # |
  Vote: I like it +2 Vote: I do not like it

In problem C, I cant understand why

From this, it follows that the minimum will either occur at position 1 or at position m

can't the minimum occur somewhere in between

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

    we are only selecting segments that contain x

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

      Consider this test :

      2 3

      1 1

      3 3

      Doesn't the minimum occur in 2-2?

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

    sort the relevant segments by the left point and by the right point, you'll see.

    → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the reason behind the name of the second problem?

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

even though i couldnt solve any but problem A was beautiful

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone pls help me identify my mistake in Div2D link? Any help would be appreciated.

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

"Now let's understand which gcd values are not suitable. If there is a number x in the array (i.e., cntx>0 ), then all g multiples of x are not suitable"

Can someone please elaborate the meaning of the above statement in the editorial for problem D? 'not suitable' for what?

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

    dp_g denotes the number of (i, j) for which gcd(a[i], a[j]) = g

    g is not suitable, indicating that g % a[i] == 0 exists in the array, and dp_g cannot accumulate to the answer

    → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Someone Explain the Solution for Problem C. Most Importantly the Part From this, it follows that the minimum will either occur at position 1 or at position m

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Imagine the selected segments. The maximum is reached somewhere, let's say at X.

    Now, there are two types of segments:

    • Containing X: they are guaranteed to increase maximum (value at X) by 1, but may (or may not) also increase minimum by 1. So they are either good or neutral. Let's simply include them

    • Not containing X: they are guaranteed not to change maximum (value at X), but may increase minimum. So they are either bad or neutral. Let's simply NOT include them

    So, we include all segments containing X (and only them). Now let's say X=6 (and all segments contain X). You can't have minimum at, say 3, because that would require that vs[2] > vs[3], so there is some segment, that contains 2, but not 3 — but that is impossible because all segments contain X (so segment containing 2 and X would also contain everything in-between including 3).

    Then we "brute force" all possible X's fast with Events:

    https://codeforces.com/blog/entry/121618?#comment-1080014

    → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am new to Competitive Programming. Is there any guideline for me? Any path I can follow?

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

There is a bit flaw in problem E's tutorial, in the second paragraph there should be b_{pos} not $$$b_pos$$$

→ Reply
»
6 months ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it

Here is another way to solve D.

Let us call $$$f_x$$$ mean that is there $$$a_i$$$ is its factor.We can get the values in $$$\Theta(n\ln{n})$$$.

And than we can get the answer:

$$$ \begin{aligned} & \sum\limits_{i=1}^n\sum\limits_{j=1}^n f_{\gcd(a_i,a_j)} \\ & =\sum\limits_{d=1}^n f_d\sum\limits_{i=1}^n\sum\limits_{j=1}^n [\gcd(a_i,a_j)=d] \\ & =\sum\limits_{d=1}^n f_d\sum\limits_{i=1}^n\sum\limits_{j=1}^n [\gcd(\frac{a_i}{d},\frac{a_j}{d})=1][d|a_i][d|a_j]\\ & =\sum\limits_{d=1}^n f_d\sum\limits_{i=1}^n\sum\limits_{j=1}^n \varepsilon(\gcd(\frac{a_i}{d},\frac{a_j}{d}))[d|a_i][d|a_j]\\ & =\sum\limits_{d=1}^n f_d\sum\limits_{i=1}^n\sum\limits_{j=1}^n [d|a_i][d|a_j]\sum\limits_{t|\frac{a_i}{d}\bigwedge t|\frac{a_j}{d}} \mu(t)\\ & =\sum\limits_{d=1}^n f_d\sum\limits_{t=1}^{\lfloor\frac{n}{d}\rfloor} \mu(t)\sum\limits_{i=1}^n\sum\limits_{j=1}^n [dt|a_i][dt|a_j]\\ & =\sum\limits_{d=1}^n f_d\sum\limits_{t=1}^{\lfloor\frac{n}{d}\rfloor} \mu(t)(\sum\limits_{i=1}^n[dt|a_i])^2\\ \end{aligned} $$$

The last $$$\sum$$$ we can solve it in $$$\Theta(n\ln{n})$$$.

So we can solve the problem in $$$\Theta(n\ln{n})$$$.

record link:https://codeforces.com/contest/1884/submission/229180049.

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please show me why my code for B goes wrong

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why this code gives wrong answer for problem D — 229186378

→ Reply
  • »
    »
    6 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Anyone? Why am I undercounting the number of non intersting pairs by above approach of op?

    For a number x in a(consider distinct as I've precalculated their frequency)

    cnew = #of multiples of x visited for the first time

    cprev=#of multiples of x which were already visited by some y<x

    Then new non intersting pairs introduced by x = cnew*(cnew-1)/2 + cprev*cnew

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

      Same approach bud! That's giving me wrong answer on test 5.

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

    hey check this test case

    1

    15

    2 2 2 2 2 2 2 2 2 2 2 3 5 10 15

    ans=35

    our output=36

    Here we are not excluding the (10,15) pair as when iterating at 5 both 10 and 15 are already visited

    → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any small hint for D? I am stuck over 10 hours on it.

I had some idea, but it ended up working 30 seconds on random data and up to 80 seconds on test #15 (2, 3, 4, 5 ... 1000000) — much better than naive O(N^3), but nearly not fast enough.

→ Reply
  • »
    »
    6 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Think of the harmonic lemma, i.e. $$$\sum_{i=1}^n{n/i} = O(n \ln n)$$$. Find out how that relates to the bound on the values of $$$a_i$$$.

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

      I already do.

      To be a bit more specific. I start by computing "base blockers": for example in case array contains both 4 and 12, we don't have to check any pair against 12, because if the pair is divisible by 12, it is also divisible by 4.

      Pseudocode here:

      for (int g in sorted-grouped(vs))
    if (!excluded[g]) {
        base.push_pack(g)
        for (int i = 1; i*g <= n; i++) {
            if (counts[i*g] == 0) continue;
            excluded[g * i] = true;
            blocking[g].push(g*i)
            blockers[g*i].push(g);
        }
    }

      This works in sum(n/i) = N log N

      Then I for the most part do a stupid thing: for all possible "conflicts" ("baseBlocks" in code below) mark all conflicting elements one by one and keep track of the remaining number of unconflicting ones 

      for (int g in sorted-grouped(vs))
    unblockedCount = n;
    for (int baseBlock : blockers[g])
        for (int toExclude : blocking[baseBlock])
            if (blockedCount[toExclude] == 0)
                unblocked -= count[toExclude]
            blockedCount[toExclude]++;
    ans += counts[g] * unblockedCount
ans /= 2

      I cut(ed) out some optimizations which allow this thing to run somewhat fast (80s) instead of absolutely slow.

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

        For some value of $$$a_k$$$, the number of conflicts is $$$C \choose 2$$$, where $$$C$$$ is the number of occurrences of multiples of $$$a_k$$$. Apply the Inclusion-Exclusion theorem to this for prevent some conflicts being counted multiple times.

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

          I thought about Inclusion-Exclusion, but couldn't come up with anything with it, because the formula grows rapidly depending on the number of sets. Just for 4, it is big: StackOverflow

          Here there seems to be up to ~8 sets (because 2*3*5*7*11*13*17*19 = 9699690 > 1000000, so "divisible by ~9+ 'various' numbers" sets are all empty), which is a lot.

          I guess, I'll think more in this direction. Thanks!

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

          Implemented Inclusion-Exclusion:

          lon combinations = 0;
function<void(int, lon, int, bool)> backtrack = [&](int l, lon p, int m, bool ne) {
	if (p > n)
		return;
	
	if (ne) {
		int c = divisibleBy[p];
		lon combinationsChange = m * c * (lon)(c - 1);
		combinations += combinationsChange;
	}
	if (l >= base.size()) return;

	backtrack(l + 1, p, m, false);
	backtrack(l + 1, lcm(p, base[l]), -m, true);
};

backtrack(0, 1, 1, true);
cout << (combinations / 2) << endl;

          'ne' (from NEw, but that is keyword) — whether we yet have to account for current combination

          'm' — swaps sign depending on the number of elements in the subset, to account for inclusion/exclusion

          'p' — LCM of the chosen subset

          it works, but now I get Time Limit on test #9 ... Locally takes 110-200 seconds just for 50 000 elements. There are just too many possible subsets with LCM<=n. I hoped that there won't be too many because LCM might grow rapidly, close to multiplication, but overall I am not too surprised. Looks like this approach is exponential.

          → Reply
          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
            ← Rev. 5   Vote: I like it 0 Vote: I do not like it

            That is kind of a "naive" inclusion-exclusion implementation, sometimes it works,but most of the time it really doesn't.

            The key to inclusion-exclusion (especially in number theory) is to "record the contribution" of that set. For example using the set operation, let's say that we want to find $$$|A \cup B \cup C|$$$. That is $$$|A|+|B|+|C|-|A \cap B|-|B \cap C|-|A \cap C|+|A \cap B \cap C|$$$. However we do not need to explicitly know this, we only need to record the contribution of $$$A$$$, $$$B$$$, $$$C$$$, etc. When counting the set $$$S$$$, find each subset $$$T \subset S$$$, and set $$$cont(T) \leftarrow cont(T)-cont(S)$$$. Initially This way, $$$A$$$, $$$B$$$, $$$C$$$ contribute by $$$1$$$, $$$A \cap B$$$, $$$B \cup C$$$, $$$A \cap C$$$ contribute by $$$1-2=-1$$$, and $$$A \cap B \cap C$$$ contributes by $$$1-3+3=1$$$. Things are automagically done. This can be generalized to superset operations as well (then can be naturally translated to zeta/mobius transform and then Subset/Superset/AND/OR/GCD/LCM convolution), but that's not a topic for this task anyways.

            Now apply this to number theory. In number theory, subsets/supersets are simply multiple/divisor relations. We know "multiples of $$$2k$$$" are subsets of "multiples of $$$2$$$", "multiples of $$$3k$$$" are subsets of "multiples of $$$3$$$", etc. So, start by setting the $$$cont(S)$$$ of everything as $$$1$$$. For each multiple of any value in $$$a$$$, do what I just described above. Then, we have the answer $$$z$$$ for non-good pairs. The answer for good pairs is simply $$${n \choose 2} - z$$$. Time complexity is $$$O(n \ln n)$$$ due to the harmonic lemma.

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

              Good news: After implementing my 3rd idea, I finally solved the task, largely with Inclusion-Exclusion, although differently. I used relation for 2 sets/properties, but "conditional":

              f( (a | b | c)&sub ) =
    f( (a | b)&sub )
    + f(c&sub)
    - f( (a | b) & c&sub )

              By f( (a | b | c)&sub ) I mean: "count of pairs, which satisfy property "sub" and satisfy at least one of properties "a", "b", "c". Properties are all of type "pair divisible by X".

              Then:

              • the first part: f( (a | b)&sub ) is a main loop accumulator

              • the second part: f(c&sub) is direct formula using precomputed array

              • the third part: f( (a | b) & c&sub ) ... well ... this is a recursive call

              Finally, the recursive function has a "fast-track": in case "sub" property (numbers divisible by "sub") narrows down initial set to <= 40 numbers, it uses alternative N^2 * log N algorithm.

              The entire time complexity is O(god knows how much of N), but took 889ms on CodeForces. I kinda intuitively understand why this approach had a chance, but my previous two approaches also seemed to have a chance.

              You can glance at my code and see that I probably overcomplicated it.

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

              Bad news: I still don't understand what you mean. After re-reading your comment several times, my impression is that you mean this kind of code:

              vector<int> cont(n+1, 1);
for (int base = 2; base <= n; base++)
    for (int k = 2; base*k <= n; k++)
        cont[base*k] -= cont[base];

              Do I understand correctly? If so, what's the logic behind it? Seems absolutely random. There's gotta be something simple I don't see: too many people solved the task:)

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

                Yes, that's what I meant. It's kind of an "intuitive" thing. "If you counted $$$a$$$ then you don't want to count $$$2a$$$ or else you'll double count things", "If you counted $$$a$$$ and $$$b$$$ separately you need to subtract the count of $$$\text{lcm}(a,b)$$$ because they are counted twice" All these things have meanings compressed in this $$$cont$$$ array. What may be also interesting is, that $$$cont$$$ array where bases are all integers greater than $$$1$$$, is basically the Möbius function. Yes, we are reinventing many wheels here! The explanation there could give you some deeper insights into this. Or if you want how the code works, you can read 229166896. mu is the $$$cont$$$ array in my code.

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

                  I managed to gain some intuition for the 'cont' array: cont[i] is how many times we have "yet to account" for pairs where both numbers are divisible by 'i'.

                  And I managed to (finally) solve the problem accordingly: https://codeforces.com/contest/1884/submission/229543303

                  I have yet to:

                  • Think through how this specific case relates to the general case you described in the previous comment

                  • Analyse your code: looks like we still have some differences in how we account for specific divisors

                  You solved this during the contest. How come you are blue instead of red?

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 months ago, # ^ |
                  ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                  "How come you are blue instead of red?" mostly due to unbalanced skillset. I absolutely suck at DP/brute force for example. I just managed to solve the task because I am probably overskilled at NT compared to other skills

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

                  DP is hard, because there are just so many possibilities what dynamics to compute. And I think this task is a perfect example of that: the solution (which is largely DP) ends up being short, but it's far from trivial to come up with the right DP here.

                  cont array where bases are all integers greater than 1, is basically the Möbius function

                  • I was able to prove it based on this definition of the Mobius function. I actually came up with two independent proofs for it and very related Inclusion-Exclusion "sign change" (depending on how many sets intersection are being accounted for). Although I don't get an intuition for neither — are they supposed to be not entirely obvious?

                  • Thought through the general case from your previous comment

                  • And analyzed the details of how your solution works (fundamentally — the same as my last one).

                  • And also understood how the official solution works and coded it (my 5th, 3rd passing solution:) It's different — it computes good pairs directly

                  I'm probably done with this task. Thanks a lot for your help! :)

                  Now trying to come back to one of the tasks in my "solve later" list, which also seems to have some even more elaborate Inclusion-Exclusion.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 months ago, # ^ |
                  ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                  chromate00 Bro, how/where did you learn number theory? Is there any source/book recommendation?

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

                  Mostly in material regarding MO problems. For CP this should be generally good enough though.

                  → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain E in detail? I cannot understand the editorial.

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what is sweep algorithm mentioned in C?

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

    It means that for each segment [l, r] we generate two "events":

    • { l, "start" }

    • { r, "end" }

    Then we sort them by location and process them (events, not original segments) left to right:

    • "start" event: increase current segment count, also check if new best score is achieved

    • "end" event: decrease current segment count

    Take a look at my solution, it should be quite readable

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

I don't know why I get wa for D use inclusion-exclusion, who can help me

(https://codeforces.com/contest/1884/submission/229407443)

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain what is sweep line algorithm?

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain me how would we implement the logic of B problem as explained in editorial , like its easy to maintain cnt_1 and sum_1 but how would we find cnt_1 number of zeroes after every index ? I tried storing the indisces in a vector and then find the sum of first cnt_1 for every index but that gave me a TLE. Someone pls explain

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

    You compute prefix/suffix sum. Something like this:

    vector<int> prefix1(n+1);
for (int i = 0; i < n; i++)
    prefix1[i+1] = prefix1[i] + (s[i] == '1');
// ... later
prefix1[b] - prefix[a] // number of 1s between 'a' and 'b' (not inclusive 'b')

vector<int> suffix0(n+1);
for (int i = n-1; i >= 0; i--)
    suffix0[i] = suffix0[i+1] + (s[i] == '0');
// ... later
suffix0[a] - suffix0[b] // number of 0s between 'a' and 'b' (not inclusive 'b')

    You don't need to compute prefix/suffix sum in this case (I didn't — note that I moved the opposite direction though — right to left), but it might be easier to solve with them sometimes

    → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I believe I have a solution for E that differs slightly from the editorial. We also consider the inverted array $$$B$$$. Let $$$f(l, r)$$$ be the cost to reduce $$$B[l, r]$$$ to all zeros. If we could compute the prefix/suffix values $$$f(1, i)$$$ and $$$f(i, N)$$$, we could compute the $$$i$$$'th answer as $$$f(i, N) + f(1, i-1)$$$. Note this doesn't necessarily work because we might have to consider wrapping around the end of the array--consider an array like 2 0 1, for instance. However, the prefixes/suffixes can be computed independently if $$$B_1 = 0$$$, and since $$$B$$$ always contains a $$$0$$$, we can rotate $$$B$$$ such that $$$B_1 = 0$$$.

Thus the problem reduces to finding the values of $$$f(1, i)$$$ ($$$f(i, N)$$$ can be computed in the same manner by reversing $$$B$$$). We process them in increasing order of $$$i$$$. The number of operations is just $$$\sum_{j=1}^i \max(0, B_j - B_{j-1})$$$. The cost can be maintained using a monotonic stack.

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

got stuck on A for half the comp because i missed k <= 10 and tried finding ways to optimize the solution... I need to be more careful.

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

can anyone please debug my code for the problem C(counting rythm). It is giving wrong solution on test case 3..I can't figure out that hidden test case. Below is the code -> int n,m; cin>>n>>m; 

set<int> index;
        map<int,int> end;
        map<int,pair<int,int>> start;

        for(int i=0; i<n; i++){
            int l,r;
            cin>>l>>r;
            index.insert(l); index.insert(r);
            start[l].first++; end[r]++;
            if(r==m) start[l].second++;
        }

        ll cnt1 = 0, cnt2 = 0, res1 = 0, res2 = 0;
        for(auto &idx : index){
            if(idx != 1){
                cnt1 += start[idx].first;
                if(end[idx]){
                    res1 = max(res1,cnt1);
                    cnt1 -= end[idx];
                    // if(cnt1<0) cnt1 = 0;
                }
            }

            if(idx != m){
                cnt2 += start[idx].first-start[idx].second;
                if(end[idx]){
                    res2 = max(res2,cnt2);
                    cnt2 -= end[idx];
                    // if(cnt2<0) cnt2 = 0;
                }
            }
        }

        cout<<max(res1,res2)<<endl;

// My logic is that — i m counting how many segments are starting before an end and if a segment ends at m then substract that segment.

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In question E , why the answer should add a value (s+n-i+1)^2+(bi-bli) rather than (s+n-1-l)^2+(bi-bli)?

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B using Binary Search?

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone give a counter test case for this solution of Problem C: Medium Design link

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice editorial

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

Can anyone help me know why my code of div2 D is giving me wrong answer in test 5? Thanks in advance.

→ Reply
»
4 months ago, # |
← Rev. 4   Vote: I like it -10 Vote: I do not like it

10 dislike? why bro why. I just told you how to solve this problem. Is it my mistake? Or to support Palestine on my profile

→ Reply