Editorial For CODEMarathon div-1/2/3 contest 2

Division 3:

Question 1: Sherlock and letter's case : implemetation
My solution
just print odd line's odd indexed charachter in upper case and rest in lower case.
print odd line's odd indexed character in lower case and rest int upper case.
_________________________________________________________________
Question 2: Sherlock and pattern : brute force, math
My solution

for the given number just count the number of rows subtracting row number till its stays positive. The remaining number if the column number.
_________________________________________________________________
Division 1 and 2

Question 1: Silly Watson - Simple Ad-hoc
My solution

just implement the given recurrance. Brute force works fine for the given constraints.
Or you could solve a quadratic equation that it forms
d = d + c => d(t) = d0 + tc
a = a + d => a(t) = a0 + Sum(d(t))
=> a(t) = a0 + Sum(d0 + tc) = a0 + d0 * t + t*(t+1)/2 * c = n
final equation : ct^2 + (2d + c)t - 2(n-a) = 0

solve for t and print t*p
_________________________________________________________________
Question 2: Sherlock's keyboard - Recursion, STL
My solution

you need to print all the paths in a graph with valid directions as North, South, East, West. Since we can visit an key any number of times, so a simple recursive function allow us to do that (plus the constraints are small.)

simply go to recur(x-1, y), recur(x+1, y), recur(x, y-1), recur(x, y+1). at each step the length of the string increases, when the length becomes given 'l', store the string. After the recursion terminates, print it in lexicographic order.
_________________________________________________________________
Question 3 : Sherlock and chess - shortest path, bfs
My solution
this question requires you to move 2 knights to a square in a 10x10 board. suppose knights be A and B. let the optimal cell be P:(x,y). suppose A moves to P in 'a' steps and B in 'b' steps. if it is optimal then this is equivalent to moving A to B via P or simple traversal from A to B.

_________________________________________________________________
Question 4: moriarty and his code - Dp + Greedy
My solution
Let us observe the pattern
1 1

2 10

3 100

4 1000
5 1001

6 10000
7 10001
8 10010

9 100000
10 100001
11 100010
12 100100

13 1000000
14 1000001
15 1000010
16 1000100
17 1001000
18 1001001

let p(x) denote the number of valid bit strings of length upto x
p(1) = 1
p(2) = 2
p(3) = 3
p(4) = 6
p(5) = 9
p(6) = 13
recurrance if p(n) = p(n-1) + p(n-3)

to get the nth bit string you just need to run a search down from the max index. Observe that the pattern contains the sequence itself from length 1 to x-2.

subtract largest p(x) < n and set xth bit from the right end set.

_________________________________________________________________
Question 5: Sherlock and his students : String matching
My solution

You need to find a pattern H[l..r] in a string.
given H(L + i) + H(l + i) = H(l) + H(L) for all i in 0 to r-l
So we can hash H[l..r] for comparision purpose
suppose z = H(l) + H(L)

so we need to find a pattern of (z-H[l]), (z-H[l+1]), (z-H(l+2)) ... (z-H(r))

using the standard Hash function f(H) = H[0] + H[1]*p + H[2]*p^2 .. H[n] * p^n

find the hash(H[L..R])
now we can simulate the above hash using the pattern H[l..r]
sh(z,l,r) = (z-H[l])*p^L + (z-H[l+1])*p^(L+1) + (z-H[l+2])*p^(L+2) ..
which is z*p^L(1 + p + p^2 ... + p^(r-l)) + p^L(f(H[l..r]))
if these two are equal means that the pattern match. Hence the pattern can be found .