### orchidmajumder's blog

By orchidmajumder, 9 years ago,

Hi,I'm trying to solve this problem.It asks for point update and range query where the query is sum of distinct numbers in a given range.

Is this type of problem solvable by normal segment tree or do we need any kind of persistent data structure to do this?? I don't have much idea about persistent data structures.

Any help will be appreciated very much :)

• +14

By orchidmajumder, 9 years ago,

Hi,

I want to know is there any dynamic programming or any other approach to find if there is any subset with a given xor(just like we have dynamic programming approach to find if there is any subset with a given sum) ?

UPD: I have solved this problem with a similar approach to subset sum dynamic programming.

• +5

By orchidmajumder, 9 years ago,

Hi,

I'm trying to solve this problem from SPOJ.

SPOJ-TREEBA

My idea is to run Aho-corasick algorithm to find all intervals [a,b] in the text which contains one word from the dictionary and then to run a greedy interval scheduling to find the maximum number of non overlapping intervals.If this count is <=k ,I'm outputting it as answer.else I am outputting ( k+1) as k noises can accommodate k+1 words at max,So,if we have number of non overlapping intervals > k+1 we can just consider some of those words as noises and can find k+1 words.I think the last greedy decision part is causing me WA.

I'll be very happy if somebody can point out my mistake.This is the first time I'm using Aho-Corasick algorithm,so not much experience as such.

• 0

By orchidmajumder, 9 years ago,

I want to ask how to apply a segment tree in a question like where instead of updating a range [a,b] by a constant v,we are told to update the range in such a way that i is added to i th box in the range [a,b] ,i=1..(b-a+1).

say,for example,this problem in SPOJ.

Impossible Boss

Any pointers will be appreciated.If there is any approach other than seg tree,I'd like to know that also.

• +3

By orchidmajumder, 9 years ago,

Hi,

I was trying to solve this problem of finding no of possible ways of changing a value n.

http://www.spoj.com/problems/TPC07/

http://acm.tju.edu.cn/toj/showp2817.html

now this problem has a constraint of n<=10^9.so,I can't declare an array of that size and run a dp approach.Also,I think this problem will require BigInteger support by seeing the answer for the second test case.

So,any help on how to solve it using C/C++ would be much appreciated.

• +10

By orchidmajumder, 9 years ago,

Hi,

I want to ask that while initializing the potential array for all the nodes in min cost max flow (edmond karp +djikstra potential method) should I initialize all with zero like what is described in the network flow book by ahuja(same is done also in egor's code) or should I run a bellman ford to set those initial values like what's described in topcoder tutorial min Cost Max Flow successive shortest path algorithm???

• 0