Timus - 1018 - Binary Apple Tree - Dynamic Programming

21 April 2013   832 words   ~4 mins
#Dynamic Programming #Sport Programming #Timus

Table of Contents

Today, I saw this interesting problem.
\\ Timus - 1018 - Binary Apple Tree
\\ When I started working on this, I didnt know why do we need Dynamic Programming to solve this. My idea was pretty simple.

  1. While reading Inputs find the total number of apples\\
  2. Find all the leaf Branches (I mean branches without any branches on them)\\
  3. Get the branch with the least number of apples and remove that\\
  4. Goto Step 2 until N - Q - 1 times. (N is the total number of enumerated points on the tree, Q is the number of branches to keep, Always there will be N - 1 branches on the binary tree. So N - Q - 1 will give the number of branches to be removed)

It was pretty straight forward to implement.\\

 1# include <cstdio>
 2# include <map>
 3# include <set>
 4# include <bitset>
 5using namespace std;
 6int N, Q;
 7unsigned long long Total = 0;
 8struct Branch
 9{
10 bool operator< (const Branch & branch) const
11 {
12  if (this->Apples == branch.Apples)
13  {
14   if (this->Start == branch.Start)
15    return this->End < branch.End;
16   return this->Start< branch.Start;
17  }
18  return this->Apples < branch.Apples;
19 }
20 Branch (int a, int b, int c){Start = a; End = b; Apples = c;}
21 int Start, End, Apples;
22};
23set <Branch> Edges;
24bitset <101> Visited;
25map <int, map <int, int> > Tree;
26void FindEdges (int current, int parent)
27{
28 //printf ("%d\t%d\n", current, parent);
29 if (Visited[current]) return;
30 //printf ("%d\t%d Not Visited\n", current, parent);
31 Visited[current] = true;
32 map<int, int>::iterator it = Tree[current].begin();
33 if (Tree[current].size() == 1)
34  Edges.insert (Branch (parent, current, Tree[parent][current]));
35 else
36  for (; it != Tree[current].end(); it++)
37   if (!Visited[it->first])
38    FindEdges (it->first, current);
39}
40int main()
41{
42 //freopen ("Input.txt", "r", stdin);
43 //freopen ("Scratch.txt", "w", stdout);
44 scanf ("%d%d", &N, &Q);
45 Q = N - 1 - Q;
46 int A, B, C;
47 for (int i = 0; i < N - 1; i++)
48 {
49  scanf ("%d%d%d", &A, &B, &C);
50  Tree[A][B] = C;
51  Tree[B][A] = C;
52  Total += C;
53 }
54 for (int i = 0; i < Q; i++)
55 {
56  Edges.clear();
57  Visited.reset();
58  map<int, int>::iterator it1 = Tree[1].begin();
59  Visited[1] = true;
60  for (; it1 != Tree[1].end(); it1++)
61   FindEdges(it1->first, 1);
62  //printf ("Edges Size : %lu\n", Edges.size());
63  set<Branch>::iterator it = Edges.begin();
64  //printf ("%d\t%d\t%d\n", it->Start, it->End, it->Apples);
65  Total -= it->Apples;
66  Tree[it->Start].erase (it->End);
67  Tree[it->End].erase (it->Start);
68 }
69 printf ("%llu\n", Total);
70}

However, this solution was failing so many times. Then I found the testcase for which this program was failing.

14 1
21 2 1
31 3 2
42 4 3

The above shown solution returns 1 as the result whereas the optimal result is 2. This approach is greedy approach I believe.
In the first iteration, it detects the branches

11 3 2
22 4 3

and removes the branch 1 3 2, since it has the least number of apples and in the next iteration it detects the following branch

12 4 3

since that is the only leaf branch available and it removes that, leaving us with the suboptimal solution 1.
\\ Here is the DP solution which can really solve this problem and this got accepted by Timus.
\\

 1#include <cstdio>
 2#include <cstring>
 3#include <vector>
 4#include <algorithm>
 5
 6using namespace std;
 7
 8int N,Q, Tree[101][101], DP[101][101];
 9int solve (int current, int parent, int q)
10{
11 if (q <= 0) return 0;
12 int lindex = -1, rindex = -1;
13 int & result = DP[current][q];
14 if (result != -1) return result;
15 for (int i = 0; i < 101; i++)
16  if (Tree[current][i] != -1 && i != parent) {lindex = i; break;}
17 for (int i = (lindex == -1?0:lindex+1); i < 101; i++)
18  if (Tree[current][i] != -1 && i != parent) {rindex = i; break;}
19 //printf ("%d\t%d\t%d\t%d\t%d\n", current, parent, lindex, rindex, q);
20 if (lindex == -1 || rindex == -1) return 0;
21 for (int i = 0; i <= q; i++)
22  result = max (result, (i == q?0:Tree[current][lindex] + solve(lindex, current, q - i - 1))
23   + (i == 0?0:Tree[current][rindex] + solve(rindex, current, i - 1)));
24 //printf ("Returning %d\n", result);
25 return result;
26}
27int main()
28{
29 //freopen ("Input.txt", "r", stdin);
30 //freopen ("Scratch.txt", "w", stdout);
31 scanf("%d%d",&N,&Q);
32 memset (Tree, -1, sizeof Tree);
33 memset (DP, -1, sizeof DP);
34 for (int i = 0; i < N; i++)
35  for (int j = 0, x, y, z; j < N; j++)
36  {
37   scanf ("%d%d%d", &x, &y, &z);
38   Tree [x][y] = z;
39   Tree [y][x] = z;
40  }
41 printf ("%d\n", solve (1, 0, Q));
42 return 0;
43}

Please write to me if you want me to explain this program. We can do that over chat.

← prev next →