Interesting Programming Problems

1.IOIPALIN (spoj, my code, level 2, original length - LCS of original and reversed string, bottom-up dp with space optimisation)

2.SAMER08D (spoj, my code, level 2, bottom-up DP)

3.COUNTARI (codechef, my code, solution is giving TLE but the solution implies a very strong concept which is worth learning)

4. SRM 549, Div 2, Level 2 (maximum bipartite matching, editorial)

5. SRM 338, Div 1, Level 3 (Game theory, editorial, my code)

6. FLIPCOIN (segment tree implementation with  lazy propogation, my code)

7. Given an array A of N integers such that each integer is less than equal to 29. Find the number of contiguous subsequences of integers such that xor of the integers in the subsequence is 0. Note that the subsequence can contain between 1 to N elements inclusive.
(solution- DP, Since the maximum value of integer is 29, there would be 32 xor values possible [0,31]. Suppose u know the number of subsequences whoes first element is A[i] and whoes xor value is X, then two cases arises- 1) the subsequence contains only A[i].     2)the subsequence contains A[i+1] also.Now assume we have already calculated number of subsequences starting with A[i+1] for each xor value, then we can simply find the answer for A[i],  pseudo code)

8. SRM 565, Div 1, Level 2 (Game theory, editorial, my code, idea in the above Q-7 is also used)

9. SRM 566, Div 2, Level 2 (Greedy approach, editorial, my code)

10. SRM 500, Div 2, Level 3(Maths, editorial, my code)

11. SRM 503, Div 2, Level 3 ( MST using Prim's, editorial, my code)

12.There is an array of 15 cards. Each card is putted face down on table. You have two queries:
 1. T i j (turn cards from index i to index j, include i-th and j-th card - card which was face down will be face up; card which was face up will be face down)
 2. Q i (answer 0 if i-th card is face down else answer 1)   (use BIT to solve ,my code)

13. HIGHWAYS (spoj, Dijkstra, my code)

14. SRM 570, Div 2, Level 3 (Finding the number of subtrees, editorial, my code)

15. SRM 571, Div 2, Level 3 (editorial, my code)

16. TASTR (codechef, suffix array for calculation of number of unique substrings of a string, editorial,my code)