algorithm - TopCoderのFlowerGardenpr0blemはどのようにDP-oneですか？

Question

私はここでDPベースの問題に関するDumitruによるこの優れたチュートリアルを読んでいます。そして、私は1DDP問題のリストに記載されているFlowerGarden問題に対するDPベースのアプローチを考え出そうとしています。

私は、最初に花を順番に並べ替えてから、問題で言及されているさまざまな条件チェックに基づいて花を並べ替える、非DPソリューションしか考えられません。それはDPとして分類されませんね。

社説もDPについては何も言及していません。誰かが、万が一、この問題に対する適切なDPベースのソリューションを教えてもらえますか？

ありがとう！

編集：

リンクに登録が必要だとは思いませんでした。これが問題です：

問題の説明あなたは一年中あなたに楽しい花を与えるために球根で花畑を植えています。ただし、花が見える間は他の花を遮らないように花を植えたいと考えています。

int []の高さ、int []のブルーム、およびint[]のしおれが与えられます。花の種類ごとに、高さ、花、しおれの同じインデックスの要素で表されます。高さは各種類の花の成長の高さを表し、花は各種類の花が地面から湧き出る朝を表し、しおれは各種類の花が縮んで枯れる夜を表します。Bloomとwiltの各要素は、1から365までの数値になり、wilt[i]は常にbloom[i]より大きくなります。同じ種類の花をすべて一列に並べて見せる必要があります。また、できるだけ高い花をできるだけ前方に配置する必要があります。ただし、花の種類が他の種類よりも背が高く、両方の種類が同時に地面から離れることができる場合は、ブロッキングを防ぐために、背の高い花の前に背の低い花を植える必要があります。朝は花が咲き、夕方はしおれますので、同じ日に花が咲いても、もう一方の花がしおれていても、片方がもう片方を塞ぐことができます。

上記の目標を達成するために花を植える順序で、高さの要素を含むint[]を返す必要があります。庭の正面は、戻り値の最初の要素で表され、庭を見る場所です。高さの要素はすべて一意であるため、常に明確な順序があります。

2つ編集：

例1：

height = {5,4,3,2,1}

Bloom = {1,1,1,1,1}

wilt = {365,365,365,365,365}

戻り値：{1、2、3、4、5}

これらの花はすべて1月1日に咲き、12月31日にしおれます。それらはすべて互いにブロックする可能性があるため、短いものから高いものの順に並べる必要があります。

例2：

h = {5,4,3,2,1}

b = {1,5,10,15,20}

w = {4,9,14,19,24}

戻り値：{5、4、3、2、1}同じ花のセットがすべて別々の時間に咲くようになりました。それらは互いにブロックすることはないので、最も高いものから最も短いものの順に並べて、最も高いものをできるだけ前方に配置することができます。

例3：height = {5,4,3,2,1}

Bloom = {1,5,10,15,20}

wilt = {5,10,14,20,25}

戻り値：{3、4、5、1、2}ここでの違いは、3番目のタイプの花は4番目の花の開花より1日早くしおれることです。したがって、最初に高さ3の花、次に高さ4の花、次に高さ5の花、最後に高さ1と2の花を配置できます。最初に高さ1の花を注文することもできますが、そうではありません。その結果、庭で可能な最大の高さが最初になります。

Answer 1

public int[] getOrdering(int[] height, int[] bloom, int[] wilt) {
    int[] optimal = new int[height.length];
    int[] optimalBloom = new int[bloom.length];
    int[] optimalWilt = new int[wilt.length];

    // init state
    optimal[0] = height[0];
    optimalBloom[0] = bloom[0];
    optimalWilt[0] = wilt[0];

    // run dynamic programming
    for(int i = 1; i < height.length; i ++) {
        int currHeight = height[i];
        int currBloom = bloom[i];
        int currWilt = wilt[i];

        int offset = 0; // by default, type i is to be put to 1st row
        for(int j = 0; j < i; j ++) {
            if(currWilt >= optimalBloom[j] && currWilt <= optimalWilt[j] ||
                    currBloom >= optimalBloom[j] && currBloom <= optimalWilt[j] ||
                    currWilt >= optimalWilt[j] && currBloom <= optimalBloom[j]) {  // life period overlap
                if(currHeight < optimal[j]) {  // life overlap, and type i is shorter than type j
                    offset = j;
                    break;
                } else {
                    offset = j + 1; // type i overlap with type j, and i is taller than j. Put i after j
                }
            } else {  // not overlap with current
                if(currHeight < optimal[j]) {
                    offset = j + 1; // type i not overlap with j, i is shorter than j, put i after j
                }
                // else keep offset as is considering offset is smaller than j
            }
        }

        // shift the types after offset
        for(int k = i - 1; k >= offset; k -- ) {
            optimal[k+1] = optimal[k];
            optimalBloom[k+1] = optimalBloom[k];
            optimalWilt[k+1] = optimalWilt[k];
        }
        // update optimal
        optimal[offset] = currHeight;
        optimalBloom[offset] = currBloom;
        optimalWilt[offset] = currWilt;
    }
    return optimal;
}

これは私のテスト済みの作業コードです。

Answer 2

トポロジカルソートアプローチ:

#include<stdio.h>
#include<stdlib.h>
#include <vector>  
#include <queue>  

using namespace std;

#define MAX_FLOWERS 50

struct flower
{
   int id;
   int height;
   int bloom;
   int wilt;
   bool visited;
   int ind;
};

struct flower_comp
{
  bool operator()(const struct flower* lhs, const struct flower* rhs) const
  {
    return rhs->height > lhs->height;
  }   
};

inline bool overlap(const struct flower& a, const struct flower& b)
{
    return !((a.bloom < b.bloom && a.wilt < b.bloom) || (a.bloom > b.bloom && a.bloom > b.wilt));
}

void getOrdering(int height[], int bloom[], int wilt[], int size)
{
    struct flower flowers[MAX_FLOWERS];

    for(int i = 0; i < size; i++)
    {
        flowers[i].id = i;
        flowers[i].height = height[i];
        flowers[i].bloom = bloom[i];
        flowers[i].wilt = wilt[i];
        flowers[i].visited = false;
        flowers[i].ind = 0;
    } 

    bool partial_order[MAX_FLOWERS][MAX_FLOWERS] = {false};

    for(int i = 0; i < size; i++)
    {
        for(int j = i + 1; j < size; j++)
        {
            if(overlap(flowers[i], flowers[j]))
            { 
               if(flowers[i].height < flowers[j].height)
               {
                  partial_order[i][j] = true;
                  flowers[j].ind++; 
               }
               else
               {
                  partial_order[j][i] = true;
                  flowers[i].ind++; 
               }
            }
        }
    }

    priority_queue<struct flower*, vector<struct flower*>, flower_comp> pq;

    for(int i = 0; i < size; i++)
    {
        if(flowers[i].ind == 0)
        {
           pq.push(&flowers[i]);
        }
    }

    printf("{");
    bool first = true;
    while(!pq.empty())
    {
        struct flower* tmp = pq.top();
        pq.pop(); 
        tmp->visited = true;
        if(!first)
        {
           printf(",");
        }
        first = false;
        printf("%d", tmp->height);
        for(int j = 0; j < size; j++)
        {
            if(!flowers[j].visited && partial_order[tmp->id][j])
            {
               flowers[j].ind--;
               if(flowers[j].ind == 0)
               {
                  pq.push(&flowers[j]);
               }
            }
        }
    }
    printf("}\n");
}

int main(int argc, char** argv)
{
    int height[] = {5,4,3,2,1};
    int bloom[] = {1,1,1,1,1};
    int wilt[] = {365,365,365,365,365};

    getOrdering(height, bloom, wilt, sizeof(height)/sizeof(height[0]));

    int height0[] = {5,4,3,2,1};
    int bloom0[] = {1,5,10,15,20};
    int wilt0[] = {4,9,14,19,24};

    getOrdering(height0, bloom0, wilt0, sizeof(height0)/sizeof(height0[0]));

    int height1[] = {5,4,3,2,1};
    int bloom1[] = {1,5,10,15,20};
    int wilt1[] = {5,10,15,20,25};

    getOrdering(height1, bloom1, wilt1, sizeof(height1)/sizeof(height1[0]));

    int height2[] = {5,4,3,2,1};
    int bloom2[] = {1,5,10,15,20};
    int wilt2[] = {5,10,14,20,25};

    getOrdering(height2, bloom2, wilt2, sizeof(height2)/sizeof(height2[0]));

    int height3[] = {1,2,3,4,5,6};
    int bloom3[] = {1,3,1,3,1,3};
    int wilt3[] = {2,4,2,4,2,4};

    getOrdering(height3, bloom3, wilt3, sizeof(height3)/sizeof(height3[0]));

    int height4[] = {3,2,5,4};
    int bloom4[] = {1,2,11,10};
    int wilt4[] = {4,3,12,13};

    getOrdering(height4, bloom4, wilt4, sizeof(height4)/sizeof(height4[0]));

}

Answer 3

私もこの問題を解決しようとしました。私のアプローチの主なアイデアは、各子がその親によって少なくとも 1 回オーバーラップするツリーを構築することです。

たとえば、高さが 4、2、1 の 3 種類の花が同じ日に成長し、枯れる場合、結果のツリーは次のようになります。

一方、4 と 2 と 4 と 1 が同時に存在するが、2 と 1 が共存しない場合、結果のツリーは次のようになります。

これにより、問題の制約と一致するツリーが生成されます。それにもかかわらず、問題ステートメントには、いくつかのソリューションを他のソリューションよりも優れたものにするコスト関数も含まれています。

...また、前の方にある列の花をできるだけ高くしたいと考えています。

このプリファレンスをツリーに射影する方法は、すべての「兄弟」(同じ親を共有するすべてのノード) を上位から下位に並べることです。したがって、2 が 1 より先に来ます。

次のコードを使用してこのツリーを構築しました。

#define INT_MOD(a,b) ((a<0)?(b+(a%b)):(a%b))
#define DIST(a,b) ((a-b>=0)?(a-b):(b-a))

//Prev: ForAll(i), bloom[i] < wilt[i]
inline bool isOverlap(vector<int> & bloom,
                      vector<int> & wilt,
                      vector<int> & height,
                      unsigned int idxPrev, unsigned int idxFollowing)
{
    int f1A = bloom[idxPrev];
    int f1B = wilt[idxPrev];
    int f2A = bloom[idxFollowing];
    int f2B = wilt[idxFollowing];

    bool notIntersecting = 
    f2A > f1B /* --[--]-(--)-- */ ||
    f1A > f2B /* --(--)-[--]-- */ ;

    return height[idxPrev] > height[idxFollowing] && !notIntersecting;
}


class CPreference {
public:
    static vector<int> * pHeight;
    static bool preference(int a, int b)
    {
        return (*pHeight)[a] > (*pHeight)[b];
    }
};
vector<int> * CPreference::pHeight = NULL;

vector<int> getOrdering(vector<int> height,
                        vector<int> bloom,
                        vector<int>  wilt)
{
    int l = height.size();
    vector<int> state = vector<int>(l, -1); /*  Tree where each leave points to its
                                                parent. Being that parent the first
                                                flower type that is forced to be
                                                after (backwards) its children */

    //This loop is the dynamic programming core.
    for(int i = 0; i < l; i++)
        for(int j = INT_MOD((i-1),l); j != i; j = INT_MOD((j-1),l))
        {
            if(isOverlap(bloom, wilt, height, i, j) &&
                (state[j] < 0 || DIST(height[j],height[i]) < DIST(height[j], height[state[j]])))
            {
                state[j] = i;
            }
        }

    vector<vector<int> > groups; //Groups of indexes overlapped by the element at the same index
    for(int i = 0; i < l+1; i++)
        groups.push_back(vector<int>()); // (l+1) for no overlapped indexes group.

    for(int i = 0; i < l; i++)
    {
        int k = state[i];
  if(k < 0) k = l;
  groups[k].push_back(i);
}

CPreference::pHeight = &height;
for(vector<vector<int> >::iterator it = groups.begin(); it != groups.end(); it++)
    sort(it->begin(),it->end(), CPreference::preference);

この時点で、グループの各行 (i) には、インデックスiの花の種類の前に配置する必要があるすべての花の種類のインデックスが含まれています。

グループを出力ベクトルにフラット化するために、最後のステップが 1 つ必要です。つまり、各要素の後に次のいずれかが続くベクトルを構築するには:

• ツリー上のその親。
• 身長で並べると隣の弟。

これは、 groupの各ノードの深さの訪問によって行うことができます。それが私のソリューションの弱点だと思います。あまり時間がなかったので、単純な再帰的な実装を作成しました。

//PRE: each vector, v, in 'groups' is sorted using CPreference
void flattenTree(vector<vector<int> > & groups, vector<int> & out, int currentIdx /*parent*/, int l)
{
    int pIdx = currentIdx;
    if(pIdx < 0) pIdx = l;

    vector<int> & elements = groups[pIdx];
    vector<int> ret;

    for(vector<int>::iterator it = elements.begin(); it != elements.end(); it++)
    {
        flattenTree(groups, out ,*it, l);
    }

    if(currentIdx>=0)
        out.push_back(currentIdx);
}

getOrdering 関数を完了するために使用されます。

vector<int> getOrdering(vector<int> height,
            vector<int> bloom,
            vector<int>  wilt)
{
  int l = height.size();
  vector<int> state = vector<int>(l, -1); /* Tree where each leave points to its
                         parent. Being that parent the first
                         flower type that is forced to be
                         after (backwards) its children */
  for(int i = 0; i < l; i++)
    for(int j = INT_MOD((i-1),l); j != i; j = INT_MOD((j-1),l))
      {
        if(isOverlap(bloom, wilt, height, i, j) &&
        (state[j] < 0 || DIST(height[j],height[i]) < DIST(height[j], height[state[j]])))
        {
            state[j] = i;
        }
      }

  vector<vector<int> > groups; //Groups of indexes overlapped by the element at the same index
  for(int i = 0; i < l+1; i++)
    groups.push_back(vector<int>()); // (l+1) for no overlapped indexes group.

  for(int i = 0; i < l; i++)
    {
      int k = state[i];
      if(k < 0) k = l;
      groups[k].push_back(i);
    }

  CPreference::pHeight = &height;
  for(vector<vector<int> >::iterator it = groups.begin();
      it != groups.end(); it++)
    sort(it->begin(),it->end(), CPreference::preference);

   vector<int> ret;
   flattenTree(groups, ret, -1, l);
   for(unsigned int i = 0; i < ret.size(); i++)
    ret[i] = height[ret[i]];
    return ret; 
}

より良い解決策を見つけた場合、または私のものを改善する方法を知っている場合はお知らせください。

Answer 4

ロブと同様に、再び Python で、わずかに複雑なオーバーラップ ブルーム/ウィルト チェックを行います。

H = 0
B = 1
W = 2

def getOrdering(heights, blooms, wilts):

    def _f1_after_f2(f1, f2):
        fs1 = set(range(f1[B], f1[W]+1))
        fs2 = set(range(f2[B], f2[W]+1))
        return f1[H] > f2[H] if fs2.intersection(fs1) != set([]) else False

    fs = zip(heights, blooms, wilts)
    fs.sort()
    ffs = []
    for f1 in fs:
        insert_at = len(ffs)
        for f2 in reversed(ffs):
            if _f1_after_f2(f1, f2): break
            insert_at -= 1
        ffs.insert(insert_at, f1)
    return [f[H] for f in ffs]

Answer 5

問題を解決するグラフ アルゴリズム:

有向グラフ (V,E) を作成します: V -> 花の種類 E -> 2 つの花の種類間の関係

For all pairs (v_i, v_j)
  If v_i is smaller than v_j and v_j 'blocks' v_i
    draw an edge starting from v_i to v_j
For all nodes v_i
  Find the v_i with no incoming edges and the biggest height
   -> write it at the end of the result list
   -> remove v_i and all of its outgoing edges from graph

詳細については、このフォーラムをチェックアウトしてください: Topcoder Forum - FlowerGarden