WARush143's blog

POI — Vacation
By WARush143, history, 8 years ago, In English

Hi,

I'm currently solving the problem Vacation ( http://main.edu.pl/en/archive/ontak/2010/wak ). I find these problems where every subarray of length n has to satisfy some property very challenging. I believe its DP, but I would appreciate anyones help on this problem.

Thanks

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

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

Whats the time limit?

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

Linear program(n<=200) : http://ideone.com/dVn1wb
Maximize c^T*x, subject to x>=0 and Ax<=B. Here x = [3*n variables denoting if i is taken or not], 3*n equations for x<=1, and 3*n-n+1 equations for each sub-array of the form of sum(n consecutive x_i)<=k. c[i] = a[i]; Maximum of 600 variables and 1001 equations is solvable pretty fast.

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

    I wonder what's wrong with this solution(why are people downvoting?). It gives AC on POI judge.

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

You can fix numbers of days taken in first third and second third. Then do dp through each of three thirds, in parallel, remembering how many days you took in each third so far. Because of fixed numbers you can take care of constraints as you do dp. Complexity is O(nk5) .

There is also more general solution using mincost maxflow. It's similar to http://www.spoj.com/problems/VOL/ and problem D from NEERC16.

→ Reply