Google Kickstart Round C Editorial

general
, ,
1

Hello Codechef Community, Here are the video editorials for today’s held Google Kickstart Round C 2021. Each and every problem along with their solutions are explained in detail.

Below are the links to the solution:-

  1. Smaller Strings
  2. Alien Generator

Rest problems will be updated soon.

Please do watch videos, like, comment, and subscribe to this channel. Likewise, Videos will be uploaded for most of the contest’s editorial. Any suggestions are welcome, do comment in this blog post.

Thank You!!

Google Kickstart Round B Editorial
Algebra in Competitive Programming

2 Likes
2

Solution for Alien generator is just the number of odd factors of G .

2 Likes
3

yes, you are correct!

1 Like
4

Is there any mathematical proof for that?

5

I have one
k+k+1+k+2+…+k+n could be written as
=(n+1) * k+1+2+3+4+5+…n
=(n+1) * k+(n * (n+1))/2
=(n+1) * (k+(n/2))
it means that n is even so (n+1) is odd , and (n+1) is a factor of ans.

6

Yes, If we solve the mathematical relation, we get this.

7

yes. All you are doing is writing an AP(Arithmetic progression)

A + (A+1) + … (A+n) = G

then sum on left is (n+1)*(2A + n) / 2 = G
rewriting we get

(n+1) * (2A + n) = 2G

now observe that on the left only one number can be even and other is odd

so u need to break 2G into factors = d1 * d2 such that only one is odd. this can be done by removing all powers of 2 from 2G and lets say it becomes = G’ then G’ is odd. now divide it into 2 factors say x and y and put all the powers of 2 you removed from 2G into x

this method will give you required (n+1) and (2A+n)

and since the number of ways would depend on number of ways of getting x and y
which is same as finding all odd factors of G’ and hence in turn of G

2 Likes
8

Can you make video on problem C Rock Paper Scissors?

9

Solve these problems, that one is really trivial if you know how to solve these standard problems.

1 Like
10

very interesting problems.

11

my code
why is my code giving TLE when submitting, it’s not even passing tescase1, what’s wrong?
can anyone help?
my approach
you can represent G = k + (k+1) + (k+2) + (k+3) + … (k+n)
(n+1) * k + (n * (n+1))/2 = G
k = (G - (n * (n+1) / 2) ) / (n+1)
max value of n * (n+1) / 2 will the nearest triangular number T smaller than G, we can find that like this, then find the ‘n’ from that triangular number and iterate from n → 0

let 0<=i<=n, count the number of i for which k is a positive integer, that will be the answer