Monday, November 3, 2014

UVa Problem 10003 - Cutting Sticks

Problem:

Please find the problem here.

Solution:

First notice this problem is an 'ordering' problem. We are trying to find an order. To determine an order you make a choice which one is the first one to go, and then which is next, and so on.

A little fiddling make me realize the sub-problems are overlapped. It doesn't matter how I get to the state of cutting a stick from the mth endpoint to the nth endpoint, I just have to solve that sub-problem optimally.

So in the view of this, we define the recurrence relation as follow

Let opt(m, n) be the minimal cost of cutting the stick from the mth endpoint to the nth endpoint.

Base case, we have opt(m, m+1) = 0, because there is no need to cut a segment with no internal endpoints.

Inductively, we have opt(m, n) = endpoints(n) - endpoint(m) + min over k (opt(m, k) + opt(k, n)). We have to make a cut anyway and that will always cost us endpoints(n) - endpoint(m) independent on where we choose, and we need to choose one, that minimize subsequent costs.

That's it, given the recurrence formula we can code up the bottom up DP easily.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=944

#include "UVa10003.h"

#include <iostream>
#include <vector>

using namespace std;

int UVa10003()
{
    while (true)
    {
        int stick_length;
        int num_cuts;
        cin >> stick_length;
        if (stick_length == 0)
        {
            break;
        }
        cin >> num_cuts;
        vector<int> endpoints;
        endpoints.resize(num_cuts + 2);
        endpoints[0] = 0;
        for (int i = 1; i <= num_cuts; i++)
        {
            int cut;
            cin >> cut;
            endpoints[i] = cut;
        }
        endpoints[num_cuts + 1] = stick_length;

        vector<vector<int> > opt;
        opt.resize(endpoints.size());
        for (unsigned int i = 0; i < endpoints.size(); i++)
        {
            opt[i].resize(endpoints.size());
        }

        // Initialization - minimal cost of cutting a segment with no cutting point in it is 0
        for (unsigned int i = 0; i < endpoints.size() - 1; i++)
        {
            opt[i][i + 1] = 0;
        }

        for (unsigned int gap = 2; gap <= endpoints.size() - 1; gap++)
        {
            for (unsigned int i = 0; i + gap < endpoints.size(); i++)
            {
                int j = i + gap;
                int segment_length = endpoints[j] - endpoints[i];
                bool first = true;
                int min = -1;
                for (int k = i + 1; k < j; k++)
                {
                    int cost = opt[i][k] + opt[k][j];;
                    if (first)
                    {
                        min = cost;
                        first = false;
                    }
                    else
                    {
                        if (cost < min)
                        {
                            min = cost;
                        }
                    }
                }
                opt[i][j] = segment_length + min;
            }
        }

        cout << "The minimum cutting is " << opt[0][endpoints.size() - 1] << "." << endl;
    }

    return 0;
}

3 comments :

  1. Thanks a lot. This post was really helpful.

    ReplyDelete
  2. Thanks a lot. This post was really helpful.

    ReplyDelete
  3. very nice explanation! saved me a lot of time!

    ReplyDelete