hocky's blog

By hocky, history, 2 months 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: Zap
Developer: hocky, Zap
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: Zap
Developer: steven.novaryo
Editorialist: steven.novaryo

Idea

1575M. Managing Telephone Poles

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

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

»
2 months ago, # |
  Vote: I like it +48 Vote: I do not like it

This contest is highly educational for me

»
2 months 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 ?

  • »
    »
    2 months 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.

»
2 months 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)$$$
  • »
    »
    2 months 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$$$
»
2 months 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

»
2 months 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.

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

    Here is my solution (same as editorial) 130644884

  • »
    »
    2 months 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}$$$).

    • »
      »
      »
      2 months 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.

»
2 months 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)$$$.

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

Can someone explain H a little bit better?

  • »
    »
    7 weeks 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://codeforces.com/contest/1575/submission/132549880

    • »
      »
      »
      7 weeks 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.

      • »
        »
        »
        »
        6 weeks 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.

        • »
          »
          »
          »
          »
          6 weeks 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.

»
6 weeks 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"

  • »
    »
    6 weeks 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.

    • »
      »
      »
      6 weeks 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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do problem J with DSU as explained in the editorial?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone share the editorial for it?

»
3 weeks 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