As-salamu alaykum, Codeforces! (Peace, Codeforces!)

I am glad to invite you to HackerEarth December DSA Contest. The contest is rated and will start on 11 December at 10:00 AM BDT. In the contest will be given 3 problems to solve in 90 minutes. All the problems are prepared by me and lucky_21, and I hope that you will like them.

I would like to thank Arpa for coordinating and testing the round.

As always, thanks to MikeMirzayanov for polygon platform.

hello everyone

i'm trying to sort a vector using an explicit compare function

why does this simple code gives me Runtime Error sometimes and sometime Time Limit Exceeded

https://ideone.com/MpRvD9

hello codeforces

this problem 917A - The Monster has only a greedy solution which is well explained in the editorial

however i want to introduce a Dynamic programming solution

O(N^4) DP solution : 34679276

Explanation :

the boolean solve function finds out if a certain substring can be a valid sequence of brackets

if it finds a question mark it treats it like an open bracket then a closed bracket

complexity O(n^2)

the main function calls the solve function for every different substring which is nearly

N^2 substring

so the overall complexity is O(N^4)

O(N^3) DP solution : 34680960

Explanation :

like the previous solution the main function calls solve function n^2 times but this time

solve function is O(n^2) n times and the rest of the calls is O(1)

Nearly O(N^2) Accepted DP solution : 35227974 i know that this solutions seems very weird compared to the previous solutions but actually it's doing the same thing efficiently Explanation:

now we know that in the previous solutions solve(pos,nopen) goes to

states solve(pos+1,nopen+1),solve(pos+1,nopen-1)

if string[pos] was a question mark and solve(pos,nopen) goes to solve(pos+1,nopen+1)

if it was an open bracket

and solve(pos+1,nopen-1) if it was a closed bracket

now let's put all these states in an array

example :

if the input string was "((?)"

the array should contain:

[0] meaning solve(0,0)

then

[1] meaning solve(1,1)

then

[2] meaning solve(2,2)

[1,3] meaning solve(3,1) and solve(3,3)

[0,2] meaning solve(4,0) and solve(4,2)

notice that we don't need to save the first parameter in the array as all states has the same level

now we observe that if there's an open bracket we have to increase all array elements by 1 and -1 in case of closing

and in case of question mark all states is increased by 1 and new state is added which is

equal to first state -2

prove it for yourself on a sheet of paper

now after every iteration we only have to increment our answer if there's an element in the array =0

hope you got it

important notes :

-please feel free to comment if you find any mistake in my blog

-i'm not really good at writing blogs so i'm sorry if you find bad styling or poor english

-i hope that this workaround help anyone optimizing similar DP solutions

-it took me around a month to come up with this solution and i really want to know if i'm doing problem solving efficiently

thanks

hello codeforces i'm trying to solve a hard problem and this is my 25th submission :

http://codeforces.me/contest/794/submission/27321156

i believe that i'm too close to the right solution

can anybody tell me what's wrong with my code

and i want to know if solving hard problems better or problems at my level "like C" problems

thanks

hello codeforces

i was wondering why do i have to use int while long long is more useful

today i found the answer :

using long long :http://codeforces.me/contest/543/submission/22092332

using int : http://codeforces.me/contest/543/submission/22092593

hope this help

thanks

i had runtime error in this submission and i was going crazy finding where the error is

after 2 hours of debugging and tracing .. i didn't find the problem .. i did something stupid and the problem got accepted .. i don't know why actually ...

does any one knows where was the error in the first code ? ?

and why C++ behaves like that

run time error : http://codeforces.me/contest/706/submission/20629423

accepted :http://codeforces.me/contest/706/submission/20629645