hocky's blog

By hocky, history, 3 years ago, In English

1575A. Another Sorting Problem

Author: hocky
Developer: richiesenlia
Editorialist: hocky

Idea

1575B. Building an Amusement Park

Author: Panji
Developer: hocky, rama_pang
Editorialist: hocky, rama_pang

Idea

1575C. Cyclic Sum

Author: steven.novaryo
Developer: steven.novaryo
Editorialist: steven.novaryo

Idea

1575D. Divisible by Twenty-Five

Author: hocky
Developer: hocky
Editorialist: hocky

Idea
Short Solution

1575E. Eye-Pleasing City Park Tour

Author: steven.novaryo
Developer: rama_pang, hocky, steven.novaryo
Editorialist: rama_pang, steven.novaryo

Idea

1575F. Finding Expected Value

Author: rama_pang
Developer: rama_pang
Editorialist: rama_pang

Idea

1575G. GCD Festival

Author: yz_
Developer: hocky, yz_
Editorialist: rama_pang

Idea

1575H. Holiday Wall Ornaments

Author: hocky
Developer: Sakamoto, hocky
Editorialist: hocky, rama_pang

Idea

1575I. Illusions of the Desert

Author: JulianFernando
Developer: JulianFernando, hocky
Editorialist: hocky

Idea

1575J. Jeopardy of Dropped Balls

Author: richiesenlia
Developer: richiesenlia
Editorialist: hocky

Idea

1575K. Knitting Batik

Author: hocky
Developer: hocky
Editorialist: hocky

Fun fact
Idea

1575L. Longest Array Deconstruction

Author: yz_
Developer: steven.novaryo
Editorialist: steven.novaryo

Idea

1575M. Managing Telephone Poles

Author: yz_
Developer: steven.novaryo
Editorialist: steven.novaryo

Fun fact
Idea
  • Vote: I like it
  • +102
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +48 Vote: I do not like it

This contest is highly educational for me

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Hi can someone elaborate on the Divide and Conquer solution for problem L ?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    The DnC solution is more known as CDQ DnC. You can read more from the first search result of google. The link also contains a solution to the 3D LIS problem which can be applied in L.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please tell in the editorial of G, how to conclude

$$$\sum _{y} \phi (y) ( \sum _{i=1} ^{\lfloor \frac n x \rfloor} [a_{ix} mod y = 0])^{2}$$$
$$$from$$$
$$$\sum _{i=1} ^{\lfloor \frac n x \rfloor} \sum _{j=1} ^{\lfloor \frac n x \rfloor} \sum _{y \in d(a_{ix},a_{jx})} \phi (y)$$$
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it
    $$$\sum_{i = 1}^{\lfloor \frac{n}{x} \rfloor} \sum_{j = 1}^{\lceil \frac{n}{x} \rceil} \sum_{y \in d(a_{ix}, a_{jx})} \phi(y)$$$
    $$$\sum_{y} \phi(y) \sum_{i = 1}^{\lfloor \frac{n}{x} \rfloor} \sum_{j = 1}^{\lfloor \frac{n}{x} \rfloor} [a_{ix} \bmod y = 0 \land a_{jx} \bmod y = 0]$$$
    $$$\sum_{y} \phi(y) \sum_{i = 1}^{\lfloor \frac{n}{x} \rfloor} [a_{ix} \bmod y = 0] \sum_{j = 1}^{\lfloor \frac{n}{x} \rfloor} [a_{jx} \bmod y = 0]$$$
    $$$\sum_{y} \phi(y) \left(\sum_{i = 1}^{\lfloor \frac{n}{x} \rfloor} [a_{ix} \bmod y = 0]\right)^2$$$
»
3 years ago, # |
Rev. 2   Vote: I like it +24 Vote: I do not like it

I have solution for problem L in Square Root decomposition.

We divide the complete array into $$$SQRT$$$ blocks. For each block, we maintain, $$$dp[BLOCK][LEN]$$$, which shows maximum score we can achieve by using subsequence of size $$$LEN$$$ up-to $$$BLOCK$$$. How to update? We have 2 updates: $$$dp[BLOCK+1][LEN]$$$ can be updated from $$$max(dp[BLOCK][LEN-k])$$$ for all $$$k \leq SZ$$$ where $$$SZ$$$ is size of each $$$BLOCK$$$. To solve this, we can use maximum over all segments of size $$$SZ$$$, which is a standard problem using deque.

There is another transition, when subsequence increases in value inside the $$$BLOCK$$$ to be updated. For that we can use $$$sqrt(n)^{2}$$$ dp inside the $$$BLOCK$$$.

Code: 130653046

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

Can you provide your implementation for problem G? My solution had the same complexity but it got TLE.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here is my solution (same as editorial) 130644884

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    It seems that the many modulo operations are the reason for TLE, as it is a very expensive operation.

    Here is your code, but with the modulo operations removed. In custom invocation, this speeds up your code by 4-5 times. As a side note, the answer comfortably fits in long long data type (the maximum answer is less than $$$10^{16}$$$).

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

      Somehow I never realized that sum of $$$gcd(i, j)$$$ for $$$1 \le i, j \le n$$$ is not that large. Thanks for the answer.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

An easier way to achieve the second complexity in B is to binary search on $$$log(answer)$$$.

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

Can someone explain H a little bit better?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I'll explain to you the way I did it: (if you don't know kmp you need to learn it first cause it won't make sense otheriwse) dp[posInA][bPrefix][matches] is the minimum amount of characters you need to change in (1...posInA) in order to have 'matches' nr of ocurences of B in (1...posInA) AND the last 'bPrefix' elements of (1...posInA) in our changed A is the same as the first 'bPrefix' elements in B. Now for the transitions: We'll need to precalculate the prefix function for b like in kmp. And now we'll do the transitions forward-style. So we're in a dp[posInA][posInB][matches]. We can either make a[posInA + 1] a 0 or a 1. We try both, and now we need to calculate the new prefix and the new number of matches. If you know kmp the new prefix is gonna be pretty easy to understand, if it isn't clear from my code I can explain it to you. And the matches get increased by 1 whenever the prefix is m Code: https://mirror.codeforces.com/contest/1575/submission/132549880

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

      Thanks a lot for your explanation, I finally understand this dp!

      But I think your implementation works in $$$O(n^4)$$$ (actually it's divided by some big constant, but it's still $$$O(n^4)$$$).

      To see why, imagine a string $$$1111...111$$$, to calculate the transition when you change $$$i$$$-th symbol to $$$0$$$ for each $$$i$$$, you need $$$O(n^2)$$$ operations in total, because prefix function for this string looks something like $$$0, 1, 2, 3, \dots , m-1$$$. You calculating this transitions for each $$$k$$$ and for each $$$i$$$, so it's $$$O(n^2*n^2) = O(n^4)$$$

      The solution here is for each $$$pre$$$ calculate transition first and then for each $$$k$$$ update your $$$dp$$$, because $$$pre$$$ for each $$$k$$$ will be the same.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Okay, tell me if I'm wrong but I actually think it softens to n^3. Even though one transition might be o(n), that means the newPrefix is gonna be 0. And now the next prefix can only increase by one. It's the same reasoning as to why KMP is o(n), that pre can only increase by 1 every step and every extra operation necessarily decreases it. I think a really important part is that I check if a dp state is valid before I calculate off of it.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It seems that checking if a dp state is valid gives $$$O(n^3)$$$.

          Sorry, I didn't pay much attention to this line of code.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does classic LIS really work for L? it's not really clear how to compare pairs (a[i], i-a[i]). if we're using dp[i]-> min pair which the sequence of length i ends in.

Also I tried using 2D BIT and I'm getting TLE 3. Would be nice to know what the author had in mind by "standard LIS algorithm"

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You just compare pairs the normal way :think:. First priority first element, then second element if first element equal.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That doesn't work because we need both components of the pair to increase simultaneously

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

    Yes it works, editorial doesn't really explain clearly.

    You need to find maximum length of subsequence of pairs with three conditions to be fulfilled. $$$i<j$$$ and $$$a[i]<a[j]$$$ and $$$i-a[i]<=j-a[j]$$$. Notice that $$${2}^{nd}$$$ and $$${3}^{rd}$$$ inequality automatically implies $$${1}^{st}$$$ inequality. So, ignore the $$${1}^{st}$$$ inequality, and focus on $$${2}^{nd}$$$ and $$${3}^{rd}$$$.

    Now imagine a sequence $$$b$$$ such that $$$b[a[i]]=i-a[i]$$$ and if $$$b[j]$$$ has no value, then $$$b[j]=-INF$$$. Just find the $$$L.I.S$$$ of this sequence and you're done! Essentially just image $$$a[i]$$$ as the index of some sequence with values $$$i-a[i]$$$.

    You can also imagine "index" as $$$i-a[i]$$$ with "values" $$$a[i]$$$, however, in case of duplicate indexes, just place element with lower "value" to the left.

    Here's my code btw: https://mirror.codeforces.com/contest/1575/submission/161134216

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem G:

What is the process of thinking that will lead to such a solution ? I mean I knew the key idea for the solution but it never occurred to me to use Euler function here

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For F there's a closed $$$O(n)$$$ formula without convolution or other polynomial product tricks.

Fix $$$n, k$$$, and consider a tuple of multiplicites of non-randomized entries $$$C$$$, put $$$s = \sum {c \in C}$$$. Define $$$F(C) = n\left( - H_s + \sum_{c \in C} \sum_{j = 1}^c \frac{k^{j - 1} {c \choose j}}{j {s \choose j}}\right)$$$, where $$$H_s = \sum_{i = 1}^s \frac{1}{i}$$$. Then the answer is $$$F((n)) - F(C)$$$, where $$$C$$$ is the given multiplicities tuple.