eagle93's blog

How to solve UVA 12800 — Cut
By eagle93, 10 years ago, In English

problem link: here

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

Any hints will be appreciated!

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

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

          → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          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.

          → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it 
      int remaining(int L, int R)
{
   int res = 0;
   while (L != R) {
      ++res;
      L = (L + 1) % n;
   }
   return res / 2 -2;
}
      → Reply
»
10 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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!

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

→ Reply