CCC 2014 S5: Lazy Fox

The fox start from (0,0) that is the starting point, it has no treat.

Then the fox can visit from every point of N to every other point of N,

Here is visited rules:

1. it can not visit the same point consecutive, for example, it visits i point, and it can not visit the same point.

From one point i visited go to the next point j, the distance d1 between i and j , then from j point go to another point k, if the distance d2 between j and k is less than d1.

1. The fox can visit any point although it already visited.

The question is what is the maximum visit(sugar eat) .

So we can think about that the fox comes from j , then go to the current i, it eats m sugar arriving j, then arrive i. We can use f(j, i, m) to represent point i that the fox can eat the max sugar.

Assume d1 is the distance between point j and i.

f(j, i, m) = max(f(i, 1, m+1), f(i, 2, m+1), f(i, 3, m+1)...f(i,k,m+1)...f(i, N, m+1))

and k != i

It will visit k point, the d2 is the distance between i point to k point.

Case 1:

If d1 > d2:

Get f(i, k, m+1)

Else:

M+1 (termination condition)

Then we can implement the solution:

Do the recursive solution:

getmaxsugar(int from, int pos, int fromsgar):

Maxsugar = fromsgar + 1

for(i = 1; i < = N; i++)

If d_pos_i < d_from_pos:

If maxsugar < getmaxsugar(int pos, int i, int fromsgar+1):

Update maxsugar

Return maxsugar

We can only get 1 mark if you implement the above.

Then if you use DP, store result[from][i].

You can get 10 marks.

int getmaxdist(int from, int curdeep, int pos){
   curdeep++;
   if(result[from][pos]!= -1){
      return curdeep+result[from][pos];
   }
   int pd = dist[from][pos];
   int maxdeep = curdeep;
   for(int i = 1; i <= n;  i++){
      if(pos != i && pd > dist[pos][i]){
         int cur = getmaxdist(pos, curdeep, i);
         if(cur > maxdeep){
            maxdeep = cur;
         }
      }
   }
   //cout<<from<<" "<<pos<<" todd:"<<maxdeep-curdeep<<endl;
   result[from][pos] = maxdeep-curdeep;
   return maxdeep;

}

Another way you can get 15 marks. We can do DP from up to bottom:

For one point,

1. It can be from a point

2. It can be the current point.

The two points can form a line, it has distance.

The two points of one line can be from the point or the current point.

If we can build a line array, it contains:

Point 1

Point 2

Distance

Then sort the line array, the smallest line always the last points of each other,

Then from here, we can build the DP, until go to the max line.

C++ solution:

int n;

struct point {
  int x;
  int y;
  point(int x, int y) {
    this->x = x;
    this->y = y;
  }
};

struct line {
  Int i1;
  int i2;
  int dist;
  line(int i1, int i2, int dist) {
    this->i1 = i1;
    this->i2 = i2;
    this->dist = dist;
  }
};

vector<point> points;
int bestDist[2001];
int prevbestNum[2001];
int bestNum[2001];
vector<line> lines;

bool compare(line p1, line p2) {
  return p2.dist > p1.dist;
}

int main() {
  scanf("%d", &n);
  points.push_back(point(0, 0));
  int count = 0;
  for (int x = 1; x <= n; x++) {

     int a, b;
     scanf("%d%d", &a, &b);
     points.push_back(point(a, b));

    for (int y = x - 1; y >= 0; y--) {
      int x1 = points[x].x - points[y].x;
      int y1 = points[x].y - points[y].y;
      lines.push_back(line(y, x, x1 * x1 + y1 * y1));
      count++;
    }
  }
  sort(lines.begin(), lines.begin() + count, compare);


  for (int x = 0; x < count; x++) {
    line next = lines[x];
    if (next.dist > bestDist[next.i1]) {
      bestDist[next.i1] = next.dist;
      prevbestNum[next.i1] = bestNum[next.i1];
    }
    if (next.dist > bestDist[next.i2]) {
      bestDist[next.i2] = next.dist;
      prevbestNum[next.i2] = bestNum[next.i2];
    }
    // adding necessary previous row memorization in order to calc curr row
    if (next.i1 == 0) {
      bestNum[next.i1] = max(bestNum[next.i1], prevbestNum[next.i2]);
    } else {
      bestNum[next.i1] = max(bestNum[next.i1], prevbestNum[next.i2] + 1);
      bestNum[next.i2] = max(bestNum[next.i2], prevbestNum[next.i1] + 1);
    }
  }
  printf("%d", bestNum[0] + 1);
  return 0;
}

Python:

( can not pass all TCs)

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y


class Line:
    def __init__(self, p1, p2, d):
        self.i1 = p1
        self.i2 = p2
        self.dis = d


points = [Point(0, 0)]
bestdis = [0]*2001
prebestnum = [0]*2001
bestnum = [0]*2001
lines = []

counter = 0
N = int(input())

for i in range(1, N+1):
    ss = input().split()
    a = int(ss[0])
    b = int(ss[1])
    points.append(Point(a, b))
    for j in range(i-1, -1, -1):
        d1 = points[i].x - points[j].x
        d2 = points[i].y - points[j].y
        d = d1*d1 + d2*d2
        lines.append(Line(j, i, d))
        counter += 1

lines = sorted(lines, key=lambda Line:Line.dis)
for x in range(counter):
    linenext = lines[x]
    if linenext.dis > bestdis[linenext.i1]:
        bestdis[linenext.i1] = linenext.dis
        prebestnum[linenext.i1] = bestnum[linenext.i1]

    if linenext.dis > bestdis[linenext.i2]:
        bestdis[linenext.i2] = linenext.dis
        prebestnum[linenext.i2] = bestnum[linenext.i2]

    # adding necessary previous row memorization in order to calc curr row
    if linenext.i1 == 0:
        bestnum[linenext.i1] = max(bestnum[linenext.i1], prebestnum[linenext.i2])
    else:
        bestnum[linenext.i1] = max(bestnum[linenext.i1], prebestnum[linenext.i2] + 1)
        bestnum[linenext.i2] = max(bestnum[linenext.i2], prebestnum[linenext.i1] + 1)


print(bestnum[0] + 1)