Find how many N digit crazy numbers exist such that the difference between the adjacent digits of the number is exactly one. Crazy numbers have  the difference between the adjacent digits of that number is exactly one.
For N = 3, crazy numbers are 123 , 434 , 567 etc. Numbers like 576, 453 etc. are not considered crazy numbers.
Find out how many crazy numbers exist containing exactly N digits modulo  10^9+7.

For N=1, crazy numbers are 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 .
For N=2, crazy numbers are 10 , 12 , 21 , 23 , 32 , 34 , 43 , 45 , 54 , 56 , 65 , 67 , 76 , 78 , 87 , 89 , 98.

my approach is

f(num,sz)=total crazy numbers  of sz={1,2,3, ..upto n} and num={ 1,2,3,4,5,6,7,8,9}

base case is f(num,1)=1 // crazy numbers of length 1 is 1 for each num
f(num,sz)=f(num-1,sz-1)+f(num+1,sz-1) //for num= 1 2 3 4 5 6 7 8  
                                      //as each num except 9 has 2 states ,,1->0 , 1->2 but 9->8 only
         =f(num-1,sz-1) for num=9  
Then required ans is f(1,n)+f(2,n)+..f(9,n) .for n=1 we add special case 0


Is my approach correct?Pls help 

http://ideone.com/MFs8ou

This was question i faced during hp thinkathon (contest has ended).What should be the approach to reduce time complexity less than bruteforce(O(n*n))

You have been given an integer array A on size N. You must report the number of ordered pairs (i,j) such that A[i] & A[j] is zero.
Here '&' denotes the BITWISE AND.
(i,j) and (j,i) are considered different.

Input
First line contains T-Number of Test cases. First line of each test contains N. Next line contains N integers - the ith integer A[i].
Output
Output the number of such pairs for each test case.

Constraints 
T ≤ 10
N ≤ 100000
A[i] ≤ 1000000

Sample Input()
1
5
41 47 34 40 29 
Sample Output()
 2
Explanation
These are the required pairs 3 5 5 3

Given n .You can choose n points in a circle and you have to draw lines joining them.Condition is each point can lie in only one line and no two lines can  intersect.You have to count number of line sequences possible.A line sequence is possible when we can draw lines from each points and satisfying the condtion mentioned above.

**Constraints**
1<=n<=50

Inputs
2
Output 
1

Inputs
4
Output 
2

Inputs
6
Output 
5

How to solve this?

Given a string(S) of alphabets(lower case only,a-z) of length N<(10**6), do two kind of operations(total of M<(10**5):

Type 1: 0 index c: Replace S[index] by char c.
Type 2: 1 LeftLimit RightLimit K :  Print the lexicographically Kth smallest character in the sub-string of String S starting from LeftLimit to RightLimit, inclusively.(The lexicographic order means that the words are arranged in a similar fashion as they are presumed to appear in a dictionary)

Input format:
The first line contains 2 space separated integers N and Q, denoting the length of the string and the number of operations respectively.
The next line has a string S of length N.
The next Q lines denote the update/print operations, where 0 and 1 denote the type of operation which has to happen.

Output format:
For each print operation, output the lexicographically Kth smallest character in the substring of S starting from LeftLimit to RightLimit if possible, else print "Out of range." (Without quotes)


1 <= Size of the string(N) <= 10**6
1 <= Number of queries(M) <= 10**5
1 <= LeftLimit, RightLimit, index <= N
c is a lowercase Latin letter only
1 <= K <= N
S contains only lowercase latin letters (a to z).

Sample Input
 5 3
aabbc
1 2 5 3
0 3 a
1 3 3 1


Sample Output
 b
a

Which datastructure should be used?I think BIT or segment tree should be used,but how ? How to do the lexicographically kth one?( i saw this problem while doing xseed hiring challenge at hackerearth)

Given: A strings contains 1 to K lowercase characters and at most M distinct characters.Find total such possible strings

constraints:
1 <= T <= 25
1 <= K <= 10^9
1 <= M <= 26

Sample input
2
1 1
2 10


Sample Output
26
52

https://www.hackerearth.com/code-hack-5/algorithm/incredible-string/
How to approach this problem?

I don't know whether to ask here or not but ..

I started practicing in topcoder today.

1)While solving a problem of 250 points i got 240.3 and another question of 250 points i got 83? why so?

Does it means partial marking ?(means topcoder gives partial marks or not)

why my code gives warning "Please do not use the %lld (or similar) specificator to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specificator. Press button to submit the solution."

and also gives wa for n=10**9?My code in my computer gives ans as 8888888899 but in site, it is 8888888898?

#include <bits/stdc++.h>  
using namespace std;  
#define lli long long int
const int MAX=1e9+7;
lli solve(lli n){
	lli sz=log10(n)+1;
	if(sz==1)return n;
	lli ans=9+(n-pow(10,sz-1)+1)*sz;
	for(int i=sz-1;i>1;i--){
		ans+=9*i*pow(10,i-1);
	}
	return ans;
}
int main()  
{  
  
		lli n;
		cin>>n;
    	cout<<solve(n)<<"\n";
  	return 0;  
}  

http://www.codechef.com/IOPC2014/problems/IOPC14A

What is the way to solve this problem? Most of solutions seems to check (n!mod (2*b))>=b or not ,whats the reason for this?

http://www.codechef.com/MAY15/problems/CHEFCK

This question was asked recently in codechef may15.I have been able to solve it using sparse table,but i want to know how other users solved,like AcRush and others

http://www.codechef.com/viewsolution/6875417

http://www.codechef.com/viewsolution/6918539

http://www.codechef.com/viewsolution/6851811

I think they are using RMQ <O(n),O(1)> can someone explain it or just the standard algorithm name?Pls help :)

Given a sequence a1, a2, ..., aN. Count the number of triples (i, j, k) such that 1 ≤ i < j < k ≤ N and GCD(ai, aj, ak) = 1. Here GCD stands for the Greatest Common Divisor.

http://www.codechef.com/LTIME13/problems/COPRIME3

the editorial is very difficult to understand,,isn't there any other methods??

can any one give the mathematical calculation for the question http://www.codechef.com/CLASH14/problems/CREDDIST