Блог пользователя kostka

Автор kostka, 3 года назад, По-английски

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!

  • Проголосовать: нравится
  • +51
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится -31 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится -10 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +22 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится -26 Проголосовать: не нравится

      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 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

speedstart

Spoiler
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

Solution
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      20 second time limit moment

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится

      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 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How to solve Palindrome Free Strings for 18 points ??

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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