lucifer1004's blog

By lucifer1004, history, 3 weeks ago, In English

Google Kick Start 2021 Round B Tutorial

中文版 | Chinese version

Here are my solutions to Google Kick Start 2021 Round B. Some of them (C & D) are not optimal, albeit they passed all the test cases.

Problem A — Increasing Substring

We simply go ahead and try appending the current letter after the last letter.

Complexity:

  • Time complexity is $$$\mathcal{O}(|S|)$$$.
  • Space complexity is $$$\mathcal{O}(|S|)$$$.
Code (C++)

Problem B — Longest Progression

For $$$N\leq3$$$, it is obvious that the answer is $$$N$$$.

For $$$N\geq4$$$, we can first calculate $$$l[i]$$$, which denotes the length of the longest arithmetic array from left till $$$i$$$ without making any changes, and $$$r[i]$$$, which denotes the length of the longest arithmetic array from right till $$$i$$$ without making changes.

Then we check each position $$$i$$$ to see if we could get a longer length by changing $$$a[i]$$$ so that we can:

  • combine $$$l[i-1]$$$ and $$$r[i+1]$$$
  • combine $$$l[i-1]$$$ and $$$a[i+1]$$$
  • combine $$$a[i-1]$$$ and $$$r[i+1]$$$

And the complexity:

  • Time complexity is $$$\mathcal{O}(N)$$$.
  • Space complexity is $$$\mathcal{O}(N)$$$.
Code (C++)

Problem C — Consecutive Primes

Solution I: Find the three primes $$$A<B\leq\sqrt{S}<C$$$ closest to $$$\sqrt{S}$$$

The official solution leverages the concept of the prime gap and is a very beautiful brute-force solution.

I would not repeat the prime gap part, but will instead talk about the primality test. In this problem, a naive $$$\sqrt{N}$$$ primality test is enough to pass, but we could do better with Miller-Rabin, which runs in $$$\mathcal{O}(K\log^3N)$$$ time.

Since $$$S\leq10^{18}$$$, the largest number we would need to check will be around $$$10^9$$$, in this case, $$$[2,7,61]$$$ would be enough to ensure the correctness of the primality test.

Code (C++)

Solution II: Find all primes and binary search

Since the test cases are bundled, we can also pass Test 3 if we use Euler sieve to generate all primes smaller than $$$\sqrt{\text{MAXN}}$$$ optimally, and then use binary search for each query. Note that we need to make $$$\text{MAXN}$$$ a bit larger than $$$10^{18}$$$ so that we will also generate the smallest prime that is larger than $$$10^9$$$.

Note that we need to use bitset instead of bool[] to save space.

And the complexity:

  • Time complexity is $$$\mathcal{O}(\sqrt{\text{MAXN}}+Q\log\frac{\sqrt{\text{MAXN}}}{\ln\sqrt{\text{MAXN}}})$$$.
  • Space complexity is $$$\mathcal{O}(\sqrt{\text{MAXN}})$$$.
Code (C++)

Problem D — Truck Delivery

The official solution uses the segment tree. However, we can also use the blocking technique to solve this problem.

We separate edges into blocks according to their limits $$$L_i$$$, and each block will have an optimal size of $$$\sqrt{N}$$$.

We first do a depth-first search to gather the information we need. That is, for each node, we would like to know the GCD value of all the edges whose limits are within the same block ($$$acc[i][j]$$$ in the code below), along the path from the root (capital city) to the current node. Also, we would like to know the previous edge ($$$last[i][j]$$$ in the code below) that has a limit that falls within a certain block, along the path.

For each query, we first determine the block $$$j$$$ that $$$W_i$$$ belongs to. Then we can safely calculate the GCD value of all the blocks that are smaller than $$$j$$$. For the $$$j$$$-th block, however, we need to check each edge to find out whether $$$L_k\leq W_i$$$, which can be done with the help of the $$$last$$$ array.

And the complexity:

  • Time complexity is $$$\mathcal{O}((N+Q)\sqrt{N})$$$, if the block size is set as $$$\sqrt{N}$$$. (In the code below, I used a constant block size of $$$500$$$ to avoid discretization.) Also, note that all $$$L_i$$$ are distinct, so each block with size $$$\sqrt{N}$$$ can contain at most $$$\sqrt{N}$$$ edges, which ensures the correctness of the time complexity.
  • Space complexity is $$$\mathcal{O}(N\sqrt{N})$$$.
Code (C++)
 
 
 
 
  • Vote: I like it
  • +60
  • Vote: I do not like it

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

Is blocking a algorithmic concept, or you just used it explain the algorithm?

The prime calculation concept is quite clever, saved a lot of space:)

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

Why is the primes array of size 6e6?

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

    It's a rough estimation.

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

      But shouldn't it be 6e7 according to this?

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

        Yes, you are right, there are around 5e7 primes under 1e9. But that would exceed the memory limit. So I think the problem setters did not intend to let this method pass, but I was just lucky to avoid MLE because I missed a 0 when I typed the number.

        Anyway, I think I will modify the solution in this editorial so as not to be misleading.

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

          Yes, but how is it magically passing? You're accessing out of bounds but still got it correct.

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

            Since I am using int[] instead of vector<int>, the behavior of out-of-bounds access is undefined.

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

              Using std::bitset for the bool array may work. Would occupy ~300M memory together with the prime array.

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

Auto comment: topic has been updated by lucifer1004 (previous revision, new revision, compare).

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

Hey in the second question after building up the l and r array in the final loop from 1 to n-2, upon entering the loop why you did ans=max(ans,l[i-1]+r[i+1]+1) since it is possible that the common differences of the left segment and right segment of the ith index may not be the same, it is possible only if their common differences are same as you did in the 3rd if statement

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

    I am doing

    ans = max(ans, max(l[i - 1] + 1, r[i + 1] + 1));

    instead of

    ans = max(ans, l[i-1] + r[i+1] + 1);

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

      Oh really sorry misread the solution. This is perfectly fine then. Kudos for such a great editorial :)