Hi folks, Got to know about this problem from a friend. It was asked in codenation's coding round/interview last year.

Any leads on a better approach than $$$O(n^2)$$$ will be appreciated.

Question — You are given n strings and q queries. Each query is also in the form of a string (say $$$q_i$$$). You have to reply with true if this string can be formed by concatenating any of the n strings given earlier.

For example — Suppose $$$n = 3$$$ and the strings are $$$abc$$$ , $$$bc$$$ and $$$cd$$$.

So $$$abcabc$$$ is a valid string because you can use $$$abc$$$ twice. (There is no constraint on the number of times you can use any given string.)

Also, $$$bccdabc$$$ is a valid string as we can use the given strings in the order $$$2$$$, $$$3$$$ and $$$1$$$.

Sum of all the strings in query is $$$\leq 10000$$$

My friend final_tsu helped me in coming with a $$$O(n^2)$$$ approach using Trie and DP.

Thanks.

Hello CF community,

I have a problem and I don't know how to solve it. Some time back, I took help from some amazing people on codeforces for a problem about finding frequency of a number in a range from l to r. The blog for the same is this — http://mirror.codeforces.com/blog/entry/52578

I was wondering about how can we solve the same problem given we have to keep an eye on updates also this time. The updates are basically range updates (adding x from l to r).

Hello CF community,

In this blog, I look to ask up two things which are somewhat related to my approach for yesterday's Div2 E problem Buy Low Sell High. But before asking about that I need to ask something about segment trees.

My approach for yesterday's problem - First I took all the stock values in a pair array with second index storing actual index. I sorted the array so as to get the least to highest prices keeping lowest index in mind first.

I built a segment tree (max query) then.

The basic idea was to now iterate over the pair array whose first index gives me the stock value (say val) and second index gives actual position (pos) of that stock in the real array. The next thing to do is find the maximum value of stock in array (using segment tree) from pos + 1 to n , say max. Since there is a possibility that there can be multiple position with value max in the array, I took up the closest one to pos. For this, I simply stored all the values of position a particular number in a set and just found the upper bound of pos. If that max value is greater than stock value, cool.. update it, add the difference to answer and keep moving, otherwise just simply continue.

The first submission I made got a runtime error and I wasn't able to understand why it happened. After the contest while trying to upsolve or possibly find out the error, what I just did was change all 2node + 1 to 2node and 2node + 2 to 2node + 1 in my segment tree implementation. Surprisingly the problem now got solved.

So my two questions for this problem and particularly my situation are that why the problem got solved with that little change or in-fact why I got that problem when everything was basically fine and same in my update and query function. Was it something related to memory issues?

Second obviously is why my algorithm is wrong as I am still getting wrong answer?

Problem Link - http://mirror.codeforces.com/problemset/problem/867/E

My runtime error submission - http://mirror.codeforces.com/contest/867/submission/30885275

No runtime error but WA submission - http://mirror.codeforces.com/contest/867/submission/30910560

I guess the heading says everything :)

Problem solved. Thanks MikeMirzayanov and other admins.

Update- Not Completely though.

Hello codeforces community, I was solving this problem (http://mirror.codeforces.com/blog/entry/46425) on codeforces and came across an interesting doubt (at least according to me) . I just wanted to know that is there any algorithm for finding frequency of any number in a particular range in an array?

We use Mo`s Algorithm for finding max frequency in a range but is there any other one which is faster for this particular problem of mine (calculating frequency of any number)?

I tried writing an algorithm for it but I believe its too slow to pass in one second. Although I think that my build takes O (n log n) time and queries come out in O (log n) time but I believe it's the uncertainty of hashing that`s making the algorithm slower.

Here is my code — https://pastebin.com/Ypj90749

Note- Please do not tell me the solutions of the codeforces problem. I have already read the editorial and their implementation is pretty simple. I just want to get an answer for my curiosity to be able to learn a new beautiful algorithm (if there is) and help some other learners like me.

Hi , I have just started learning about graphs to enjoy the world of competitive programming even more and I was trying to solve a problem on graphs 20C - Dijkstra? .

I submitted my code and now its failing on test 31 as you can see in my submission 25347179 . I even tried various ways to get to know why this is happening . I*I even used n=37 , m=36 and then used same data as given in test case 31 , the output that I was getting was correct . I even thought that , it might be because of this long long thing but still I am not getting the GREEN ACCEPTED result .

Will be really good if someone from codeforces community helps me in finding why my code is failing .

Hello codeforces community :)

PROBLEM 1: C++ related

I am beginner who has recently started learning about graphs and for that I was trying to solve out this dfs problem (http://mirror.codeforces.com/problemset/problem/115/A) ..

I wrote a code in C++ which is working fine on my laptop but is giving a runtime error on codeforces .. Can anyone help me out why this is happening and how to sort it out and can someone also list out the possible reasons when and why this kind of error happens , as it will help me in future ... :)

Code Link -> http://pastebin.com/54hFqrMC

PROBLEM 2: Java related

Well my second problem is also related to same question but this time , I need help of people who code in java. Basically , When my solution was not working , I tried to write code for the problem in Java . This time , problem is not about runtime error but lack of knowledge that I am having about how to use iterators and collection frameworks in Java . I am attaching a picture of error I am getting on IntelliJ IDEA and also providing my code . Please do help me out with these 2 problems . :)

Code Link -> http://pastebin.com/42sekm53 Thanks in advance to the best competitive coding community in the world :) ..

Hi , I was going through this problem on SPOJ (http://www.spoj.com/problems/NSTEPS/) , where I was basically trying to practice OOP concepts in c++ . You can see in my code (http://pastebin.com/qubfkgEr) that I defined a point object and also defined a comparing operator for it but when i was running the code on sample tests , find operator in map is not working properly or basically I should say that since I am a newbie to these advanced features of C++ , I am , may be not using comparator function properly . Can anyone help me out to sort this problem .??

If possible , Please also tell me how to tackle this problem in java if some time I encounter it there..

Hi , I am a beginner programmer and i need some help . Basically i was working on a problem on codeforces (Problem Link-> http://mirror.codeforces.com/problemset/problem/600/B)(using java) and i am getting TLE verdict. I am not able to understand why i am getting so as I am using map for insertion and retrieval of values which is a form of red black tree and takes logarithmic time . My code is exceeding limit on test 20 .. Submission link->http://mirror.codeforces.com/contest/600/submission/23908885

Please help me in understanding the reason behind this and if possible , also tell about how to overcome this problem of Time Limit..

Code Link->http://pastebin.com/tH39VQkR

Hi , I am a beginner programmer and i need some help . Basically i was working on a problem on codeforces (using java) and i am getting Null Pointer Excpetion. I am not able to understand the root cause of this problem and how to sort it out..

I tried searching on Internet , and i got a few answers about my problem but after even implementing them , my code is giving the same exception .. Can anyone tell me what is the solution for this problem.. Thanks .. !!

Codelink-> http://pastebin.com/qCxiyeH4

Hi Reader,

I just wrote the solution for this problem (710-B) in Java and I just don`t know that why i am getting a TLE verdict.. Problem link -> http://mirror.codeforces.com/contest/710/problem/B The real reason to worry is that my code is passing one of the tests (where value of n is 300000) but is getting a verdict of TLE where (n is equal to 299999) .. How can this be posssible ?? I have used basic inbuilt sorting algorithm in Java and then one more step of O(n) complexity . So if n is larger , time will also be larger. As it will be directly proportional to O(n) or O(nlogn).. What is the reason behing this , that time is larger in latter case?? Infact , I then solved the problem in C++ where no such unexpected activity is happening and i passed all tests ..

Please help me out with this !! This is my code -> http://pastebin.com/DfYg30zj This is my submission link -> http://mirror.codeforces.com/contest/710/submission/23467650

Can anyone tell me , why I am getting runtime error on test 1 itself ?? Problem link->http://mirror.codeforces.com/problemset/problem/387/B Code link->http://pastebin.com/N3JKSVPj

Can anyone tell me , why I am getting runtime error on test 1 itself ?? Problem link->http://mirror.codeforces.com/problemset/problem/387/B Code link->http://pastebin.com/N3JKSVPj

well this has happened with me in so many problems and i really don`t know the reason behind it. My code fails on a particular test but when i enter that test on my own compiler , the answer comes out to be correct .. Earlier also , this has happened with me many times. 2 days back also , i encountered the same problem as why i am getting a runtime error on test 9 of Problem 659-B http://pastebin.com/UBV4KPf0 This is the link for my code..

Today i got stuck in Problem 725B in test 7 . Again I am getting correct output in my computer but wrong on Codeforces . http://pastebin.com/WuCR3X9p Link for 725-B(My code) Can anyone help me out with this???

This is the attached link for my code..(Problem-659B) http://pastebin.com/UBV4KPf0