Submission #930987

#	Time	Username	Problem	Language	Result	Execution time	Memory
930987		Lib	Aliens (IOI16_aliens)	C++14	Compilation error	0 ms	0 KiB

aliens

#include <bits/stdc++.h>
//Aliens - Knuth opt variant
using namespace std;
long long DP[6000][6000]; //dp[i][k]: Minimum cost for covering the first i segments with EXACTLY k pictures (obviously i>=k)
long long OptLastCut[6000][6000];
//Why tf are there segments here? Refer to the official editorial for that - the expaination seems good enough
const long long INF=2000000000000000000;
struct seg{
  long long Start;
  long long End;
};
seg Segments[6003];
vector <seg> ActualSegments;
//Custom sort function for removing uneeded segments. If a segment which starts at L and end at R is kept, alongside with another segment which starts at L' and end as R', and L'<= L <= R <= R' (aka: The segment is completely covered), the DP will become absolute shitfuckery and extremely wrong (trust me, I thought it would work but it didn't)
bool operator< (const seg &x, const seg &y){
  if(x.Start==y.Start){
    return x.End>y.End;
  }else{
    return x.Start<y.Start;
  }
}
 
long long take_photos(int N,int M, int Pics, vector <int> Rows, vector <int> Columns){
  for(int i=1;i<=N;i++){
    Segments[i]={min(Rows[i-1],Columns[i-1])+1,max(Rows[i-1],Columns[i-1])+1};
  }
  sort(Segments+1,Segments+N+1);
  ActualSegments.push_back({0,0});
  N=ActualSegments.size();
  Pics=min(Pics,N);
  //Removing the fully-covered segments: It is easy to see that our resulting set of segments will have the later segments have both higher start and endpoints when compared to all previous ones, so...... Again, if you can't understand this, you shouldn't try learning about fucking ALIENS' TRICK just yet.
  for(int i=1;i<=N;i++){
    if(Segments[i].End>ActualSegments.back().End){
      ActualSegments.push_back(Segments[i]);
    }
  }
  //Now, the DP.
  /*
  The standard O(N^3*K) algorithm for standard range DP is, well, standard. Nothing to talk about. Knuth's Optimization comes from the following observation
  (which could be proven, but proving that is both relatively complicated and not crucial to understanding the idea, plus you can "feel" why it is correct anyways):
  - What we're essentially doing with the DP transitions here, is: We try to find the optimal cost for covering the first i segments with k pictures,
  by trying all the ways the k-th pictures could be taken. More formally, we can get the optimal cost for covering the first i segments with k pictures,
  with the k-th picture covering segments j+1 to i (obviously j<k), by combining the optimal cost for covering the first j segments with k-1 pictures and
  the cost of the k-th picture. The DP formula is:
  DP[i][k]=min(DP[i][k],DP[j][k-1]+(Cost to take k-th picture)-(The overlapping section))
  Now, we consider the optimal j for several cases. Let OptLastCut[i][k] be the corresponding position j, where the j+1-th segment
  is the leftmost segment fully covered by the final picture we take. We can "guess" the following things:
  - OptLastCut[i][k] >= OptLastCut[i][k-1]: Just imagine that: When we try to cover the same amount of segments with more pictures, the position
  of the last "cut" point should move closer to the end, or something.
  - OptLastCut[i+1][k] >= OptLastCut[i][k]: Again, when there are more segments that must be covered with the same amount of pictures, the position of
  the optimal last cut should ideally move closer to the end
  Combining the 2 above "provable but guesswork is best" "observations", we have the following inequation:
  
  OptLastCut[i+1][k] >= OptLastCut[i][k] >= OptLastCut[i][k-1]. In other words, the possible range for OptLastCut[i][k] is bounded, and the runtime is reduced.
  The exact degree of optimization: From O(N^3*K) to O(N^2*K) (cp.algo prove this thing quite well so I don't think that it's actually needed, if anything
  Knuth Opt is probably the most intuitive optimization out of the 4 that will be used for this..thing)
  To find a valid DP order, notice that: While iterating by order of i or k will cause absolute shitfuckery to happen, calculating the DP by order of 
  decreasing i-k works (as both (i+1)-k and i-(k-1) equalls to i-k+1, and i-k equals to...yeah
  */
  long long ThisSplit;
  long long ThisPic;
  long long Overlap;
  for(int i=0;i<=N;i++){
  	DP[i][0]=0;
  	for(int k=1;k<=Pics;k++){
  		DP[i][k]=INF;
  		OptLastCut[i][k]=0;
  		if(k==1){
  			DP[i
		  }
	  }
  }
  for(int Diff=N;Diff>=0;Diff--){
  	for(int k=2;k<=Pics&&k+Diff<=N;k++){
  		for(int opt=OptLastCut[k-1+Diff][k-1];opt<=OptLastCut[k+Diff][k];opt++){
  			return opt;
  			ThisPic=ActualSegments[Diff+k].End-ActualSegments[opt+1].Start;
  			Overlap=min(0ll,ActualSegments[opt+1].Start-ActualSegments[opt].End);
  			ThisSplit=DP[opt][k-1]+ThisPic*ThisPic-Overlap*Overlap;
  			if(DP[Diff+k][k]<=ThisSplit){
  				OptLastCut[Diff+k][k]=opt;
  				DP[Diff+k][k]=ThisSplit;
			  }
		  }
	  }
  }
  long long Ans=INF;
  for(int i=1;i<=Pics;i++){
  	Ans=min(Ans,DP[N][i]);
  }
  return Ans;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:69:10: error: expected ']' before '}' token
   69 |      DP[i
      |          ^
      |          ]
   70 |     }
      |     ~     
aliens.cpp:69:10: error: expected ';' before '}' token
   69 |      DP[i
      |          ^
      |          ;
   70 |     }
      |     ~     
aliens.cpp:70:5: warning: statement has no effect [-Wunused-value]
   69 |      DP[i
      |      ~~~~
   70 |     }
      |     ^