Given a list of words and q queries are given . In each query i am given a string and i have to tell which strings are combination of two or more words from the initial given words. I am solve this if each word is a combination of two mords using hashing and extend it to more words case using dp. Does there exists a better solution somewhat linear in the number of words using some advanced data structure?

eg.

a

b

c

1

abc

Output

yes

https://www.hackerrank.com/contests/ncr-codesprint/challenges/flexible-tree-visitor-pattern

I am unable to get it right , can someone share their accepted code? The solutions are not visible and no editorial is provided.Your help is highly appreciated!! Please help !! Just share your code.

I was trying to solve this question of dynamic programming using the convex hull trick .

http://codeforces.me/contest/319/problem/C .

Here is a link to my implementation which got accepted.

http://codeforces.me/contest/319/submission/23071655.

But this submission is raising more concerns .In the query part of the struct i made for cht , i know i am supplying lines whose slope are continuously decreasing with x.So the query part is a kind of pointer algorithm which evaluates the intersection between the last two lines in the hull and moves forward if it finds it adequate because the points in which i am eveluating the lines are strictly incresing.But the problem is that i am popping lines in the insert part so suppose we have 4 lines in the hull and the cur pointer is at the last line.The next inserted line comes and pops everything but the last one so what cur was previously pointing does not exist , so this code should have given RTE , but why not ? I hope some experienced person might look through this code explaining why this didn't happen as well as whether my code is fully correct because i tried to make this one for the case too where the slopes are equal which is not demanded in this question.

You have a string of length 10^5 which is a binary representation of a number.The string has no leading zeros like 11001 represent the number 25. We have to represent it as sum of numbers of the form of 2^x or -2^x (x>=0) . Find the minimum number of numbers needed to do so. Please highlight the states you use and the transitions when replying !

I was trying to solve the question http://codeforces.me/contest/117/problem/E

I coded it but in one of the test cases my answer is differing from jury but i think that the jury's answer is not in accordance with the question ( I know that i am wrong because many people have got ac on that problem ) so i request the commumnity to solve my doubt.In the last case where the path from 5 to 6 is asked there are two paths

5 -> 6

5 -> 4 -> 3 -> 6

the smallest one is the first one while the lexicographically smallest one is the second one.The question asks to find the smallest path first so 5->6 shold be taken and the number of components is 5 which are {3},{4},{5,6},{1},{2} but the answer is 3 which is got when we take the second path ? Why . The first sample case is itself against this.

The test i am refering to is this.

6 4 6 3 4 3 1 5 1 2 5 4 5 6 1 1 3 3 5 2 5 6

PLEASE HELP!!

PLEASE DO NOT GIVE NEGATIVE VOTES . IF YOU ARE NOT WILLING TO HELP PLEASE IGNORE IT

Here i tried to maintain 4 order statistics set with value compresses be coordinate compression , one for row , one fo column ,one for additive sum of coordinates and one for the absolute difference of coordinates . Then to check whether a particular piece can attack the white piece in one move i am checking the domain in which they are identical ( 4 domains as defined above ) and then using pbds whcih is basically a set with additional functionalities i am checking the number of objects between cells . My code is passing on small cases but failing o test 5 . Can someone point the flaw in my approach ?? Thanks in advance

Code : http://codeforces.me/contest/734/submission/22629567

Hi , can someone help me to solve this question , this is a question from the recently held Walmart CodeSprint https://www.hackerrank.com/contests/walmart-codesprint-algo/challenges/digit-minmax-scores

The link is here: http://codeforces.me/gym/100133?locale=en . This gym contains problems of strings but i am unable to get the english version . Can someone help , i was directed by a blog to this link. If you can help translate this to english please do so.Thank you.

Hello community, i am going to start learning flows and matching.Can you all suggest some good resources maybe some lectures , pdfs ,ppts , some well written blogs.What all topics and standard algorithms should i be familiar to solve questions on these topics.

I was solving this question http://codeforces.me/problemset/problem/696/E and my code is passsing in less than a second int max test cases as in test case 10 but it is giving TLE in test case 14 where there is a single node.I am unable to find where it is getting TLE. someone please help and please do not down vote as i have been caught for a while. My submission: http://codeforces.me/contest/696/submission/19464350

I was trying this question "http://codeforces.me/contest/27/problem/E"

Code is giving the correct answer on my machine for values say 1000 but in custom invocation it gives 0

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[12][1005];
int arr[]={0,2,3,5,7,11,13,17,19,23,29};
int base(int num)
{
    ll ans=num;
    for(int i=2;i<=1000;i++)
    {
        if( (ans*num)/num == ans )
            ans=ans*num;
        else
            return i;
    }
}
ll temp[100];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;cin>>n;
    for(int i=1;i<=10;i++)
        for(int j=1;j<=n;j++)
        dp[i][j]=2e18;
    dp[1][1]=1;
    for(int i=2;i<=1000;i++)
    {
        if( (dp[1][i-1]*2)/2== dp[1][i-1] )
            dp[1][i]=2*dp[1][i-1];
        else
            break;
    }

    temp[0]=1;
    for(int i=2;i<=10;i++)
    {
        int till=base(arr[i]);
        for(int j=1;j<till;j++)
            temp[j]=temp[j-1]*1ll*arr[i];

        for(int j=1;j<=n;j++)
        {
            for(int k=0;k<till;k++)
            {

                if((dp[i-1][j] * temp[k])/temp[k] == dp[i-1][j] && j*(k+1)<=n)
                  {dp[i][j*(k+1)]=min(dp[i][j*(k+1)],dp[i-1][j]*temp[k]);}
                else
                   break;

            }
        }
        for(int j=1;j<=n;j++)
            dp[i][j]=min(dp[i][j],dp[i-1][j]);
    }
    cout<<dp[10][n]<<"\n";
}

I was looking through this accepted code and seems that the states of dp are dp[i][j] meaning that the submask i is considered and j is the winner.I am confused about two things.

1. dp[i][j] shouldn't be max(dp[i][j],p[j][k]*dp[i^(1<<k)][j] + p[j][k]*dp[i^(1<<j)][k])
 meaning j is the winner of the mask so j was winner of mask excluding k and defeated k. and k was the winner of mask excluding j and j defeated k.

2. we want 0 to be winner so why we are iterating to get final answer.shouldn't it be dp[(1<<N)][0] 

#include <iostream>
#include <iomanip>
using namespace std;

double p[18][18];
double dp[1<<18][18];

int main()
{
	int N;
	cin >> N;
	for(int i=0;i<N;i++) for(int j=0;j<N;j++) cin >> p[i][j];
	for(int i=0;i<N;i++) dp[1][i] = 0.0;
	dp[1][0] = 1.0;
	for(int i=2;i<(1<<N);i++) for(int j=0;j<N;j++) if(i&(1<<j))
	{
		dp[i][j] = 0.0;
		for(int k=0;k<N;k++) if((i&(1<<k))&&(k!=j))
		{
			dp[i][j] = max(dp[i][j],p[j][k]*dp[i^(1<<k)][j] + p[k][j]*dp[i^(1<<j)][k]);
		}
	}
	double best = 0;
	for(int i=0;i<N;i++) best = max(best,dp[(1<<N)-1][i]);
	cout  << setprecision(20) << best << '\n';
}

THe editorial as well as all solution seems to do the same thing.Can someone explain?

Hey , i was learning persistent segment trees , i got what the concept behind it and now i have to solve problems.I guess people out here might be having some built in templates , can you share yours so that i can see how to efficiently code it as i read that too much pointers can cause TLE.

HOW TO UPDATE RANGES USING LAZY PROPAGATION IN THIS METHOD

Hi , was trying to solve the problem

http://codeforces.me/contest/543/problem/A

using the following algo

for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=b;j++)
            dp[i][j][0]=1;
    }
    for(int k=1;k<=m;k++)
    {
        for(int j=0;j<=b;j++)
        {
            for(int i=1;i<=n;i++)
            {
                dp[i][j][k]=(dp[i-1][j][k]+dp[i][j][k])%mod;
                if(j-arr[i]*1>=0)
                    dp[i][j][k]=(dp[i][j][k]+dp[i][j-arr[i]][(k-1)])%mod;

            }
        }

    }

where dp[i][j][k] means answer for the first i members with maximum error begin j and writing k lines ans is dp[n][b][m] but it's memory is too much.

So i optimised it as

 for(int k=1;k<=m;k++)
    {
        for(int j=0;j<=b;j++)
        {
            for(int i=1;i<=n;i++)
            {
                dp[i][j][k&1]=(dp[i-1][j][k&1]+dp[i][j][k&1])%mod;
                if(j-arr[i]*1>=0)
                    dp[i][j][k&1]=(dp[i][j][k&1]+dp[i][j-arr[i]][(k-1)&1])%mod;

            }
        }
        for(int j=0;j<=b;j++)
        {
            for(int i=1;i<=n;i++)
                dp[i][j][(k-1)&1]=0;
        }
    }

ans is dp[n][b][m&1] but this is getting wrong answer.Someone help.

This is one of the problems of mathematical expectation. As explained in the editorial we have to calculate the answer based on the number of the inversions of the permutation.

THe first two points in the editorial are clear

1. it is clear that after a Jeff's step inversions will become lower by 1 2. it is clear that after a Furik's step inversions will be on 1 lower with porbability of 0.5, and on 1 greater with probability of 0.5 .

but for the third point i am finding it difficult to comprehend.Generally for finding the total expectation we multiply the thing like some value associated with the object and the probabilty of its occurence and then take the summation over all the cases.(Correct if i am wrong) So how did the third point make sense

3. we have the formula for an answer ansI = 1 + 1 + ansI - 1 - 1 × 0.5 + ansI - 1 + 1 × 0.5

Please explain.

link to problem http://codeforces.me/contest/351/problem/B

any links to similar problems are highly appreciated

I have recently started learning kmp algorithm and really want questions on codeforces for this. Can someone suggest questions from codeforces from KMP?

Given N numbers and K, find out if there exists a subset of numbers such that their bitwise xor is K.

Input

First line contains N and K. The second line contains N space-separated integers A1, A2, ..., AN denoting the N numbers.

Output

Output "Yes" if such subset exists, "No" otherwise.(without quotes) Constraints

1 ≤ N ≤ 200

1 ≤ K,Ai ≤ 10^9

Example

Input: 4 101

1 2 100 1000

Output: Yes

Explanation

Example case 1. We can take xor of 1 and 100 to get 101 Note

Bitwise xor of a subset A1, A2, .., AN is equal to (..(A1 xor A2) xor A3).. AN).Each bit of bitwise xor of two numbers is calculated separately. The result in each position is 1 if only the first bit is 1 or only the second bit is 1, but will be 0 if both are 0 or both are 1. For example, bitwise xor of 1(01) and 3(11) is 2 (10).

link for problem: https://www.codechef.com/problems/XORSACK

I am unable to solve the question https://www.hackerrank.com/contests/codeagon/challenges/jesse-and-two-strings-

The editorial is clear to me upto the point where i encounter the following statement After finding the LPS for the both the strings, we traverse through L(i,i)=Length of LPS,∀i=0...N−1 and see what all the middle characters can both the LPS's have. Can someone explain me this? Thanks.

my submission:

http://codeforces.me/contest/472/submission/15130187

is getting TLE on test 10.I have founded the minimum spanning tree and then calculated the distance between each pair of nodes using BFS.

Hi, i was trying to solve the problem http://www.spoj.com/problems/FINDSR/

This problem is the application of failure function of KMP. The function block given below (i got in one of the blogs) aims to calculate the failure function:

void table(string p){

lld length = p.size();
v[0]=0;  
v[1]=0;  
lld cur=0;
for(lld j=2;j<length;j++){
    while(cur!=0 && p[cur]!=p[j-1])
        cur=v[cur];

    if(p[cur]==p[j-1])
        cur=cur+1;

    v[j]=cur;

}

lld length_substring = length - v[length-1]-1; // i am caught in this statement

}

// v[length-1] holds the the length of the longest proper prefix which matches the longest proper suffix from [0,length-2] for example for: abcabcabcabc v[length(12)-1]=v[11]=8; which is visible in the substring (abcabcabcab) length of the longest proper prefix which matches the longest proper suffix is of length 8(abcabcab)

problem is about the intuition of calculating the length of the repeating substring lld length_substring = length — v[length-1]-1;//formula simplifies to length_substring = 12-8-1=3; which clearly is the length of(abc)

Can someone explain me the intuition behind the formula of getting the substring as well as suggest some problems on codeforces to strengthen the concepts. Thanks in advance.

Hey i am getting tle on test 66. My code: Please anyone suggest any optimization http://codeforces.me/contest/229/submission/14839811

I was trying to solve a question through hashing.When I used ll P1=1000000009,M1=1000001011 where i converted the string into P1 based number system and took modulo by M1 i got wrong answer on test 14 but the same code replaced with ll P1=257,M1=1000000007 passes the system tests. I know that the wrong answer would be because of collision So my question is how to know of what values to hash from before solving a question.Are there any set of values which give better performance in certain type type of questions? (ll means long long)

I was trying to solve subsequences http://codeforces.me/problemset/problem/597/C of Testing Round #12 but could not figure out the solution.Can anyone explain the solution using binary indexed tree.

Hey i was trying to solve King's Path on codeforces http://codeforces.me/problemset/problem/242/C but i am getting wrong answer on test 10; my code: http://codeforces.me/contest/242/submission/14186492

Can anyone point my mistake? Thanks.

I am having problem understanding how we are utilising Binary Indexed tree to solve the problem.The DFS part is clear as well as the notion of levels. But i am unable to understand how BIT is used. http://codeforces.me/contest/383/problem/C link.