Hi Folks,

I wrote the this solution for this Tree Constructing but i kept getting runtime error during the contest. Though i managed to get my solution accepted by changing few things but still did not understand why i was getting runtime error. Can anybody help here ?

Hi Coders,

I am trying to solve a problem but couldn't come up with a better solution.

Problem Statement

Given an array A of N integers and Q queries where 1 ≤ A_i ≤ 100, 1 ≤ N ≤ 10⁵ & 1 ≤ Q ≤ 10⁵. Each query gives L and R(a subarray of array A). For each query find the minimum X such that A_X > A_{L + X - 1} and L + X - 1 ≤ R.

I tried solving this problem but couldn't come up with a solution better than Q × N. Any help to improve the complexity would be much appreciated.

Hi all,

Can anybody help me understanding the sample test cases given in the problem statement https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1310 ?

Your help will be appreciated.

I want to write a function that accepts one string and one integer and return concatenation of both but i always want integer to be fixed width say 3.

e.g. if string is "jamesbond" and integer is 7, function should return a string "jamesbond007". How to do it in C++ ?

Note: I dont want to write if else and other conditional statements. Thank you.

Let G be a graph so that for every v, deg(v) ≥ k. Show that G contains a path of length at least k and give an algorithm to find such a path.

Hint: Augment a path from both ends until there are no vertices outside the path, that are joined to the end vertices of the path.

Hi Everyone,

I would like to ask all of you about the cause for this kind of strange behaviour of my code with respect to little change.

I have made submission to the following problem Rebuild (January Clash Contest). I have made the following submission at first link here and got following result.

I thought and checked for the possible reason of segmentation fault but could n't find one as everything was correct according to me then suddenly i made one small change and woohhhh amazingly it worked and the change was ..

I am still not convinced with whatever happened to me. After all what possible difference an "equal to" can cause in this case. Please explain ?

Hi Codeforces,

Can anybody help me with the following problem ?

Reduced Problem Statement

Given 2 integers N and K. We are asked to print the lexographically smallest permutation of first N natural number such that abs(i - pos_i) ≥ K for every if it exists where pos_i is the position of i^th element in the permutation.

Constraints:

1 ≤ N ≤ 10⁵

0 ≤ K ≤ N - 1

Example

Input:

3

2 2

3 0

3 1

Output:

-1

1 2 3

2 3 1

Explanation

For the first test case, N = 2 and K = 2. It is impossible to permute [1, 2] in any way such that abs(P[1]-1) >= 2 and abs(P[2]-2) >= 2. Hence, output is -1.

For the second test case, N = 3 and K = 0. We can just set P[i] = i, and hence the answer is 1 2 3 For the third case, the valid permutations are [2, 3, 1] and [3, 1, 2]. The answer is [2, 3, 1] since it is lexicographically smaller than [3, 1, 2].

Hello everyone,

I am trying to improve the time complexity of the following simple problem.

Problem:  Given an array A consisting of N positive integers. For each K where (1 ≤ K ≤ N) find the largest sum sub array of size K. You just need to output the largest sum for each size K.

Sample Input:
4
1 3 2 1

Sample Output:
3 5 6 7

Any solution or idea better than O(N^2) is welcome. Any help will be appreciated.

Hi frendz,

Recently one of my friend ask me following question which i am unable to solve efficiently. I am putting that question here.

PROBLEM : Given N points in 2 dimensional plane and Q queries each containing a point X in the 2 D plane. Find the minimum distance of this point X from the given N points.

NOTE If anyone has any solution considering either Eucledian distance or manhattan distance. Please post it here.

Any help will be highly appreciated.

Hello codeforces community,

problem link

mysolution link

I tried the following solution in this problem and got TLE for the subtask2. For each union operation i tried to merge smaller size set into bigger size set and added element to the corresponding balanced bst. so for each union operation i will be taking time O((number of element in smaller size set) * (log(element in the bigger size set)) and find the kth element in O(log(size of given set)). what is the worst case complexity of this solution ? I think it is O(N*log^2(N)) amortized. O(N*log^2(N)) was it unacceptable ? Please help me.

Hello frendz,

I have decided to learn java during my summer vacation. I want to master java as much as I can. So, please suggest me some good strategies to accomplish this task.

Main purpose of this post is to ask you for best study material, readings, or some books. Please reply fast as I want to start as soon as possible.

Looking forward for your valuable comments.

Hello Frends ,

This problem is from the last hack contest on hackerrank. Here is the link

contest link

Problem Link

Problem Statement

HackerRank is conducting a teamed programming contest. The rules of the contest are a bit different than usual:

A team consists of exactly N members. Problemset contains exactly N problems and each team member must solve exactly 1 problem. Only one member from the team is allowed to read the problem statements before the contest start time. Note that not everyone have read the problems at first. So, to solve problems a member needs to know the statements from some teammate who already knows them. After knowing problems once, a member is eligible to explain them to other teammates ( one teammate at a time ). You can assume that the explaining ( 1 or N problems ) will always take D minutes. During explaining, none of the two involved members will be able to do anything else.

Problems are of different difficulty levels. You can assume that it will take Ti minutes to solve the ith problem, regardless of which member solves it.

Given a team's data, what is the minimum possible time in which they can solve all problems?

Input Format

The first line will contain T, the number of test cases. The first line of each test case will contain space-separated integers N and D. The second line will contain N space-separated integers, where the ith integer denotes Ti.

Constraints

1≤T≤20

1≤N≤3×10^3

1≤Ti,D≤10^9

Output Format

For each test case, output the minimum possible time in which the given team will be able to solve all problems in a separate line.

Sample Input

1

2 100

1 2 Sample Output

102

Explanation

Member 1 is allowed to know problems before start time. He starts explaing problems to member 2 when contest starts. Explaining ends at the 100th minute. Then both of them immidiately starts solving problems parallely. Member 1 solved 1st problem at the 101th minute and member 2 solved 2nd problem at the 102th minute.

I have also copied problem statement along with the problem link. I am just unable to solution mentioned in the editorial. Also it is mentioned this problem can be solved with better complexity :). I am interested in learning both approaches. If anyone of you can help me :).

Hello everyone ,

I am trying to read this top coder tutorial and understood the working of KMP algorithm completely.

I have found this problem at the end of this post.

A typical problem seen quite often is: given a string find its shortest substring, such that the concatenation of one or more copies of it results in the original string. Again the problem can be reduced to the properties of the failure function. Let’s consider the string

A B A B A B

and all its proper suffix/prefixes in descending order:

1 A B A B
2 A B
3 /the empty string/

Every such suffix/prefix uniquely defines a string, which after being “inserted” in front of the given suffix/prefix gives the initial string. In our case:

1 A B
2 A B A B
3 A B A B A B

Every such “augmenting” string is a potential “candidate” for a string, the concatenation of several copies of which results in the initial string. This follows from the fact that it is not only a prefix of the initial string but also a prefix of the suffix/prefix it “augments”. But that means that now the suffix/prefix contains at least two copies of the “augmenting” string as a prefix (since it’s also a prefix of the initial string) and so on. Of course if the suffix/prefix under question is long enough. In other words, the length of a successful “candidate” must divide with no remainder the length of the initial string.

So all we have to do in order to solve the given problem is to iterate through all proper suffixes/prefixes of the initial string in descending order. This is just what the “failure function” is designed for. We iterate until we find an “augmenting” string of the desired length (its length divides with no remainder the length of the initial string) or get to the empty string, in which case the “augmenting” string that meets the above requirement will be the initial string itself.

This is what i have understood from the solution : use KMP failure function and find each suffix/prefix of the initial string and then for each of the suffix/prefix p that satisfies the |s|%|p| == 0. construct the string and check it against the given string. If you find any valid string (choose the best one) otherwise the answer is original string itself. Am i right ?? Can anybody explain it in a better way or can someone provide me link to the above problem. I think i have understood the idea wrongly otherwise same thing can also be done each prefix of the initial string once (i know that time complexity of this will be O(N^2)). what will be the time complexity of the solution described in the post ? Please help

Hello cool coders out here ..

Round Div1 299 was the first round when i am able to solve problem B during the contest itself and i feel very motivated after this. I want to be consistent at solving B during contest like i am on solving A. So, Suggest me something to keep myself consistent. I am eagerly waiting to read your valuable comments :). I was not much focussed during the last contest but still i solved two problems (it was really an amazing experience for me) or may be problem A and B were easy.

Hello friends ,

I have decided to learn some new stuff in my mid semester break. So, it will be great if some of you can share some problems related to dynamic programming on tree. Although i am not much familiar with this topic so i want some useful links to learn the tricks involved in dynamic programming on tree .

Looking forward for your comments.

Problem Name : Cinema Problem Link : http://mirror.codeforces.com/contest/200/problem/A Tutorial Link : http://mirror.codeforces.com/blog/entry/4769

I am trying on this problem but not able to come with an idea. I thought of decomposing this |x2-x1| + |y2-y2| but that does not work in this case as we need to find the nearest coordinate not the farthest one.

I saw some simple short solution for this problem but not able to get any of those solutions. Please help me.

Any kind of help will be appreciated. :)

for ex : http://mirror.codeforces.com/problemset/problem/56/A

I want to have a look at solutions of other coders for this problem so that i can improve my implementations skills .

Hello frendz,

Can anyone help me solving this problem. I find some similar solution on the submissions page of this problem but not able to understand any of those solution. Please help.

problem link here

Problem statement : Its Ignus and Timo wants to take part in BreakThrough which is the city wide treasure hunt. As a part of a task in the hunt Timo has to visit some malls in the city.

N malls were situated in a row. Timo has to visit K malls. But as she is running out of time she does not want to visit two consecutive malls.

How many different combinations of malls should Timo consider? Input

The first line contains an integer T — the number of test cases. Next follow T lines, each containing two space separated integers, N and K. Output

For each test case, output a single integer representing the number of combinations of malls.

Output the answer modulo 100003. Constraints

1 ≤ T ≤ 10 1 ≤ N ≤ 10^16 1 ≤ K ≤ 10^16

Sample Input:

Input: 2 5 2 5 3 Output: 6 1

Explanation

For the first test case: vovoo

voovo

vooov

ovovo ovoov oovov For the second test case: vovov where v are the visited malls.

Hello all ,

I formulate my solution for this problem during the contest itself but got WA . Here is my solution i basically form equation of line using 2 point form and find the number of distinct line segment. more formally values of coefficient A , B , C are calculated.

#include 
using namespace std ;
#define LL long long int
#define ft first
#define sd second
#define PII pair
#define MAXN 200005
#define MAXM 10000001
#define mp make_pair
#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)
#define sc(x) scanf("%d",&x)
#define scll(x) scanf("%lld",&x)
#define pr(x) printf("%d\n",x)
#define pb push_back
#define MOD 1000000007

vector A ;
vector > B ;
int main(){

    int N , X , Y ;
    sc(N) ; sc(X) ; sc(Y) ;
    A.resize(N+1) ;
    B.resize(N+1) ;
    for(int i=1;i<=N;i++){
        sc(A[i].ft) ;
        sc(A[i].sd) ;
    }
    set > S ;
    for(int i=1;i<=N;i++){
        B[i].ft.ft = A[i].ft - X;
        B[i].ft.sd = Y - A[i].sd ;
        B[i].sd = B[i].ft.sd * X + B[i].ft.ft * Y ;
      WA  int com = __gcd(__gcd(abs(B[i].ft.ft),abs(B[i].ft.sd)),abs(B[i].sd)) ;
      AC  int com = __gcd(__gcd((B[i].ft.ft),(B[i].ft.sd)),(B[i].sd)) ;
        B[i].ft.ft /= com ;
        B[i].ft.sd /= com ;
        B[i].sd /= com ;
        if(B[i].ft.ft < 0){
            B[i].ft.ft = B[i].ft.ft * -1 ;
            B[i].ft.sd = B[i].ft.sd * -1 ;
            B[i].sd = B[i].sd * -1 ;
        }
        S.insert(B[i]) ;
    }
    cout << S.size() << endl ;
    return 0 ;
}

I have highlighted two lines. I used above one during the contest and got WA. Later, i changed it to below one and got AC.

I know that gcd(a,b) = gcd(-a,b) = gcd(a,-b) = gcd(-a,-b) = gcd(|a|,|b|). Can anybody tell me why was i getting WA. Thanks in advance ..

Hello frendz ,

Can anyone tell me how to solve this problem .

A Computer Science Engineer from SKIT has been assigned a problem by his Maths Lecturer to find the number of pairs (a,b) within a given range N such that the sum of the two numbers divides the product of the two numbers.

Input:

The first line of the input contains an integer T, denoting number of test cases, only to be followed by T lines. Each of the following line contains the upper limit of range i.e. N

Output:

For each test case, output a single line containing the number of such pairs.

Constraints:

1 <= N <= 10^5 1 <= T <= 10

Sample Input (Plaintext Link) 2 2 15 Sample Output (Plaintext Link) 0 4

Hello all ,

I have written this code for the problem Aurthor and Brackets link but don't know why i am getting MLE on 9th test case . Can anyone help me please ..

My code ..

#include 
using namespace std ;


#define MAXN 605 
#define sc(c) scanf("%d",&c)
#define pr(s) printf("%d\n",s) 


int DP[MAXN][MAXN],Pos[MAXN][MAXN],N,L[MAXN],R[MAXN] ;
string ans ;

int solve(int start,int end){
	int &ret = DP[start][end] ;
	if(end < start){
		ret = 1 ;
	} 
	if(end == start){
		if(L[start] > 1){
			ret = 0 ;
		}else{
			ret = 1 ;
			Pos[start][end] = start ;
		}
	}
	if(ret != -1){
		return ret ;
	}
	ret = 0 ;
	for(int i=L[start];i<=R[start];i++){
		if(i%2){
			if(solve(start+1,start+i/2) && solve(start+i/2+1,end)){
				ret = 1 ;
				Pos[start][end] = start+i/2 ;
			}
		}
	}
	return ret ;
}

void construct(int s,int e){

	if(s > e){
		return ;
	}
	ans += '(' ;
	int mid = Pos[s][e] ;
	construct(s+1,mid) ;
	ans += ')' ;
	construct(mid+1,e) ;
	
}
int main(){

	sc(N) ;
	for(int i=1;i<=N;i++){
		sc(L[i]);
		sc(R[i]) ;
	}
	memset(DP,-1,sizeof DP) ;
	if(solve(1,N)){
		construct(1,N) ;
		cout << ans << endl ;	
	}else{	
		printf("IMPOSSIBLE\n") ;
	}
	return 0 ;
}

Hello Fellas ,

I am trying to solve this problem from Quora Hackathon but not able to come up with a idea .. how to appraoch it ?

Can any one help ..

Just for the convenience i have copied the problem statement here otherwise you can use this link

Problem Statement

For the purposes of this problem, suppose Quora has N questions, and question i (1≤i≤N) takes Ti time to read. There exists exactly one path from any question to another, and related questions form undirected pairs between themselves. In other words, the graph of related questions is a tree.

Each time Steve reads a question, he will see a list of related questions and navigate to one that he hasn't read yet at random. Steve will stop reading once there are no unread related questions.

Which question should we show first to Steve so that we minimize his total expected reading time? It is guaranteed that there is one unique question that is optimal.

Input Format

Line 1: A single integer, N

Line 2: N integers, Ti

Line 3...N+1: Each line contains two integers A, B indicating that question A and B are

related

Output Format

Line 1: A single integer, X, the best question to show first.

Constraints

1≤N≤105

1≤Ti≤106

Sample Input

5

2 2 1 2 2

1 2

2 3

3 4

4 5

Sample Output

3

Hello all ,

Hope you all are doing well .

I am looking for an efficient way to multiply two numbers A and B mod C where A,B,C can be in the range [1,10¹⁵] .

Here are the list of the solution which i think can think off but there must be some more fast methods .

Solution 1 : simplest and easiest solution is two switch language to jave,python or to use big int in c++ . I don't fill it is a good technique and would like to do it in c .

Solution 2 : Russian Peasant Multiplication

long long int mulmod(long long int a,long long int b) {
    if (M <= 1000000009) return a * b % M;
 
    long long int res = 0;
    while (a > 0) {
        if (a & 1) {
            res += b;
            if (res >= M) res -= M;
        }
        a >>= 1;
        b <<= 1;
        if (b >= M) b -= M;
    }
    return res;
}

which works in O(log(min(A,B))) time .

I heard of karatsuba algorithm which is very fast. Is it faster than the russian multiplication .. can anyone provide me some implementation stuff or some motivation ..

Any kind of help is appreciated :D :D

EDIT1

EDIT2

long long int mulmod(long long int val, long long int n,long long int mod)
{
    long long int q=((double)val*(double)n/(double)mod);
    long long int res=val*n-mod*q;
    res=(res%mod+mod)%mod;
    return res;
}

Hello Everyone,

I am trying to solve this problem from Pledge contest going on HackerEarth. I got stucked on this problem http://www.hackerearth.com/tracks/pledge-2015-medium/tree-coloring/ . So, I decided to read the editorial and coded all the thing as mentioned but do not know why i am getting wrong answer. Even my code is exactly similar to the author code . Can anyone help me please.

It has been 4 hours since i am doing this question.. help me ..

Here is my code http://ideone.com/cl9E09

Author solution link : http://ideone.com/eEyDYc

I was solving a simple DP problem ..

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example: S = "rabbbit", T = "rabbit"

Return 3.

I made a recursive code which is like this ..

I initialise the DP array with -1 and used one based indexing in DP matrix ..

 int solve(string S,string T,int N,int M){
if( M <= 0)
        return 1 ;

    if( N <= 0 )
        return 0 ;

    int &ret = DP[N][M];
if(ret != -1)
    return ret ;
ret = 0 ;   
    if(S[N-1] == T[M-1]){
        ret += (solve(S,T,N-1,M-1)+solve(S,T,N-1,M)) ;
    }else{
        ret += (solve(S,T,N-1,M)) ;
    }

    ret ;
} 

I was not getting correct answer then i changed my code and prepared a bottom up code which is this ..

int solve(string &S,string &T,int N,int M){

	
	for(int i=0;i<=N;i++)
		for(int j=0;j<=M;j++)
			DP[i][j] = 0;

	for(int i=0;i<=N;i++)
		DP[i][0] = 1;

	for(int i=1;i<=N;i++){
		for(int j=1;j<=M;j++){
			if(S[i-1] == T[j-1])
				DP[i][j] += DP[i-1][j-1] ;
			DP[i][j] += DP[i-1][j] ;
		}
	}
	return DP[N][M] ;
}

I got AC with this solution ..Essentially the same as previous one ..

I am still unable to find a bug in my previous code so can anyone help me please ..

Thanx in advance