Code Chef: February Challenge First Five

Chef And His Characters:

This problem is straight-forward. Check every substring of length four and find if the 4 characters of string are 'c', 'h', 'e' and 'f'.

Complexity: Linear per case.
Link to my C++ code!  

---

Chef And The Patents:

Simple implementation problem. Just calculate the maximum number of patents that can be finished in the given time and finally compare it with the required patents to print the answer.

Complexity: Linear per case
Link to my C++ code!

---

Permutation and Palindrome:

First of all make a 2D-Array or Array of vectors v(let).

v['a'] = {indices where a occurs in the string}

v['b'] = {indices where b occurs in the string}

...

...

v['z'] = {indices where z occurs in the string}

Now  check where frequency of each of the character in the string. 

If there are more than one character which have odd count:

    then, print -1.

else:

First see all those characters which have even count.

Print half of the stored indices of those characters from 'a' to 'z'.

Now see if there is a character with odd count.

If Yes, then print all the indices of that character.

Now print remaining half of the indices but this time in reverse order i.e from 'z' to 'a'.
Complexity : Linear per case

Link to my C++ code!

---

Car-pal Tunnel:

Let t(i) denotes the time taken to pass from ith tunnel.

Observation:

If t(i - 1) > t(i): 

    Then there will be no delay when passing from ith tunnel. So simple ignore 

    the ith tunnel.

Note: Starting from first tunnel consider only those tunnels which have t(i) > t(i-1).

Must use paper and pen !!

Now note the delay at each tunnel. At each tunnel delay between first and last car will be (t(i) - t(i-1)) * (c-1).

Add all the delays and print the answer.
Complexity : Linear per case.

Link to my C++ code! 

---

Broken Clock:

Pre-requisite: 

Trigonometric formula: 2*cos(a)*cos(b) = cos(a+b) + cos(a-b)

Let cos(theta) = d / l, where theta is angle moved in 1 second.

Clearly, after t seconds:

    Angle moved, $ = t * theta

So y-coordinate after t-seconds will be l * cos($).

Note: We need to calculate cos(t * theta) using already known cos(theta).

Let see the calculation:
Let t = 12
t is even, so divide t into 2 equal parts:
2 * cos(6*theta) * cos(6*theta) = cos(12 * theta) + cos(0)
or
cos(12 * theta) =  2 * cos(6*theta) * cos(6*theta) - cos(0)

We know that cos(0) = 1.  So only thing we need to calculate is cos(6*theta)

Now Lets calculate cos(6 * theta) using the same formula:
cos(6 * theta) = 2 * cos(3 * theta) * cos(3 * theta) - cos(0)

Again we need to calculate  cos(3 * theta):
Note: Here t is odd, so divide t into 2 parts: (t/2+1) and (t/2)
cos(3*theta) = 2*cos(2*theta)*cos(theta) - cos(theta)

We know cos(theta), but we need t calculate cos(2*theta).

So cos(2*theta) = 2*cos(theta)*cos(theta) - cos(0)

I hope you observed the Recursion.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

typedef long long ll; map<ll,ll> cos; ll funcos(ll l, ll d, ll t){ ll mod = 1e9+7; if(t == 0){ cos[0] = 1; return 1; } if(t == 1){ cos[t] = (d * inverseModulo(l, mod-2, mod))%mod; return cos[t]; } if(cos.count(t))return cos[t]; if(t is odd){ cos[t] = (2*funcos(l, d, t/2+1)%mod*funcos(l, d, t/2)%mod + mod - funcos(l, d, 1LL)%mod) % mod; }else{ cos[t] = (2*powerModulo(funcos(l, d, t/2), 2LL, mod) + mod - 1) % mod; } return cos[t]%mod; }

Note: 
1.       powerModulo calculates base^exponent modulo mod.
2.       inverseModulo calculates base^(-1) modulo mod. 
Complexity : log(n) per case.
Link to my C++ code!

Thanks for reading this post!
Happy Coding!