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 :
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).
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).
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.
1 = T = 100.
1 = length of each string = 5.
1 = length of each string = 1000.
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.
#stripping the ‘\n’ (newline) at the end.
# This is all you need for most Google Code Jam problems.
for i in range(1, t + 1):
#Insert code logic
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 *= len(set(W[i – 1: i + 2]));
ans %= 1000000007;
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….