Serval's blog

By Serval, history, 14 months ago, In English

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
  • Vote: I like it
  • +125
  • Vote: I do not like it

| Write comment?
»
14 months ago, # |
  Vote: I like it +18 Vote: I do not like it

E is best problem

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

    Found E very interesting, nice math trick which is very expandable and practical. Many problems use similar idea of piecewise algorithms.

»
14 months ago, # |
  Vote: I like it +46 Vote: I do not like it

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, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Thanks for sharing! I'll fix the typo in A. :)

    • »
      »
      »
      14 months ago, # ^ |
      Rev. 7   Vote: I like it +17 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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   Vote: I like it +14 Vote: I do not like it

          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, # |
  Vote: I like it 0 Vote: I do not like it

Is it true that someone has O(n) on D or are those just rumors?

»
14 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$lb(x)$$$ is lowest bit of $$$x$$$

    $$$hb(x)$$$ is highest bit of $$$x$$$

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

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No, it is index of leftmost 1 and rightmost 1

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

      $$$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, # |
  Vote: I like it +15 Vote: I do not like it

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, # |
  Vote: I like it +26 Vote: I do not like it

To share some random stuff as a tester:

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

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

  3. 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, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +10 Vote: I do not like it

In problem C shouldn't we add $$$ m+1-appear_x $$$ to $$$count_x$$$ after all operations if $$$appear_x != -1 $$$.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Sorry for the typo. It is fixed now. :3

»
14 months ago, # |
  Vote: I like it +15 Vote: I do not like it

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, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Sorry for the typo. Fixed now. :3

»
14 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Sorry for the typo. It is fixed now. :3

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Sorry for the typo. Fixed now. :3

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it -8 Vote: I do not like it

I have a stupid dp solution of C

»
14 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

i don't understand problem C's solution.Is there anybody have understandable solution?

  • »
    »
    13 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it +8 Vote: I do not like it
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

E is fantastic!!!

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

Great

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

can anyone tell what bug is in this code

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

if you struggling to understand solution of problem C then you can read my explanation

My approach

Look at my code for reference: 256787804