713 E Sonya Partymaker

Revision en2, by Los_Angelos_Laycurse, 2016-10-05 10:39:31

http://codeforces.net/contest/713/problem/E

if we change the problem description: all guests move one step in any direction , how to solve this problem::

binary_search+iteratrion..

first we can get lp inequations: a[i]+y[i]+1==a[i+1]-x[i+1] for 0<=i<=n-2 a[n-1]+yn-1+1==a[0]-x[0]+m

2*x[i]+y[i]<=T||x[i]+2*y[i]<=T.. for  0<=i<=n-1

we can iteratively to find minimum value of lower_bound of each x variable.. low[i], use dynamic programming low[i+1]=min(a[i+1]-a[i]-1-(T-2*low[i]),a[i+1]-a[i]-1-(T-low[i])/2); low[i+1]=max(low[i+1],0); after we run a circle , we got new low[0], if this value >T return false, if this value doesn't increase return true. else continue to run a circle and update low[0].

we must consider two cases : x[0]+2*y[0]<=T and 2*x[0]+y[0]<=T seprately..

my first code which wa on test case 5 is this idea, which I have misunderstand the problem description...

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Los_Angelos_Laycurse 2016-10-05 10:39:31 5 Tiny change: 'low[i+1]=max(a[i+1]-a[' -> 'low[i+1]=min(a[i+1]-a['
en1 English Los_Angelos_Laycurse 2016-10-05 10:37:52 979 Initial revision (published)