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
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 that b > a; Now due to the fact that height of trapezoid should be > 0, we get the condition between a, b, c as b > a and b < (2 * c + a). Now you can simply iterate a, c and count the number of b's that satisfy given condition. The answer is number of ways we can pick (a, c) * number of such b's.
The counting of b's can be done in O(logn) using binary search. That gives the solution complexity of O(n2logn).
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 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).
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