Блог пользователя eagle93

Автор eagle93, 9 лет назад, По-английски

problem link: here

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

Any hints will be appreciated!

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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?

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      ok. DP(L, R, numberOfCuts)

      int cuts = n / 2 +-1;
      for (i = 0; i < n; ++i)
         for (int j = i; j < n; ++j)
            for (int k = 0; k <= cuts; ++k)
               res = min(res, D(i, j, k) + D(j, i, cuts - k));
      

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

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 :)

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          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)...

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          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.

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
      int remaining(int L, int R)
      {
         int res = 0;
         while (L != R) {
            ++res;
            L = (L + 1) % n;
         }
         return res / 2 -2;
      }
      
»
9 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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!

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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