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

# | User | Rating |
---|---|---|

1 | tourist | 3624 |

2 | Um_nik | 3468 |

3 | mnbvmar | 3363 |

4 | Petr | 3330 |

5 | wxhtxdy | 3329 |

6 | LHiC | 3300 |

7 | sunset | 3278 |

8 | V--o_o--V | 3275 |

9 | Vn_nV | 3182 |

10 | dotorya | 3156 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 191 |

2 | Errichto | 184 |

3 | rng_58 | 160 |

4 | PikMike | 159 |

5 | Petr | 156 |

6 | Ashishgup | 153 |

6 | Vovuh | 153 |

6 | neal | 153 |

9 | Um_nik | 152 |

10 | majk | 151 |

10 | 300iq | 151 |

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

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 : [submission: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 : [submission: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 : [submission: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.com/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.com/contest/543/submission/22092332

using int : http://codeforces.com/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.com/contest/706/submission/20629423

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

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/22/2019 14:19:23 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|