### kostka's blog

By kostka, 10 months ago, 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:

• Practice out past problems and review the FAQ.
• Check out our YouTube playlist, where you’ll find problem walkthrough videos hosted by Google engineers.  Comments (30)
 » 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. Solution#include #define int long long using namespace std; int cases = 0; void rr() { cout << "Case #" << cases << ": "; } bool ok; bool test(string &s, int i, int j) { if (i < 0) return false; while(i < j) { if (s[i] != s[j]) return false; i++, j--; } return true; } void solve(int i, int n, string &s) { if (i == n) { ok = 1; return; } if (s[i] == '?') { s[i] = '0'; int a = test(s, i - 4, i); a |= test(s, i - 5, i); if (!a) solve(i + 1, n ,s); s[i] = '?'; } if (s[i] == '?') { s[i] = '1'; int a = test(s, i - 4, i); a |= test(s, i - 5, i); if (!a) solve(i + 1, n ,s); s[i] = '?'; } if (s[i] != '?') { int a = test(s, i - 4, i); a |= test(s, i - 5, i); if (!a) solve(i + 1, n , s); } } void test_case() { int n; cin >> n; string s; cin >> s; rr(); ok = 0; solve(0, n, s); if (ok) { cout << "POSSIBLE"; } else cout << "IMPOSSIBLE"; } int32_t main() { int tt; cin >> tt; while(tt--) { cases++; test_case(); cout << endl; } return 0; } 
•  » » It 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 Strings for 18 points ??
•  » » You can check out my solution videos if you want
•  » » 10 months ago, # ^ | ← Rev. 2 →   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 pos [0,15] -> position from left we are at small[0,1] -> are we smaller than the input number or equal to it till the i position start[0,1] -> have we started building the number zero[0,1] -> is the product of digits equal to 0 two[0,8] -> number of times 2 comes in the prime factorization of the product of digits till now three[0,6] -> number of times 3 comes in the prime factorization of the product of digits till now five[0,3] -> number of times 5 comes in the prime factorization of the product of digits till now seven[0,3] -> number of times 2 comes in the prime factorization of the product of digits till now sum[0,120] -> sum of all the digits till now 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.