**WPC #3** was held on this sunday.

http://aca.cse.iitk.ac.in/public/
Problems have been moved to spoj.

Editorials: (these editorials are merely hints, You need to work things yourself for final answers)

Hope you will like them. Leave a comment if something is unclear or needs to be modified, Also leave your opinion about the contest.

Consider the string s. Let it has some consecutive characters of length
L, Then you can directly replace L by just 1 character. After such
replacements just check if the string is palindrome or not?

eg. s = "ababbbaaa".

s = "ababa". Replace bbb with b and aaa with a.

You need to do this in O(n).

2.

**Gopu and Validity of Arrangement:** (

http://www.spoj.com/problems/SPCU/)

You can easily prove that if answer exists then it is unique, Only
condition you need to check that any ith indexed person does not say
that $\ge$ i persons are before him. You can relate this problem with
permutations.

3.

**Gopu and Digits Divisibility: (**http://www.spoj.com/problems/SPCU/)

You can easily do a brute force. Think about it why this works, Hint:
for checking divisibility by 9, sum of digits should be divisible by 9.
(Though hint is not of great use in the proof).

4.

**Gopu and Function: (**http://www.spoj.com/problems/SPCM/**)**
Value of n will be atleast halved in each computation of f. As Take the
best cases when n = 2*p where p is prime, Sum of divisors is 2 + p
which is 2 + n / 2. In other cases, sum would be even less than n/2. For
finding prime divisors of n, use simple sqrt algorithm. Final
complexity would be O($\sqrt[2]{n}$ logn).

5.

**Gopu and Create Collections Part two (**http://www.spoj.com/problems/SPCJ/)

You can use dp over the tree for solving this. You can use a greedy
algo also. Sort the numbers in increasing order, go from right to left
and for each number K if you find a number K/2 which is not yet taken
then take it and add it to answer.

You can also use greedy
algorithm by constructing the binary tree explicitly and then going from
leaves to the root of the tree.

6.

**Gopu and Combinatorics on Graphs: (**http://www.spoj.com/problems/SPCE/)

This is standard problem. You should know

http://en.wikipedia.org/wiki/Cayley%27s_formula. Then figuring out things wont be tough. I dont want to give formulla as I want you to work it out.

7.

**Gopu and Counting bitwise prime numbers: (**http://www.spoj.com/problems/SPCO/**)**
This problem had one slow solution:

use dp(i, tight): where i denotes the position in the binary
representation of the number (i goes from most significant digit to
lower), tight denotes wheteher the current number has overshoot the
number n or n. See my slow code

http://ideone.com/numnIE.

You can optimize it slightly and get it passed. Basically think in terms of combinatorics, You will get the idea.