red_coder's blog

By red_coder, 9 years ago,

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

• -3

By red_coder, 9 years ago,

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 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++].time=eve[i].time;
}
}
sort(ans,ans+u,cmp2);
f(i,0,u)
{
printf("%d\n",ans[i].val);
}
}



• -26

By red_coder, 9 years ago,

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 :)

• -3

By red_coder, 9 years ago,

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.com/contest/280/problem/A

• +3

By red_coder, 9 years ago,

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.

• -5

By red_coder, 9 years ago,

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

• -1

By red_coder, 9 years ago,

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());
}



• 0

By red_coder, 9 years ago,

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.

• -19

By red_coder, 9 years ago,

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?

• -1

By red_coder, 9 years ago,

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

• -20

By red_coder, 9 years ago,

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++....

• -20

By red_coder, 9 years ago,

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).

• -1

By red_coder, 9 years ago,

Can anyone pls tell me how to solve this problem

• +3

By red_coder, 9 years ago,

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...

• 0

By red_coder, 9 years ago,

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

• -5

By red_coder, 9 years ago,

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 :)

• +2

By red_coder, 9 years ago,

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.....

• -10

By red_coder, 9 years ago,

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...

• -17

By red_coder, 9 years ago,

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!!!

• -2

By red_coder, 9 years ago,

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

• -2

By red_coder, 10 years ago,

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....

• 0

By red_coder, 10 years ago,

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.

• +14

By red_coder, 10 years ago,

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.

• +8

By red_coder, 10 years ago,

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..

• +2

By red_coder, 10 years ago,

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...