Thanks for the participation!

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

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

1 | tourist | 3803 |

2 | jiangly | 3707 |

3 | Benq | 3627 |

4 | ecnerwala | 3584 |

5 | orzdevinwang | 3573 |

6 | Geothermal | 3569 |

6 | cnnfls_csy | 3569 |

8 | Radewoosh | 3542 |

9 | jqdai0815 | 3532 |

10 | gyh20 | 3447 |

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

1 | awoo | 163 |

2 | maomao90 | 160 |

3 | adamant | 157 |

4 | maroonrk | 155 |

5 | -is-this-fft- | 150 |

6 | Petr | 148 |

6 | SecondThread | 148 |

8 | atcoder_official | 147 |

9 | TheScrasse | 145 |

9 | nor | 145 |

Thanks for the participation!

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of Codeforces Round 830 (Div. 2)

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/15/2024 05:58:20 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Nice.

SpoilerWow, so fast editorial, thanks!

As a tester, I solved problem E with complexity $$$O(100(n+q)\log n)$$$: write the formula as $$$f_i=a_ib_i/\gcd^2(a_i,b_i)$$$. Let's maintain the answer by maintaining segments of same $$$a$$$-s together. It's easy to see that the segments only change $$$O(n+q)$$$ times. In queries, we specially manage the segments the query crosses (i.e. it contains $$$l$$$ or $$$r$$$) and the segments in the middle can be maintained with segment tree.

Now, we essentially have to calculate $$$f(l,r,x)=\max_{l\le i\le r} x\cdot b_i/\gcd^2 (x,b_i)$$$ for $$$O(n+q)$$$ times. Let's enumerate all divisors of $$$x$$$ and try it as a candidate for $$$\gcd(x,b_i)$$$. It's easy to see that we should select the maximum $$$b_i$$$ that is a multiple of $$$x$$$. To maintain largest $$$b_i$$$ in a segment that is a multiple of $$$x$$$, we can use a sparse table or a segment tree for each $$$x$$$. The sum of sizes of the tables is $$$100n$$$, since numbers in $$$[1,50000]$$$ have at most 100 divisors.

177649266

queryforces

How to solve C1? I understand f(l,r) <= f(l,r+1), but I am not getting how binary search will help here

finally got it.

Note= maximum cost will always be

`sum(arr) - xor_sum(arr)`

. because of`f(l,r) <= f(l,r+1)`

.So we need to find the minimum segment length which will give us this cost.`i`

find the nearest index`j`

for which`f(i,j) == cost`

.My solution is not clean. Especially binary search part but still :=; 177667352

Since $$$f(l,r) <= f(l,r+1)$$$ that means that for some $$$1 <= i <= n$$$ the maximum value of $$$f(i,r)$$$ will be for $$$r = n$$$ since the function is increasing. Now the problem asked for the minimum segment therefore we need to find if there is some $$$r$$$ such that $$$i <= r <= n$$$ such that $$$f(i,r) = f(i,n)$$$ and it should be the minimum one, so therefore to find the minimum $$$r$$$ we can use binary search.

I think you should explain time complexities properly instead of ending the editorial with

It might not be obvious to some of us.

74TrAkToR can you give a proper time complexity analysis for D1?

Can someone explain D2 problem, I can't understand, the author explanation.

Same, solved it but I can't understand the author's intended solution as well.

Alternative solution for E (it's just worse than what's in the editorial, but wotever, it got AC):

To do range assign and point get in A, a VEBTree over "important" indices can be used to get O(log log n) updates and queries.

Divide the arrays into blocks of size R (constant we will fix later). Then inside each block, compute for every value $$$\leq 5 \cdot 10^4$$$ what is the smallest multiple of that value which occurs in the range.

Then to compute the answer when an entire block gets set to a value $$$v$$$, it's $$$\min(\texttt{smallest_multiple}[d] \cdot v / d^2 \enspace \vert \enspace d \vert v)$$$

When a an update or query touches but doesn't cover an entire block, just brute force.

$$$O(Rq \log \log n + nqd/R)$$$ where $$$d$$$ is the largest number of factors a number can have, which is something like $$$128$$$ for numbers this small. I chose $$$R=400$$$ from trial and error instead of calculating what block size would make sense.

submission

Best solution

Chadnus HegdahlMagnus

ChadahlStill don’t get A.. If a[n] mod n != 0, then why can we just check if gcd(g, n)? I mean if a[n] cannot be changed to n, then why checking gcd(g, n) is correct?

Sorry for my poor English in advance.

Once you apply an operation on index N you are sure that it will contain only prime factors of number N. Similarly you can see for N-1. Now since N and N-1 won't have any common prime factors gcd(gcd(a[N],N),gcd(a[N-1],N-1)) also won't have any common prime factors. So the value gcd(gcd(a[N],N),gcd(a[N-1],N-1) is guaranteed to be 1.

Got it！Thanks a lot

I still cant understand Question B, can somebody explain?

In problem E, formula answer_x = min(answer_(x/p) * p) is just plain wrong, even with d not equal to x.

Let n = 1, x = 4, b_1 = 8, p = 2. Then answer_x = lcm(x, b_1) / gcd(x, b_1) = lcm(4, 8) / gcd(4, 8) = 8 / 4 = 2. BUt answer_(x/p) = lcm(x/p, b_1) / gcd(x/p, b_1) = lcm(4/2, 8) / gcd(4/2, 8) = lcm(2, 8) / gcd(2, 8) = 8 / 2 = 4. answer_x is not equal to p * answer(x/p), actually, answer(x/p) > answer_x.

Please show me where I am wrong.

Managed to solve both C2 and D2, lost 16 rating.

The complexity analysis for D1 and D2 are not so obvious for me. Can someone maybe provide a better explanation?

`unordered_set/map`

and`gp_hash_table`

are uphacked.74TrAkToR

You even didn't hack $$$\mathcal O(n^2)$$$ solutions!!!

177850677

In editorial of D1,

"Note that if k is not one of the largest divisors of x, then x/k becomes greater than q"Why?

Does anyone have a correct proof to the solution of D1?

Can anybody explain problem C2? I don't understand what does $$$A$$$ means in the editorial.

$$$A$$$ means the maximum value in array $$$a$$$.

thus the value of the function will become smallerCan you explain this? How the function value becomes smaller, when it always increases or stays the same if we add a new element?

(My English may not be so good. ) I think it might mean this:

When we're dealing with the query $$$[L,R]$$$, a simple and slow way is to calculate every nearest $$$r$$$ for all $$$l \in [L,R]$$$. However, when the value of $$$[l,R]$$$ is less than the value of $$$[L,R]$$$, we can just end and print the answer, because $$$\forall i \in [l,R]$$$, there's no subsegment of $$$[i,R]$$$ can affect the answer since we want to maximize value first.

Then consider the time we have calculated before we break, if and only if when we delete the current first element $$$a_{now}$$$, the value of $$$[now+1,R]$$$ is less than $$$[now,R]$$$. And the reduction of the value is because, "at least one of the bits of $$$a_{now}$$$ occurs in $$$xor(now+1,r)$$$". The worst case is the first $$$\log A$$$ elements of $$$[L,R]$$$ have one bit in binary representation respectively and the bit every element have is pairwise distinct. So we have time complexity $$$O(q \log A \log n)$$$ if we use binary search.

Upd: There's something I forgot just now(

The worst case is that, the first $$$\log A$$$ elements

such that $$$\ne 0$$$of $$$[L,R]$$$ ......(the condition)So we should check the first $$$\log A + 1$$$ elements

such that $$$\ne 0$$$to get the answer.If you're confused because of this, I'm sorry.

C1 can be solved by brute force with optimization of skipping zeros with

`O = O(15*15) = 225`

, since any non-zero element is obliged to reduce the number of bits in the current xor. Thus C2 can be solved by adding a segment tree (to find the xor of segment) with`O = (225+log(n))*n`

.xor (l, r) = xor(1, r) ^ xor(1, l — 1), so you don't need to use segment tree. You can find xor with O(1) with prefix xor.

What does Hack verdict 'Unexpected verdict' mean? Problem E's hacks have so many this type.

In the system there are solutions that are marked as correct. If a hack is able to break one or more of those solutions (by either TLEing one of them, RTEing one of them, or making their output inconsistent/wrong) then the verdict of the hack will say

`Unexpected verdict`

.The times when I've triggered

`Unexpected verdict`

in the past, the most common reason is that I TLEd one of the Python solutions from the problem setters.This is related to the complexity analysis of $$$D1$$$ and $$$D2$$$:

If we have arrays $$$arr_1$$$ and $$$arr_2$$$, each of them has $$$N$$$ distinct values, where $$$1\le N \le 10^5$$$ and $$$1\le arr_1[i], arr_2[i]\le A_{max}$$$.

Then for each $$$arr_1[i]$$$, we iterate on its positive multiples in ascending order until the first multiple not in $$$arr_2[i]$$$. If $$$A_{max}=N$$$, then the total number of iterations can be calculated as $$$N\cdot \sum_{i=1}^{N}{\dfrac{1}{i}}=N\cdot H(N)=N\cdot log(N)$$$.

If $$$A_{max}$$$ is an arbitrary value larger than $$$N$$$, e.g., $$$10^{18}$$$, is there a way to prove the upper bound on the total number of iterations?

has anybody solved C1/C2 with segment tree ? i would like to see how the segments are Merged and stored

In C1 and C2, if I have a test like this : 0 8 2 0 and L = 1, R = 4

My output was "2 2" and Jury output was "1 1" and I got WA while segment [2,2] and [1,1] have the same length and f(l,r).

Could anybody explain to me why i'm WA, please :(

Problem D2 : I couldn't understand the last part. How we can recalculate these set in the case of an add/remove operation? Can anyone explain? TIA

74TrAkToR, In the editorial of D2 shouldn't it be:

*

then we should already have added approximately$$$\sum\limits_{i = 1}^t\frac{x}{k_i}$$$.At second to last line, since we are iterating over t divisors of x from $$${k_1}$$$ to $$${k_t}$$$.

Can someone please explain about problem E: how do we count answers for each x in blocks? Would apreciate it

Tried hard in D2 problem and at last accepted. I can't believe it was 2400 rated problem.

I have an alternate solution for D2 that uses sqrt optimization. Store a block of at max size $$$\sqrt n$$$ delete operations. For all queries run through all the erased numbers in the current block, if $$$x$$$ divides a number in the block ($$$b$$$) just min the answer you had kept previously with $$$b$$$.

If the block reaches size $$$\sqrt n$$$, clear the block and run D1's solution from 0 for all currently stored queries. Complexity over queries amortized is $$$O(n \sqrt n \log(n) + n \log(n)) = O(n \sqrt n \log(n))$$$. Because the clear and reset operation runs at max $$$\sqrt n$$$ times the total time complexity of that is also the same $$$O(n \sqrt n \log n)$$$. Needed some

`gp_hash_table`

optimization to remove the $$$\log n$$$ factor and make it pass. 178023023Time limit on problem E is tooooooo tight. The overall complexity is still $$$\mathcal{O}(X\sqrt{X}\log X)$$$ where $$$X = 5 \times 10^4$$$. From the complexity perspective the fansy $$$\mathcal{O}(X\log \log X)$$$ optimization in the precalculation seems not necessary.

I've also tried a $$$\mathcal{O}(100n\log n)$$$ segment tree solution and it still can't pass the time limit.

Anyone got a solution to C1 using two pointers? Would help a lot! Thanks in advance!

I have

In fact,I don't understand problem B and this tutorial o(╥﹏╥)o

There needs to be a proof for the upper bound time complexity on D1

I agree

why this givving me TL for D1 ?

https://codeforces.com/contest/1732/submission/214043354

Time complexity pf problem D1 should be O(qlogq). explanation : consider first q queries of insertion of 1 to q numbers and then for next q queries getting mex of 1 to q numbers . Insertion of 1 to q numbers takes O(qlogq) time . for finding mex of each element from 1 to q it will take (q/1+q/2+q/3 +q/4+....q/q)==qlogq Total time complexity : O(qlogq)+O(qlogq)==O(qlogq)

Honestly this is a very funny round if your rating does not depend on it.

The formal proof for D2 is really tedious, I could not normally prove it.

I passed E with a constant equal to 105, if it is 100 or 110 it TL's.

This is so fucking funny it is unbelievable.

Can someone please explain the proof for time complexity for problem D1. The editorial says

If k is not one of the largest divisors of x, then x/k becomes greater than q. Therefore, this solution will work quite quicklyThere could be case like x = 10^6 and y = 10. This could run for 10^5 times.

I did B quite differently,by iterating the string backwards and locating the 1st different element and doing the operation on that to make it equal to its predecessor and so on until i reach the "good" index from the starting,the good index from the starting would be the ind,until which string is already perfect.