can anyone give me a good explanation of how to solve this spoj problem. I know it involves the use of Euler Totient Function but i am very weak in number theory so i cant figure out how it involves the use of EOF and how to solve it. Here is the problem- LCMSUM

hey guys i tried to solve this simple spoj Problem using Binary Indexed Trees. I tested all possible cases on my computer and its giving right answer for every case. But its giving wrong answer on spoj. Can u figure out the error. here is my code

/*
written by- Piyush Golani
language- c++
country- India
College- N.I.T Jamshedpur
*/
#include <cmath>
#include <ctime>
#include <iostream>
#include <string>
#include <vector>
#include<cstdio>
#include<sstream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<cctype>
using namespace std;
#define pb push_back
#define all(s) s.begin(),s.end()
#define f(i,a,b) for(int i=a;i<b;i++)
#define F(i,a,b) for(int i=a;i>=b;i--)
#define PI 3.1415926535897932384626433832795
#define INF 2000000000
#define BIG_INF 7000000000000000000LL
#define mp make_pair
#define eps 1e-9
#define si(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define mod 1000000007

typedef long long LL;


string inttostring(int n)
{
stringstream a;
a<<n;
return a.str();
}

int stringtoint(string A)
{
istringstream a(A);
int p;
a>>p;
return p;
}

//////////////////////////////////////////////////////
struct E
{
    int i,j,rank,time;
};

struct AA
{
    int val;
    int time;
};

bool cmp(const E& a,const E& b)
{
    return a.rank<b.rank;
}

bool cmp2(const AA& a,const AA& b)
{
    return a.time<b.time;
}

E eve[250000];
int tree[30005];
int his[1000005];
int n;

int read(int idx){
	int sum = 0;
	while (idx > 0){
		sum += tree[idx];
		idx -= (idx & -idx);
	}
	return sum;
}

void update(int idx ,int val){
	while (idx <= n+5){
		tree[idx] += val;
		idx += (idx & -idx);
	}
}

int main()
{

    si(n);
    int A[n];
    f(i,0,n)
    {
        si(A[i]);
        eve[i].i=A[i];
        eve[i].j=-1;
        eve[i].rank=i+1;
        eve[i].time=0;
    }
    int q,a,b;
    si(q);
    f(i,0,q)
    {
        si(a); si(b);
        eve[i+n].i=a;
        eve[i+n].j=b;
        eve[i+n].rank=b;
        eve[i+n].time=i;
    }
    sort(eve,eve+n+q,cmp);
    AA ans[q+5];
    int u=0;
    f(i,0,n+q)
    {
        if(eve[i].j==-1)
        {
            if(his[eve[i].i])
            {
                update(his[eve[i].i],-1);
            }
            his[eve[i].i]=eve[i].rank;
            update(his[eve[i].i],1);
        }
        else
        {
            ans[u].val=read(eve[i].j)-read(eve[i].i-1);
            ans[u++].time=eve[i].time;
        }
    }
    sort(ans,ans+u,cmp2);
    f(i,0,u)
    {
        printf("%d\n",ans[i].val);
    }
}

hey guys i am finding it a bit difficult to understand KMP algo. I tried Cormen, Topcoder and many pdf's but still i am not able to grap the logic behind its working. Can anyone help :)

hey guys i am stuck with this geometry problem. I tried the editorial but the explanation is not at all understandable. I also tried to understand from the submitted codes but not able to understand much. Can anyone please explain in a nice manner how to solve this problem...http://codeforces.net/contest/280/problem/A

hey guys! today i learnt about FAST FOURIER TRANSFORM but i have no idea of how to implement this nice algorithm in c++ code. When i tried to search for the code in google all i got was a set of codes implementing it not directly but in one form or the other. So i am totally messed up.....

Guys suppose we are given two polynomial coeffecients each of degree N in vector form P and Q. Please can anyone write a nice C++ code with comments for multiplying these polynomials and output a vector of size 2N denoting the coeffecients of the resulting polynomial (product of Polynomials P and Q). Thanks in advance.

Guys can anyone give me some hint on how to do this DP Problem..

hey guys here is a simple DP Problem, to solve it i found the LCS of original and reversed string and then substracted this length from the length of given string. I am getting TLE. I used a bottom-up approach.My code is given below.Can anyone help me out??

char A[5005];
int L[5005][5005];
int n;

int ch()  //this function calculates the LCS of original string and reversed string
{

    f(i,0,n)
    {
        f(j,0,n)
        {
            if(A[i]==A[n-1-j])
            {
                L[i][j]=1;
                if(i!=0 && j!=0)
                L[i][j]+=L[i-1][j-1];
            }
            else
            {
                int x=0,y=0;
                if(i>0) x=L[i-1][j];
                if(j>0) y=L[i][j-1];
                L[i][j]=max(x,y);
            }
        }
    }
    return L[n-1][n-1];
}



int main()
{

    si(n);
    scanf("%s",A);
    //puts(B);
    printf("%d\n",n-ch());
}

hey guys here is a simple SPOJ Problem based on Dijikstra Algo. But i am not able to understand why am i getting wrong answer. Here is my CODE. Can somebody tell me where am i getting wrong.

Hey guys here is a simple problem on BFS of SPOJ. I tried to solve it but getting Run-time error. Here is my Code. At each step i am trying to pick a node from the top of Queue and insert its two children in the queue one appended with 0 and one appended with 1 back in Queue. Could u figure out the error?

Hey guys how many of u are totally pissed of by the boring and tiring Long Codechef Contests?????

Hey guys i was wondering just like BigInteger in Java is there any way to handle very large numbers along with all the arithmetic operations in c++....

hey guys here is a cool problem. u are given an array a[] of integers of size N where each integer is in range [1,100000]. We have to find the number of tuples i<j<k such that L<=a[i]+a[j]+a[k]<=H. Here L and H are integers. Need a solution better than O(N^3).

Can anyone pls tell me how to solve this problem

Hey guys i want to implement a priority queue which contains entries of type 'node'. The code is as follows....

struct node
{
    int a;
    int b;
};

bool cmp(const node& A,const node& B)
{
    return (A.a<B.a) || (A.a==B.a && A.b>B.b);
}

/// main function starts 

 priority_queue<node,vector<node>, cmp> Y;

But i am not able to compile with error... "type/value mismatch at argument 3 in template parameter list for 'template<class _Tp, class _Sequence, class _Compare> class std::priority_queue"... Can anyone help me out...

Can anyone help me to understand how to solve this problem. I am not able to understand by reading the editorial...

Can anyone suggest me how to Solve this Problem using BFS along with Bitmasks.... Never solved problems of this kind before so need some help :)

Can anyone pls explain me in detail how to solve Problem C and Problem D of CF round 138 Div 2. I tried hard to understand from the editorial but they have simply given some hint in two or three lines and i am not able to understand the logic and thus need some very good explanation.....

I am facing a lot of trouble as now a days editorials of contest are published in russian language... Writers should know that this is not a russian contest but a world level contest. So editorials should be in English and not russian...

Can anyone tell me how to solve this Problem using matrix, DP solution for this problem is too slow O(n*m*m) (n<=10^15). There exists a solution of O(m*m*m*logn) using matrix exponentiation. Can anyone please explain in detail how to solve this problem using matrix exponentiation!!!

Can anyone pls help me to solve this problem .... HAYBALE

Guys i tried hashing in a problem in which i used top down approach with recursion and made sure that if a subproblem is solved once i dont have to solve it again with STL container "map" but i failed in that.... i declared a map like "map<int,int> A" and when trying to solve a problem with a particular value of "n" i first checked whether it is already solved as the following code....

map<int,int> A;
int solve(int n)
{
    map<int,int>::iterator got= A.find(n);
    if(got!=A.end())
    {
        return got->second;
    }
    else
    {
     //solve the problem and then compute the result. Suppose the result for 'n' is RESULT then
     A[n]= RESULT;
     return A[n];
    }
}

the above code is working fine for small values of "n" but for large values of "n" like n>=100000 its giving runtime error. how to solve this problem.

Also i would like to mention that earlier for memoization i used simple array but that lead to a lot of wastage of space and also it did not work in cases when "n" took large values like upto 10^9. Guys can u help....

suppose we are applying memoization in which we check if we have already calculated the value for some value of N. If yes we simply return that value; like if DP[N]>-1 return DP[N] else compute for N and store it in DP[N].

But how to apply memoization when N is too large upto 10^9. After all we cant have size of array DP[] upto 10^9.

guys can u suggest me the different maximum values of N so that my program runs in time limit of 2 second for different complexities!!! Like if my complexity is O(N) then whats the maximum N for which my program would run in 2 second time limit? Similarly please also tell maximum N for O(N^2), O(N^3), O(logN), O(N*logN), O(2^N), ......etc.

     A derangement of n numbers is a permutation of those numbers in which none of the numbers appears in its original place. For example, the numbers {1,2,3} can be deranged into {2,3,1} and {3,1,2}. We can modify this slightly for n numbers that are not necessarily distinct by saying that no number in the derangement can be in the place that a number of the same value was in in the original ordering. So the numbers {1,1,2,2,3} could be deranged into {2,2,1,3,1}, {2,2,3,1,1}, {2,3,1,1,2}, and {3,2,1,1,2}. Write a program that takes a series of numbers and outputs the number of derangements of nums.

sample input: {0,0,0,0,0,0,0,1,1,1,1,1,1,1,2} sample output: 14

sample input: {0,5,4,2,3,6,6} sample output: 640

now how to solve it??? can anyone give a detailed solution..

suppose we are given two integers M and N such that k1+k2+k3....kM= N

where k1,k2,... are non-negative integers. now we have to print all possible unique combinations along with the numbers of occurence of each combination. for example M= 3 and N=7 so the combinations goes like-

007 3 (3 means 007, 070, 700, 0+0+7=7)

016 6

025 6

034 6

115 3

223 3

...... and so on...

now what is the fastest way to output all the combinations given the integers M and N. M and N can be large...