kostka's blog

By kostka, 3 years ago, In English

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.

Sign up today!

Hope you'll join us for Round A!

  • Vote: I like it
  • +51
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it -31 Vote: I do not like it

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 :/

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

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

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +41 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -26 Vote: I do not like it

      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 ?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

speedstart

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

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

Solution
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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$$$.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

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

      20 second time limit moment

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

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      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.

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve Palindrome Free Strings for 18 points ??

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You can check out my solution videos if you want

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

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

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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

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

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like 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

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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