.NET (3) .rb (1) *.cod (1) 3110c (1) Algorithm (1) Amazon Cloud Drive (1) amkette (1) Android (1) Apex (6) apex:dynamic (1) API (1) API version (1) Application Development Contest (2) Artificial Intelligence (2) Atricore (1) b2g (1) Binary Search Tree (1) Blackberry Application Development (1) Blackberry Java Development Environment (1) Blender Game Engine (1) bluetooth (2) Boot2Gecko (1) bug fix (1) C (1) C++ (2) Cloud computing (1) Cloud Storage (1) Code Blocks (1) Code for a Cause (2) codejam (1) Coding (1) const_cast (1) Custom Help (1) Dancing With the Googlers (1) Data Structures (1) desktop environment (5) Doubly Linked List (1) Dropbox (1) dynamic visualforce component (1) dynamic_cast (1) Enterprise WSDL (1) Execution Context (1) fedora 14 (1) fedora 17 (5) Firefox OS (1) Flashing Nokia 3110c handset (1) (7) Gaia (1) Game Developement (1) GCC (2) GDG (2) Goank (1) Google (4) Google Developer Group (2) Google Drive (1) GTK+ (5) HACK2012 (2) Hall of Mirrors (1) help for this page (1) HTML5 (2) HTTP Web Server (1) IDE (1) Identity Provider (1) Intelligent Systems (1) Java (1) JDE (1) JOSSO (1) location based social network (1) (1) MinGW (1) Natural Language Processing (1) Natural Language Toolkit (1) neckphone (1) NLKT (1) Nokia Pheonix (1) Notebook (1) Numeric XML Tags (1) OAuth2.0 (1) OLPC (7) OLPC-XO-1 (7) One Laptop per Child (5) Override custom help (1) Paas (1) Partner WSDL (1) Polymorphism (1) programming contest (1) PyGTK (4) Python (10) Recycled Numbers (1) reinterpret_cast (1) Research (1) REST (1) RM-237 (1) Robotics (1) Ruby (1) Saas (2) (7) SDK (1) Service Provider (1) Single sign on (1) SOAP (3) Speaking in Tongues (1) SSO Agent (1) SSO Gateway (1) static_const (1) sugar (7) sugar activity (4) sugarlabs (7) SVG (2) Symbiotic AI (1) Tabbed container (1) TCP/IP (1) TCP/IP stack (1) Typecasting (1) typeid (1) ubuntu 13.10 (1) UDP (1) Upgrade Assembly (1) Visualforce (2) Web Server (1) Web Services (3) Web2.0 (1) wikipedia (1) wikipediaHI (1) WSDL (1) XML tags (1)

Saturday, April 21, 2012

Google CodeJam 2012 experience

Last weekend was something different from stereotyped weekend pattern. I participated in Google CodeJam 2012. I took part last year but did not manage to get through subsequent rounds leading to finals. 

This time I was bit lazzy even after knowing the schedule of the contest. I woke up at around noon( 6 hrs past the beginning of contest-started at 4am IST) and landed on codejam page. I went through set of questions and got an idea on complexity of problems. Last time I wrote all code in C programming language. But this time I used C and Visual Basic for solving the problems. The advantage you get in using high level language is availability of data structures like list, hashtables, etc. I must say the set of questions presented this year was mix of easy and complex problems. This time they have also changed the pattern. The first question "A" carried 15pts and only required for small input.

Lets discuss about problems, their complexity and approach I used to solve them:

Problem A. Speaking in Tongues (read problem)
This problem was easy among the set. you actually need to translate the given input into other format. Googlerese is the language generated by replacing english alphabet by different alphabet . They provided the mapping in question. 

Solution: I went through problem statement and sample input in question to capture the mapping pattern. I made use of two hashtables. one hashtable used for simple english to Googlerese mapping and other used for inverse mapping. i.e Googlerese to english. I used static initialization of hastables with pair for mapping based on sample input.

Key points to be noted while solving this:
1. Make sure mapping for all alphabets is present in map or any other data structure you are using.

download my output for Speaking in Tongues -small input from here.

Problem B. Dancing With the Googlers (read problem)

This problem deals with permutation and combination. So if you are comfortable with P&C then it will be easy for you to solve. The main crux of the problem was to bring out all the possible set of triplet for each score for Googlers and find the ones with minimum value of some threshold value. This threshold value is varying for each case.

sample provided :

Here the tricky part was of surprising triplet. a triplet is said to be surprising if all 3 judges gives scores such that scores differ exactly by 2. example( 6,7,8), (2,4,4) are surprising triplet.

Solution: I used algo to bring out all triplets keeping in mind the threshold value(p). 

I initially done it this way:
say if we have  input as 3 1 5 15 13 11. where 3 is number of Googlers for which score is given, 1 is number of surprising triplet, 5 is the threshold value(p). and rest of numbers are scores for Googlers separated with spaces. so here we need to find out how many triplets will have atleast one value> threshold value(p). 

I initially write code that assumes surprising triplet value( here 1) not equal to 0 then the current score I am working on is surprising triplet, so first score 15 is surprising. But this may not give the best possible set( our aim is to maximize number of googlers with one judge's score>threshold value(p)). So you need to consider case when 15 is surprising, case when 13 is surprising and case when 11 is surprising. then pick the best result maximizing number of googlers with one judge's score>threshold value(p). 

Key points to be noted while solving this:
1. Sum of judge's response should be equal to given score for case.
2. Make sure to consider best possible set for each case.

download my output for Dancing With the Googlers -small input from here.

Problem C. Recycled Numbers (read problem)
This problem seems easy but the main aim why Google brought this question on developer's plate is to check efficiency of the code as it involved number ranges in order of 1 to 2000000.

The problem was to find set of distinct numbers (n,m) such that if one or more digits were replaced from back of n and place in front of n will result in m. 

example: (12345, 34512) is a recycled pair since you can obtain 34512 by moving 345 from the end of 12345 to the front. 

sample provided:

Solution: I enjoy writing parsers thus I picked up approach to solve this using strings. Starting from smallest value in the range I moved each single character from back of number to front of number and checked whether resulting number is in the given range.

So far we are moving only single digit at a time, the resulting number will be different if we move more that 1 character at a time. that's it! If you got this then you can easily solve this!  so if you have a 4 digit number then you need to consider cases when moving only single digit, moving 2 digits, moving 3 digits at a time.

Key points to be noted while solving this:
1. n and m must have the same number of digits in order to be a recycled pair. 
2. Neither n nor m can have leading zeros. example: number 0021 is not valid.
3. Make sure you include range check in your code to handle dataset range given in problem.

download my output for  Recycled Numbers -small input from here
download my output for  Recycled Numbers -large input from here

Problem D. Hall of Mirrors (read problem)
This problem was bit tough and unfortunately I did not get time to solve and submit this. I will try to solve this and share my experience on this.

I hope this post helps you understand the kind of questions presented in codejam.

No comments: