According to clist.by, the estimated rating of problem E-Routing is about 2500. I don't think it requires a very clever mind, but it contains a lot of evil details that might hinder your from solving it.
Evil detail 1: You should pay attention to the memory limit. Many people tend to put lots of emphasis on time limit but ignore the memory limit. In this problem, the memory limit is a little bit tight. You will get MLE if you use a large array (e.g., int dp[1<<20][20][20]
). Key idea: use a bitset. For example, std::bitset
or a dynamic bitset. You might use the dynamic bitset in my submission. std::bitset
is static because its size is given by the template parameter during the compiling period. In this problem, both static and dynamic bitsets are OK!
Evil detail 2: You should avoid an $$$O(n^3 2^n)$$$ approach. For example, you might define the dynamic programming (dp) as follows: $$$dp[state][x][y]$$$ denotes a Hamilton path starts from $$$x$$$ and ends with $$$y$$$. Then you enumerate all the neighbors $$$z$$$ of $$$y$$$. Be careful, this is $$$O(n^3 2^n)$$$ because you enumerate duplicated circles. To tackle this problem, we still use this $$$dp$$$ array, but we only consider the $$$y, z$$$ that are larger than $$$x$$$. For example, given a Hamilton circle $$$1-2-3-1$$$, we should enumerate $$$1-2-3-1$$$ only. We should not enumerate $$$2-3-1-2$$$. Each circle is enumerated only once, achieving $$$O(n^2 2^n)$$$ complexity.
Evil detail3: You should be cautious about the sequence of the for
loops. Here is a part of my code:
//CORRECT
for(int j = 0; j < (1 << n); ++j){
for(int start = 0; start < n; ++start){
for(int end = start; end < n; ++end){
if(!dp[start][end][j]) continue;
for(int e2: o[end]){
if(e2 < start) continue; //Only enumerate the smallest start
if(BT(j, e2)) continue; //Already enumerated #define BT(x, i) (((x) & (1 << (i))) >> (i))
int nextj = j|(1<<e2);
dp[start][e2].set1(nextj);
pre[nextj][e2] = end;
if(nb[e2][start]) ok[nextj] = e2;
}
}//end of 'end'
}//end of 'start'
}//end of bitmask 'j'
In the wrong submission, it is:
//WRONG!
for(int start = 0; start < n; ++start){
for(int end = start; end < n; ++end){
for(int j = 0; j < (1 << n); ++j){
...
}//end of bitmask 'j'
}//end of 'end'
}//end of 'start'