Google's hiring contest, APAC Kickstart 2017 Round E is going to held on Sunday, August 27, 2017 05:00 UTC – 08:00 UTC

Ready to get started solving fun, challenging problems? Throughout the year, Code Jam hosts online Kickstart rounds to give students the opportunity to develop their coding skills, get acquainted with Code Jam’s competition arena, and potentially get noticed by Google recruiters, too. Participate in one—or join them all!

For more visit here.

You asked it in english twice.

American English, British English.

Did anyone got call due to his/her performance in KickStart Round D ???

Where can we upload our resume on the kicktstart site? I have already registered

you can give your resume link in "update profile " section on their website

All solutions and explanations will update here soon after the contest ends. https://github.com/ckcz123/codejam

Good Luck!

Solutions of A, B and C-small have been updated!

Round link anyone?

https://code.google.com/codejam/contest/12234486/dashboard

Sadly no one get 100 scores, people who passed C large are all failed in A large.

Can any one tell me how did they did B large?

Let's say the sides of trapezoid are

a,b,c,c; such thatb>a; Now due to the fact that height of trapezoid should be > 0, we get the condition betweena,b,casb>aandb< (2 *c+a). Now you can simply iteratea,cand count the number ofb's that satisfy given condition. The answer is number of ways we can pick (a, c) * number of suchb's.The counting of b's can be done in

O(logn) using binary search. That gives the solution complexity ofO(n^{2}logn).Can you share your code please ?

I can share but it's very complex.

You can also check my code, it's easier to understand.

Instead of binary searching for counting of b we can use two pointer method and reduce complexity to O(n^2)

Yes of course :)

Can someone explain their solution for A-large?

I tried a dp solution but failed. Can somebody please point out the error? Let s be the string. State is dp[i] which is the minimum steps required to construct the string s[0..i]. Initialise dp[0] = 1 and dp[1] = 2. For every i in [2, length(s)-1], first do dp[i] = dp[i-1] + 1 which corresponds to the first operation. Or select some j < i and consider the string t = s[j..i]. Check if the string t can be formed by repeatedly concatenating some substring of itself and check whether that substring exists in s[0..j-1]. If it does, then dp[i] = min(dp[i], dp[j-1] + 1 + length(t)/l) where l is the length of repeating string we considered.

My code: Ideone

Thanks!

DP[i][a][b] — minimal number of steps for sufix i...n if in clipboard we have substring a..b

Transitions ?

Got my mistake.

Can you please share what the mistake was?

A substring can reamin persistant on the clipboard with character intsertions in between. For example, condider bacackac.

Here, b-> ba -> bac -> bacac -> bacack -> bacackac.

Ah yes, totally missed that. Thanks!

What would be recursion for this problem ? I came up with these cases ->

What with this test?

gabbbbbbbbbcwabbbbbbbbbc

Mine gives 12. But I cant give assurance since mine is a hashing solution

could you share the idea of hashing solution?

I am getting 12 with my code, I compared this with an AC code which also outputs 12.

Simply use recursion with memoization

f(cur, str) -> if till cur we have made the string till "cur" and "str" is on clipboard, our answer is f(-1, "") and halt recursion when cur = n — 1; where n is string's length.

Transitions:

1) add one char -> 1 + f(cur + 1, str)

2) if string on clipboard fits -> 1 + f(new_length_done, str)

3) one by one check for all x if substring (s[cur + 1....x]) is already present in made up string -> 2 + solve(x, s[cur + 1....x]);

Memoize using map< pair<int, string> , int> dp Code: https://ideone.com/pixvWn

Wow, that's an awesome solution!

Can you please explain the third transition in a bit detail ????

Basically I try to copy a new string to clipboard and obviously paste it to end of our already made up string (otherwise we won't even paste it on clipboard). So 1 move for pasting on clipboard and then 1 move for pasting it at the end.

For e.g. s = "mautkakuan" and cur = 5, clip = "a";

I try to put strings 1) "k", "ku", "kua", "kuan" one by one to clipboard and then to string and move forward to f(new_len_done, clip).

shubhiks1032

why are we considering only the first occurrence of substring?

I dont think this will pass large data set, even with memoization.

nice solution, and how to analyze the time complexity？

What is the approach to solve C Large ???

Here are some unofficial results after running plagiarism check on all the codes(includes both accepted and unaccepted submissions).

https://drive.google.com/drive/folders/0ByNcq665KLJhMWh6U1MwWEY0djQ

My rank is below 350 and in india below 100.I am in third year can i get chance of intership or not.

Here's your answer. You can read it

Hello everyone, here is the official analysis:

https://code.google.com/codejam/contest/12234486/dashboard#s=a&a=3

How to check if three circles have a common intersection?