According to clist.by, the estimated rating of problem E-Routing is about 2500. I don't think this problem requires a very clever mind, but it contains a lot of evil details that might hinder you from solving it. You might ask me any questions about this problem.
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'
Why it is wrong? Because when a bitmask is evaluated, it is not guaranteed that all its subsets are properly handled!
Evil detail 4: You should be careful about the difference between the Hamilton path and the Hamilton circuit. For example, in the below code:
//o[end] is an adjacency list. Every element in this list is adjacent to the vertex end
//nb[a][b] is an adjacency table. nb[a][b]==1 iff a and b are adjacent.
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;
if(BT(j, e2)) continue;
int nextj = j|(1<<e2);
dp[start][e2].set1(nextj); //BECAREFUL: if(nb[e2][start]) dp[start][e2].set1(nextj); is WRONG!
pre[nextj][e2] = end;
if(nb[e2][start]) ok[nextj] = e2; //e2 could go back to start, so the vertices in nextj form a Hamilton circuit.
}
}//end of 'end'
}//end of 'start'
}//end of bitmask 'j'
When we execute dp[start][e2].set1(nextj);, should we check whether we can return to start from e2, i.e., there exists an edge connecting start with e2? The answer is NO! Take a simple example: $$$a-b-c-d-a$$$ is a Hamilton circuit, and there isn't an $$$a-c$$$ edge. When we explore $$$c$$$, we should still update the $$$dp[a][c]$$$ item even if there isn't an $$$a-c$$$ edge ($$$a$$$, $$$c$$$ are the start, e2 in the code, respectively). If we don't update the dp table, the algorithm will not explore $$$d$$$!
Evil detail 5: $$$0$$$ or $$$-1$$$, it is a problem. If you are using bitmasks, you might set your arrays $$$0$$$-indexed. So, in these cases, you should be very careful about if(ok), because of some thinking inertias. Sometimes if(ok) should be corrected to if(ok != -1)!
Evil detail 6: You should be careful about the nodes/vertices that are on the Hamilton circuit $$$H$$$. If a vertex $$$v \notin H$$$, we can assign $$$v$$$ to an arbitrary vertex from $$$H$$$. However, if $$$v \in H$$$, we cannot do so. There is an easy counterexample: A Hamilton circuit $$$1-2-3-4-1$$$. If we assign $$$a(1)=2$$$ and $$$a(2)=1$$$, then neither vertex $$$1$$$ nor vertex $$$2$$$ can reach vertex $$$3$$$. They will form a deadlock. So, a construction for $$$v \in H$$$ is $$$a(v) := $$$ the previous vertex of $$$v$$$ on the circuit. For the circuit $$$1-2-3-4-1$$$, we may assign $$$a(1)=4, a(4)=3, a(3)=2, a(2)=1$$$. To achieve this, we need to use another array $$$pre$$$ to record the previous vertex. Its updating is quite similar with the Dijkstra/Floyd algorithm. We might define:
$$$pre[curmask][end]$$$ = the previous vertex of end on the Hamilton circuit curmask.
and do such kinds of update until last==-1:
while(last != -1){ //not fxxking while(last)!
last = pre[curmask][end];
curmask ^= (1 << end); //The current end is last, and the current circuit does not contain end, so we should remove it from the curmask.
end = last;
}
Evil detail 7 I find the problem statements in the Nebius round is rather difficult to read. I mean no offense, it is somehow like taking an IELTS reading test. Maybe my English is too poor. I apologize for it. But we need to improve our reading efficiency in this round
