Codeforces Round #904 (Div. 2) Editorial

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
43:39:42
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

Codeforces Round #904 (Div. 2) Editorial

Автор 74TrAkToR, история, 13 месяцев назад, перевод, По-русски

Спасибо за участие!

Tutorial is loading...

Разбор задач Codeforces Round 904 (Div. 2)

74TrAkToR
13 месяцев назад
102

Комментарии (80)

Показать архивные | Написать комментарий?

RlKKA

13 месяцев назад, # |

← Rev. 2 →

+22

D can also be solved by using GCD convolution.

→ Ответить

lyh3.14

13 месяцев назад, # ^ |

That's true

→ Ответить

nns2009

13 месяцев назад, # ^ |

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?

→ Ответить

luanmenglei

13 месяцев назад, # ^ |

← Rev. 2 →

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.

→ Ответить

Furlute

12 месяцев назад, # ^ |

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

→ Ответить

chromate00

13 месяцев назад, # |

← Rev. 2 →

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

→ Ответить

EnDeRBeaT

13 месяцев назад, # ^ |

and their multiples

damn, how did i not see that D:

→ Ответить

chromate00

13 месяцев назад, # ^ |

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

→ Ответить

sahaun

13 месяцев назад, # ^ |

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

→ Ответить

jerefigo

13 месяцев назад, # ^ |

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

→ Ответить

chromate00

13 месяцев назад, # ^ |

← Rev. 3 →

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.

→ Ответить

Manoj07

13 месяцев назад, # ^ |

← Rev. 2 →

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!

→ Ответить

yyashm1491625

11 месяцев назад, # ^ |

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

→ Ответить

jdkyx

8 месяцев назад, # ^ |

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

→ Ответить

dv_0101

10 месяцев назад, # ^ |

What is your logic behind code? Thanks

→ Ответить

sunup15

4 месяца назад, # ^ |

Your text to link here... I'd like to know why my code always times out, obviously I've restricted it to be able to output -1 directly as soon as the second pointer reaches n. Why on earth is this causing a timeout! Can you help me to solve the error of my answer?

→ Ответить

sunup15

4 месяца назад, # ^ |

Are you discussing question B?

→ Ответить

chromate00

4 месяца назад, # ^ |

← Rev. 2 →

Your linked solution will build a new bitset sized 200005 at most $$$t=10^4$$$ times, leading to $$$2\cdot 10^9$$$ bits allocated (of course, they are constantly freed, but they contribute to runtime).

→ Ответить

thangdz2k7

13 месяцев назад, # |

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

→ Ответить

Yumesekai239

13 месяцев назад, # |

-7

what a hard div 2!

→ Ответить

Izuku__Midoriya

13 месяцев назад, # |

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

→ Ответить

AhtheUncertainty

13 месяцев назад, # ^ |

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?

→ Ответить

hasnain_bashir_

13 месяцев назад, # ^ |

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

→ Ответить

AhtheUncertainty

13 месяцев назад, # ^ |

← Rev. 3 →

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!

→ Ответить

madorz

13 месяцев назад, # ^ |

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

→ Ответить

AprLsity

13 месяцев назад, # ^ |

excellent explaination！thanks！

→ Ответить

UP84

13 месяцев назад, # |

← Rev. 2 →

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

→ Ответить

NegativeElo

13 месяцев назад, # ^ |

← Rev. 2 →

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

→ Ответить

_Frust

13 месяцев назад, # |

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

→ Ответить

Aliyyiakbar

13 месяцев назад, # ^ |

why use trees tho

→ Ответить

_Frust

13 месяцев назад, # ^ |

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

→ Ответить

Aliyyiakbar

13 месяцев назад, # ^ |

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

→ Ответить

Utsav82

13 месяцев назад, # |

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

→ Ответить

KK_1729

13 месяцев назад, # ^ |

we are only selecting segments that contain x

→ Ответить

Entropy.

13 месяцев назад, # ^ |

Consider this test :

2 3

1 1

3 3

Doesn't the minimum occur in 2-2?

→ Ответить

Utsav82

13 месяцев назад, # ^ |

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.

→ Ответить

copyPasteCoder

13 месяцев назад, # ^ |

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

→ Ответить

nectarl

13 месяцев назад, # ^ |

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

→ Ответить

italianDefence

13 месяцев назад, # |

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

→ Ответить

sadhwanyash6

13 месяцев назад, # |

← Rev. 2 →

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

→ Ответить

power_verse

13 месяцев назад, # |

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

→ Ответить

nns2009

13 месяцев назад, # ^ |

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

→ Ответить

luanmenglei

13 месяцев назад, # |

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

→ Ответить

adonkey

13 месяцев назад, # |

← Rev. 3 →

+10

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

→ Ответить

UP84

13 месяцев назад, # |

Why this code gives wrong answer for problem D — 229186378

→ Ответить

CaptLevi

13 месяцев назад, # ^ |

← Rev. 2 →

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

→ Ответить

CaptLevi

13 месяцев назад, # ^ |

hey check this test case

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

→ Ответить

nns2009

13 месяцев назад, # |

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.

→ Ответить

chromate00

13 месяцев назад, # ^ |

← Rev. 2 →

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

→ Ответить

nns2009

13 месяцев назад, # ^ |

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.

→ Ответить

chromate00

13 месяцев назад, # ^ |

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.

→ Ответить

nns2009

13 месяцев назад, # ^ |

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!

→ Ответить

nns2009

13 месяцев назад, # ^ |

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.

→ Ответить

chromate00

13 месяцев назад, # ^ |

← Rev. 5 →

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.

→ Ответить

nns2009

13 месяцев назад, # ^ |

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.

→ Ответить

nns2009

13 месяцев назад, # ^ |

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

→ Ответить

chromate00

13 месяцев назад, # ^ |

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.

→ Ответить

nns2009

13 месяцев назад, # ^ |

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?

→ Ответить

chromate00

13 месяцев назад, # ^ |

← Rev. 2 →

"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

→ Ответить

nns2009

13 месяцев назад, # ^ |

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.

→ Ответить

Entropy.

13 месяцев назад, # ^ |

← Rev. 2 →

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

→ Ответить

chromate00

13 месяцев назад, # ^ |

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

→ Ответить

EvenToWorldFinal

13 месяцев назад, # |

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

→ Ответить

rashid_aziz

13 месяцев назад, # |

what is sweep algorithm mentioned in C?

→ Ответить

nns2009

13 месяцев назад, # ^ |

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

→ Ответить

rashid_aziz

13 месяцев назад, # ^ |

okay got, it thanks

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

→ Ответить

nns2009

13 месяцев назад, # ^ |

← Rev. 2 →

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

→ Ответить

OobugoO

13 месяцев назад, # |

← Rev. 2 →

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)

→ Ответить

variety-jones

13 месяцев назад, # ^ |

Take a look at Ticket 17117 from CF Stress for a counter example.

→ Ответить

OobugoO

13 месяцев назад, # ^ |

← Rev. 2 →

thinks for you,I have known why I get wa.

→ Ответить

OobugoO

13 месяцев назад, # ^ |

I get AC finally! grateful to your help!

→ Ответить

f20202065

13 месяцев назад, # |

Can anyone explain what is sweep line algorithm?

→ Ответить

nns2009

13 месяцев назад, # ^ |

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

→ Ответить

dreameater69

13 месяцев назад, # |

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

→ Ответить

nns2009

13 месяцев назад, # ^ |

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

→ Ответить

silxi

13 месяцев назад, # |

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.

→ Ответить