Posted in GCJ

GCJ Post #1

So GCJ for the year 2016 has started, I signed up on Saturday thinking that it was next month but apparently it was yesterday…. Kinda caught me off-guard there!

This is my first try in applying for this and I am making it a point to work on it to qualify to the 2nd round(There are 5 rounds A-E and I just wanna attend round B that is all…). So I will be posting a few questions and how I answered it and how they have answered it and compare them both and find where I can improve myself so that I can achieve this short term goal.

I call this a short term goal cause yesterday (26th, June) was the practice round with 4 two subdivision questions starting at 10am for 3 hours. And the next one is on July 10th. So in this 2 weeks time, I want to solve as many algorithmic problems as possible.

A little something about GCJ problems first so that I can move on to the format of my answer given a problem. The problem is a descriptive scenario where they give you the variables and trust me it was kinda hard to even understand the questions given in the practice round. And it is said that the practice questions are comparatively easier than the real deal… *sigh I have a long way to go I guess?

So the question format is this. A scene is given. A set of inputs are given and the corresponding set of outputs are given and we have to code in the language that we are comfortable in. I was having a hard time choosing the language. I think python will give me the desired results (I’ll most probably switch over to C halfway through?)

┬┴┬┴┤(・_├┬┴┬┴

Anyway, the problem randomly chose for today for me to work on is :

The Lazy Spelling Bee

I was only able to understand the problem statement like after the time expired (meaning I never attempted any of the 4 problems) this was the question.

In the Lazy Spelling Bee, a contestant is given a target word W to spell. The contestant’s answer word A is acceptable if it is the same length as the target word, and the ith letter of A is either the ith, (i-1)th, or (i+1)th letter of W, for all i in the range of the length of A. (The first letter of A must match either the first or second letter of W, since the 0th letter of W doesn’t exist. Similarly, the last letter of A must match either the last or next-to-last letter of W.) Note that the target word itself is always an acceptable answer word.

You are preparing a Lazy Spelling Bee, and you have been asked to determine, for each target word, how many distinct acceptable answer words there are. Since this number may be very large, please output it modulo 1000000007 (109 + 7).

Input

The first line of the input gives the number of test cases, T. T test cases follow; each consists of one line with a string consisting only of lowercase English letters (a through z).

Output

For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the number of distinct acceptable answer words, modulo 109 + 7.

Limits
1 = T = 100.

Small dataset
1 = length of each string = 5.

Large dataset
1 = length of each string = 1000.

Sample
Input 
4
ag
aa
abcde
x

Output 
Case #1: 4
Case #2: 1
Case #3: 108
Case #4: 1

In sample case #1, the acceptable answer words are aa, ag, ga, and gg.
In sample case #2, the only acceptable answer word is aa.

I really feel stupid now that I wasn’t able to understand the question…*sigh Guess I have a long way to go to qualify for the B round?
# input() reads a string with a line of input, 
#stripping the ‘\n’ (newline) at the end.
# This is all you need for most Google Code Jam problems.
t = int(input()) # read a line with a single integer
for i in range(1, t + 1):
     #Insert code logic
This is the format you need to submit in at least that was what I understood from reading the tutorials page at the site (after 10:30 cause I was totally new over here…*sigh)

So what’s the logic? More importantly, what’s the question? I don’t know if I can make it more complicated by explaining it but you never know cause it is me under consideration!!!

Ψ( ̄∀ ̄)Ψ

So from the question: 

There are 3 cases. W of length 1 which has 1 and W of length 2 has 4 iff W’s 2 characters are different from each other else it is again 1. And the others can be split into [ 1,W-2,1 ] and the problem logic can be applied. So a possible solution can be…

T = int(raw_input())
for i in range(T):
   print (“Case #%d:” %(i + 1));
   W = raw_input();

   ans = 1;
   if (len(W)==1):
      print ans;
   elif (len(W)==2):
      if(W[0]==W[1]): print 1;
      else:print 4;
   else:
      W = W[0] + W + W[-1];
      for i in xrange(1, len(W) – 1):
         ans *= len(set(W[i – 1: i + 2]));
         ans %= 1000000007;
      print ans;

At least that is what I have understood from the problem statement. Since I don’t have a way to find if the logic is right or not for all possible inputs… I am gonna think of some other way to prepare for the GCJ, Maybe try out some site like Code Chef or CodeKata or the Euler Project that dropped in the middle cause of my sem exams….

(≖ლ≖๑ )フ

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s