problem link: here

I've tried the brute force approach, but TLE for sure :P

Any hints will be appreciated!

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

1 | tourist | 3822 |

2 | Benq | 3745 |

3 | ksun48 | 3560 |

4 | Radewoosh | 3538 |

5 | peehs_moorhsum | 3532 |

6 | Um_nik | 3489 |

7 | maroonrk | 3424 |

8 | Petr | 3380 |

9 | sunset | 3338 |

10 | ecnerwala | 3336 |

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

1 | 1-gon | 206 |

2 | Errichto | 181 |

2 | awoo | 181 |

4 | Um_nik | 180 |

5 | -is-this-fft- | 175 |

6 | maroonrk | 174 |

7 | Radewoosh | 172 |

7 | tourist | 172 |

9 | SecondThread | 170 |

10 | rng_58 | 166 |

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/31/2021 02:32:02 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

It's DP problem. D(L, R).

but how will you manage the cuts?

if n = 5, and you choose L=0, R=5

how will you manage the remaining sub-polygons?

ok. DP(L, R, numberOfCuts)

UPD: just DP(0, 1, cuts). I'm an idiot

your code doesn't use L or R !

also, in this case:

if we have already cut the two red lines, how will we calculate the sub-problem?

thanks in advance :)

Code below DP function declaration is in

`int main()`

body of DP function you should write. first cut was in`main`

. There was update "just DP(0, 1, cuts). I'm an idiot". DP(0, 1, 3) cuts (1, 8) and calls DP(2, 7, 2)...Suppose you are calculating DP(L, R). You know the line from R to L may be a cut (a red line), the other lines of the polygon are actual edges. Also you know the R-L line has to be a part of one quadrilateral.

So for the transition, choose two more points x and y and form the quadrilateral R-L-x-y. You can see that the remaining subproblems will all have at most one cut.

what is the secret behind the negative votes, it's just a question! what does it mean? is the answer is "the question is too easy to answer it ?!" your negative vote has no mean. just makes the weak students frighten from asking again!

Hi All, Please, I need some hints to solve cut(12800) problem

I solve this problem with a dp aprouch : the main idea is that we can define a poligon with two indexes lo , hi lo <= hi that means that we have a convex polygon from lo , lo + 1 , .. hi , lo (the last edge close the polygon) the we can cut between some pair of point of our current polygon (in this transicions we have to conserve that the two halfes of polygon (subproblems) have 2 * n points (n >= 2) )

Finaly we have a O(n^4) complexity.

UPD : Code