### Serval's blog

By Serval, history, 14 months ago,

### 1789A - Serval and Mocha's Array

Idea & Preparation: Bazoka13

Tutorial

### 1789B - Serval and Inversion Magic

Idea & Preparation: Bazoka13

Tutorial

### 1789C - Serval and Toxel's Arrays

Idea & Preparation: Toxel

Tutorial

### 1789D - Serval and Shift-Shift-Shift

Idea & Preparation: Toxel

Tutorial

### 1789E - Serval and Music Game

Idea & Preparation: Serval

Tutorial

### 1789F - Serval and Brain Power

Idea & Preparation: Serval

Tutorial
• +125

| Write comment?
 » 14 months ago, # |   +18 E is best problem
•  » » 14 months ago, # ^ |   +6 Found E very interesting, nice math trick which is very expandable and practical. Many problems use similar idea of piecewise algorithms.
 » 14 months ago, # |   +46 In A complexity is $O(n^2 \log C)$, or you can check that $gcd \le 2$ in $O(1)$ somehow?In F to estimate $w_3$ we can consider the following bijection: let's take $n$ white balls and 5 black balls and put them in a linear order. White balls will denote letters of the string, 2nd and 4th black balls will denote where we split our string in 3 parts, and 1st/3rd/5th black balls will denote where in each of 3 strings we stay in DP. Thus there is a bijection between orders of balls and all DP states over all ways to split the string into 3 parts (actually we allow splits with empty parts, so it's even a bit smaller than this). The number of ball orders is $\binom{n+5}{5} = \frac{n^5}{5!} + O(n^4)$, thus $w_3 = \frac{1}{120}$
•  » » 14 months ago, # ^ |   +14 Thanks for sharing! I'll fix the typo in A. :)
• »
»
»
14 months ago, # ^ |
Rev. 7   +17

It's possible to solve it fastly.

#### How to Quickly Calculate the GCD in E (Bonus) and A

Bonus of E: The only algorithm costing $\omega(s_n)$ in the official solution is calculating GCD. However, we can calculate $\gcd(x,s_n)$ for all $x\in[1,s_n]$ in $\Theta(s_n)$:

since $\forall x,y\in \mathbb Z$ satisfying $\gcd(x,y)=1$ $, gcd(xy,s_n)=gcd(x,s_n)\cdot gcd(y,s_n)$ (this property is also called "Multiplicative"), we can use Euler's sieve to calc it in $\Theta(s_n)$, solving the bonus of E.

Bonus of A: there's a well-known tech that can also solve A in $O(\text{SIZE})$ precalc and $O(1)$ per query (where $\text{SIZE}=\max{a_i}$ and the number of pairs of GCD we query is $\frac{Tn(n-1)}{2}$ in this problem). You can solve this problem (on a mainland Chinese OJ, Luogu).

•  » » » » 14 months ago, # ^ |   0 But in this case, O(SIZE+K) will be of the order of 10^6 per case, so won't it be slower than O(n^2) as n<=100?
•  » » » » » 14 months ago, # ^ | ← Rev. 4 →   +14 It's my typo. Initialization only runs once. Fixed&thx.In fact we only run initialization like a Euler's sieve to reduce the range to $\sqrt {\text{SIZE}}$ and precalc $\gcd(a,b)$ for all $a,b\in[1,\sqrt {\text{SIZE}}]$(Like the bonus of E) within $O(\text{SIZE})$ and we can query any $a,b\in[1,\text{SIZE}]$ in $O(1)$.
 » 14 months ago, # |   0 Is it true that someone has O(n) on D or are those just rumors?
 » 14 months ago, # |   +8 I didn't understand the concept of lb(a) and hb(a) in the editorial of D. Is it referring to the left-most and right-most bits of a? Sorry for the confusion.
•  » » 14 months ago, # ^ |   0 $lb(x)$ is lowest bit of $x$$hb(x)$ is highest bit of $x$
•  » » » 14 months ago, # ^ |   0 What does it mean by lowest bit of x or highest bit of x? Is it the count of 0's and 1's in x?
•  » » » » 14 months ago, # ^ |   0 No, it is index of leftmost 1 and rightmost 1
•  » » » » » 14 months ago, # ^ |   0 Oh, I get it now. Thanks a lot.
•  » » » 5 months ago, # ^ |   0 $lb(x)$ means $lsb(x)$ ? bcoz if we do +1 we need to which direction are we moving ? and $lb(x)$ doesn't give information IMO
 » 14 months ago, # |   +15 DP solution for problem C.Let $cnt(i, k)$ be the number of times the number $k$ appears in the arrays $A_0, A_1, \ldots, A_i$ and let $dp[i]$ the sum of the values of the concatenations $(A_i, A_j), 0 \leq j < i$.When we go from the iteration $(i-1)$-th to the $i$-th only changes the number $a_p$ to $v$, so, in the transition $dp[i-1] \rightarrow dp[i]$ we only have to analyze how $a_p$ and $v$ affect the result.Assume that the change is not yet made in $A_i \ (A_i = A_{i-1})$, then $dp[i] = dp[i - 1] + n$ (because $(A_i, A_{i-1})$ are equal, so just add $n$ to $dp[i]$). The change is made and for each $a_p$ in ${A_0, A_1, \ldots, A_{i-1}}$ we add $+1$ to $dp[i]$ (because $a_p$ doesn't exist in $A_i$), and for each $v$ in ${A_0, A_1, \ldots, A_{i-1}}$ we substract $-1$ from $dp[i]$.So, the transition is: $dp[0] = 0, \ \ dp[i] = dp[i - 1] + n + cnt(i - 1, a_p) - cnt(i - 1, v), \ 1 \leq i \leq m$And the answer is: $ans = \sum_{i=1}^m dp[i]$
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 !
 » 14 months ago, # |   +26 To share some random stuff as a tester: The original contest had only current ABCEF, D is newly added to alleviate the gap between C and E (well, as you already found, D is harder than expected, but it would be worse with respect to the gap if the next problem of C were E). The original statement of E is horribly longer than current's (maybe more than two times longer). For me the current version is way too better (maybe already the best for such a in fact complicated problem). Personally I like the problem F and C is quite an educational problem (which I'd like to recommend every newbies to give it a shot, definitely will they learn a lot).
 » 14 months ago, # |   0 Why the interval in problem E does not contain ${uk}$, where u is an integer? we can let p_i be u and q be 0.
•  » » 14 months ago, # ^ |   0 I think the tutorials means that those intervals are illegal.An interval is illegal means that if $s_i\in[l, r]$, $i$ will not be counted into $f(x)$.
 » 14 months ago, # |   0 I don't know what $\frac{m(m + 1)}{2} - \frac{(m−count_x)(m−count_x+1)}{2}$ meant in the interpretation of the problem C.
•  » » 14 months ago, # ^ |   0 m(m+1)/2 is the amount of all concatenated arrays. And (m−countx)(m−countx+1)/2 is the amount of all concatenated arrays which don't have x. in m arrays we have countx arrays that have x .If x doesn't appear in concatenated arrays , the 2 arrays must be chosen from (m-countx) arrays which don't have x.
 » 14 months ago, # |   +10 In problem C shouldn't we add $m+1-appear_x$ to $count_x$ after all operations if $appear_x != -1$.
•  » » 14 months ago, # ^ |   +23 Sorry for the typo. It is fixed now. :3
 » 14 months ago, # |   +15 I think that $m−appear_x$ in the solution of problem c is wrong, I think it is $m-appear_x+1$.If you write $m-appear$ in the code, it will be WA.
•  » » 14 months ago, # ^ |   +18 Sorry for the typo. Fixed now. :3
 » 14 months ago, # |   +10 Problem C After all operations, for all x, add $m − appear_x$ to $count_x$ if $appear_x$ is not −1. Shouldn't it be $m + 1 - appear_x$ ?!! I have been confused about it for hours!
•  » » 14 months ago, # ^ |   +23 Sorry for the typo. It is fixed now. :3
 » 14 months ago, # |   0 In Problem D step 4, "we may logical left shift a by i-hb(a) bits to erase it", should it not be i-lb(a) bits instead?
•  » » 14 months ago, # ^ |   +5 Sorry for the typo. Fixed now. :3
 » 14 months ago, # |   0 In problem D, my solution is consistently giving wrong answer on case 113 of test case 4. It says the sequence of operations doesn't give b. Kindly help
 » 14 months ago, # |   -8 I have a stupid dp solution of C
 » 14 months ago, # | ← Rev. 3 →   0 i don't understand problem C's solution.Is there anybody have understandable solution?
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 every element is contributing in this fashion , for the first occurrence it is contributing m to the answer(as it would be a unique element for the next m arrays) , then in next occurrence it would contribute (m-1) (it would be unique for the next (m-1) arrays) and this would continue , so we just need to count the frequency of every element , as the range is only till n+m we can count them in a frequency array and then we just need to sum up from m + (m-1) + (m-2) .... + (m- count + 1) for each element in the frequency array
 » 14 months ago, # |   0 During modifications, Toxel guaranteed that the elements of each array are still pairwise distinct after each operation.does this means that the intersection of all the elements of the array is a null set? or the intersection of the elements of a particular array is a null set?
•  » » 14 months ago, # ^ |   0 2nd one
 » 14 months ago, # |   +8 Found this for problem f https://www.youtube.com/watch?v=VBke0Ooe1ys&t=7s
 » 13 months ago, # |   0 E is fantastic!!!
 » 13 months ago, # |   0 There is a very slight mistake in the tutorial of Problem E: By observation, these $s_i$ are in one of the following $k - 2$ intervals: Actually there are $k - 1$ intervals. But, any way, it's insignificant. :D
 » 5 months ago, # |   0 Great
 » 5 months ago, # |   0 can anyone tell what bug is in this code
 » 13 days ago, # |   0 Thought my C concept is right, but couldn't implement it out. I can't manage to handle the situation where a position is modified more than twice with a same value.
 » 6 hours ago, # |   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } if you struggling to understand solution of problem C then you can read my explanation My approachthis is my fav problem now.since it look quite complex when we consider numbers and maintain their count, the way i visualised the problem was below. lets consider bitmask representation of array for better understanding: our orignal array was [ 1 , 2 , 3 ] and through out the queries we will some elements that [ 4 , 5 ]so total set of numbers are [ 1 , 2 , 3 , 4 , 5 ]consider their index in this full set is the id of each element, so orignal array bitmask is: 11100after changes bitmask will look like this11100 -> orignal 01110 -> 1st move 00111 -> 2nd moveso now we can see that even if the number is present in two array's it will only contribute once, and if for a pair there is no one it will contribute zero in this case.for each bit index we can count,b-> numbers of 0's we have total pariring is: m*(m+1)/2 but if those pairings have both zero's then they dont contribute anything. we need to remove themthat is: m*(m+1)/2 - b*(b-1)/2; the only problem now is how to mainting the count for each bit, as there can be 1e5 numbers in array if we do it naively then it would take N*M time which is we dont not wantso we can break numbers into two groups, zero_set — those numbers whose bit is currently zero one_set — those numbers whose bit is currently one [ i did not use it my implementation it is just for understanding ]any move only change one number in each group that is they switch places, so we can maintain the count the of zero's by mainting the in time and out time of number to and from zero set Look at my code for reference: 256787804