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

Автор hocky, история, 3 года назад, По-английски

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
  • Проголосовать: нравится
  • +102
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +48 Проголосовать: не нравится

This contest is highly educational for me

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится +32 Проголосовать: не нравится
    $$$\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 года назад, # |
Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

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 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Here is my solution (same as editorial) 130644884

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain H a little bit better?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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://codeforces.net/contest/1575/submission/132549880

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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://codeforces.net/contest/1575/submission/161134216

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.