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 .

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 .