**Kick Start** is back for our tenth year! Join this online global coding competition offering beginner to advanced coders the space to develop programming skills and become better acquainted with competitive programming. We offer challenges at different times throughout the year so you can join in on the fun whenever it’s convenient for you – check out the round schedule.

Our first official round of the year (round A) starts on **March 20th 2022, 04:00 UTC**.

Before the round, be sure to:

- Take a look at our helpful tutorial video, to learn more about the competition platform and some useful tips and tricks.
- Practice out past problems and review the FAQ.
- Check out our YouTube playlist, where you’ll find problem walkthrough videos hosted by Google engineers.

Hope you'll join us for Round A!

Friendly reminder that Round A starts in less than 24 hours (March 20th, 2022, 4:00 UTC).

Ok, someone please help me understand why do you put subtask 1 for problem D as difficulty div2A. Come on, its "problem D", why do you make it dead simple :/

Who said it was problem D,it was one of the 4 problems put in a row such that it was at 4th place ,if you carry conception about things,then its your problem.They just wanted you to teach to read all problems and not having prjudice about any problem.

Its a common understanding that the problems are sorted according to difficulty, which is completely reflected by the total points for each problem

But subtask 1 on D has less points than subtask 1 on C....

It's worth fewer points than any problem that got solved less, and the full problem for D was the hardest problem in the contest (or the least solved, anyway), so I'm not sure why you're complaining.

I mean, its fair enough that subtask had low point, but that is what I asking about, why do you even put a subtask that low point at that place in a contest ?

thats, why you should read all the tasks first, so you wouldnt cry afterwards about losing couple hundreds of positions

speedstart

SpoilerAnalogous to speedforces

Felt like testcases for problem C were weak. Instead dp my recursion passes both the subtasks.

SolutionIt is optional solution as the upper bound of total number possible strings is quite less.

Did anyone else just write $$$dp[index][gcd(sumOfDigits, prodOfDigits)][sumOfDigits][curSum]$$$.

I think this is close to $$$O(S^{7/3} * |B| * Z)$$$ where $$$Z = number \space of \space digits$$$.

Wow, this sounds faster than what I did.

My idea was to fix the sum first and then perform the digit dp. dp finds the count of numbers in the range [1, x] whose sum of digit is fixed and product of digit is multiple of sum.

Running this idea locally for random inputs was taking around 0.5 seconds for each test case, and therefore shouldn't have passed. But somehow it passed test set 2 lol.

20 second time limit moment

But there were 100 test cases if i remember correctly. So it should have taken 50 sec.

This was true of mine too. Google have better computers than we do :)

I tried a few other solutions from the top end of the leaderboard locally and most took over 20 seconds to run.

How to solve

Palindrome Free Stringsfor 18 points ??You can check out my solution videos if you want

use dynamic programming with $$$index, mask$$$ as your state where $$$mask$$$ is the binary string representing $$$S[index-6:index]$$$.

We use $$$6$$$ here instead of $$$5$$$ so that we can check even palindromes too not just odd.

How many do we have to solve to reach the next round?

Kickstart rounds are independent of each other. You can read the FAQ.

For problem D I overkilled with a $$$9D$$$ digit dp solution.

The product of digits will have at max 4 distinct primes in it prime factorization (2,3,5,7). Thus instead of representing the product directly in our dp we can instead represent it as the powers i.e. we can store a,b,c,d such that 2^a * 3^b * 5^c * 7^d is equal to the product of digits.

However this is still not enough.We will still need to optimize further to avoid MLE. To avoid MLE we can note that we don't need that we don't need the full factorization of the product i.e. since the sum can be at max 120 we can store prime factors required for product < 120.

With this optimization our dp table will fit in memory constraints. The states for the dp would be

My code

all your solutions for a problem must be +5d dp.

Hello, Can you please tell why 11 cant be in prime factorization of product of digits?

Since 11 cannot be a digit i.e. since all the digits are single digits their products will have no double digit prime factor.

Thanks , got it.

If the case with 0 is handled separately, the number of dimensions can be reduced to 6: number of digits, number of 2, number of 3, number of 5, number of 7 and sum of digits. This passed both time and memory quite comfortably :D

Does Kick-Start get progressively difficult from A to E? or this is only a way to number these rounds?

only a way to number these rounds

ok thanks.