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 | 3557 |

2 | Radewoosh | 3468 |

3 | Um_nik | 3429 |

4 | Petr | 3354 |

5 | Benq | 3286 |

6 | mnbvmar | 3280 |

7 | wxhtxdy | 3276 |

7 | LHiC | 3276 |

9 | ecnerwala | 3214 |

10 | yutaka1999 | 3190 |

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

1 | Errichto | 191 |

2 | Radewoosh | 180 |

3 | tourist | 173 |

4 | Vovuh | 165 |

4 | antontrygubO_o | 165 |

6 | PikMike | 164 |

7 | rng_58 | 160 |

8 | Um_nik | 156 |

8 | majk | 156 |

10 | 300iq | 154 |

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 - Монстр 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.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: Oct/20/2019 10:54:13 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|