Thanks for the participation!

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

# | User | Rating |
---|---|---|

1 | Radewoosh | 3759 |

2 | orzdevinwang | 3697 |

3 | jiangly | 3662 |

4 | Benq | 3644 |

5 | -0.5 | 3545 |

6 | ecnerwala | 3505 |

7 | tourist | 3486 |

8 | inaFSTream | 3478 |

9 | maroonrk | 3454 |

10 | Rebelz | 3415 |

# | User | Contrib. |
---|---|---|

1 | adamant | 173 |

2 | awoo | 167 |

3 | nor | 164 |

4 | SecondThread | 162 |

5 | BledDest | 161 |

5 | maroonrk | 161 |

5 | Um_nik | 161 |

8 | -is-this-fft- | 149 |

9 | Geothermal | 146 |

10 | ko_osaga | 142 |

Thanks for the participation!

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of Codeforces Round 904 (Div. 2)

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/06/2023 11:19:13 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

D can also be solved by using GCD convolution.

That's true

Can you please elaborate more

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

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?

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.

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

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

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

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

damn, how did i not see that D:

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

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

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

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.

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.

Thanks!

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

fast editorial

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

what a hard div 2!

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

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

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?

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

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 haveanoptimal 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!since the value at y is

smallerthan the value at 1(if I am not wrong). Good explanation bud.Good catch, thanks! Sorry about that

excellent explaination！thanks！

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

thnx a lot..

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

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

I did the same ... cant figure out where it goes wrong ... did you find the error? UPD: nvm found the bug

Take a look at Ticket 17110 from

CF Stressfor a counter example.I would have become CM today. Screw sets bro.

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

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

:(

why use trees tho

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

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

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

we are only selecting segments that contain x

Consider this test :

2 3

1 1

3 3

Doesn't the minimum occur in 2-2?

I think i get it now, the minimum may occur at any other place but if it occurs in a segment [l,r] along with max position x we can calculate if it can be ignored by either choosing to ignore segments starting from 1 or segments ending at m, if it cannot be ignored our answer does not worsen.

Please refer to https://mirror.codeforces.com/blog/entry/121618#comment-1079913

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

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

even though i couldnt solve any but problem A was beautiful

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

Take a look at Ticket 17112 from

CF Stressfor a counter example."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?

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

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 mImagine 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://mirror.codeforces.com/blog/entry/121618?#comment-1080014

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

There is a bit flaw in problem E's tutorial, in the second paragraph there should be

`b_{pos}`

not $$$b_pos$$$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:

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://mirror.codeforces.com/contest/1884/submission/229180049.

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

Take a look at Ticket 17111 from

CF Stressfor a counter example.Why this code gives wrong answer for problem D — 229186378

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

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

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

Any small

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

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

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:

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

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

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.

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!

Implemented Inclusion-Exclusion:

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

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-goodpairs. The answer forgoodpairs is simply $$${n \choose 2} - z$$$. Time complexity is $$$O(n \ln n)$$$ due to the harmonic lemma.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":

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 accumulatorthe second part:

`f(c&sub)`

is direct formula using precomputed arraythe third part:

`f( (a | b) & c&sub )`

... well ... this is a recursive callFinally, 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.

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:

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

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.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://mirror.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?

"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

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.

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.

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

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

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

what is sweep algorithm mentioned in C?

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 countTake a look at my solution, it should be quite readable

okay got, it thanks

I solved this by compressing the ranges https://mirror.codeforces.com/contest/1884/submission/229383481

Interesting. At its core, it is similar to events:

`freq[mpp[l]]++;`

is like "start"`freq[mpp[r]+1]--;`

is like "end"but I think events are more intuitive and end up being less code

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

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

Take a look at Ticket 17117 from

CF Stressfor a counter example.thinks for you,I have known why I get wa.

I get AC finally! grateful to your help!

Can anyone explain what is sweep line algorithm?

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

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

You compute prefix/suffix sum. Something like this:

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

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.

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.

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;

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

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

How to solve B using Binary Search?

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

Nice editorial