My Editorial for Google Kick Start 2022 Round A

Правка en1, от lucifer1004, 2022-03-20 10:06:25

Google Kick Start 2022 Round A Tutorial

中文版 | Chinese version

Here are my solutions to Google Kick Start 2022 Round A.

Problem A — Speed Typing

Solution I: Single Pointer

We use a pointer which points to the position to be matched in the target string. We then enumerate the original string and move forward the pointer whenever a match is found.

If the target string is fully matched, the answer will be the difference between the length of the original string and the target string, otherwise there will be no valid answer.

Complexity:

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

Problem B — Challenge Nine

Solution I: Math + Greedy

We know that a number is divided by 9 is equivalent to that its digit sum can be divided by 9. We can quickly determine the digit we need based on this. If the number is already divided by 9, we can add either 0 or 9, but to make the answer the smallest, we will choose 0 instead.

We then look for the position of insertion greedily. We enumerate from to left and find the first position which is larger than the digit to be inserted.

However, when we are inserting 0, we cannot place it at the beginning, so we have to put it in the second place.

Complexity:

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

Problem C — Palindrome Free Strings

Solution I: Dynamic Programming

Any palindrom with length $$$\ge$$$ 5 must either contain a 5-character palindrom or a 6-character palindrom. So we can find all the 5- and 6- palindroms and mark them, then maintain the possible situations of the last 6 positions during a dynamic programming.

Complexity:

  • Time complexity is $$$\mathcal{O}(2^K\cdot|S|)$$$, where $$$K=5$$$
  • Space complexity is $$$\mathcal{O}(2^K)$$$
Code (C++)

Problem D — Interesting Integers

Solution I: Digit Dynamic Programming

Such problems that ask for interval $$$[L,R]$$$ can usually be transformed to $$$F(R)-F(L-1)$$$. In this problem, $$$F(x)$$$ means the number of good numbers in the interval $$$[1,x]$$$.

Then we can calculate $$$F(x)$$$ via digit dynamic programming.

  • We need to consider the relationship between digit product and digit sum. When the digit sum is fixed, we only need to record the GCD of the digit product and the digit sum.
  • We can only use numbers no larger than $$$x$$$. Such problems with an upper bound or a lower bound can be solved by using a flag to denote whether the current prefix is equal to the bound.
  • We need an extra flag to denote whether we are still within the leading zeros.

Suppose the upper bound has $$$N$$$ digits, then the digit sum cannot exceed $$$9N$$$. Then we can enumerate the digit sums. For a fixed digit sum $$$sum$$$, we do a 4-dimension DP like $$$dp[p][s][z][same]$$$, in which:

  • $$$p$$$ denotes the GCD of the digit product and $$$sum$$$
  • $$$s$$$ denotes the current digit sum
  • $$$z$$$ denotes whether the current number is larger than zero
  • $$$same$$$ denotes whether the current prefix is equal to that of the upper bound

The contribution of this DP to the final answer is $$$dp[sum][sum][1][0]+dp[sum][sum][1][1]$$$.

The details of the dynamic programming can be found in the code below.

Complexity:

  • Time complexity is $$$\mathcal{O}(S^{5/2}\cdot ND)$$$, where $$$S\le9\times12=108$$$, $$$N$$$ is the length of the upper bound and $$$D=10$$$
  • Time complexity is $$$\mathcal{O}(S^2)$$$
Code (C++)

Теги google, kick start, editorial

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский lucifer1004 2022-03-20 10:06:25 11395 Initial revision (published)