Problem E-Routing in the Nebius Round: Devil is in the details

Revision en5, by Aveiro_quanyue, 2023-03-14 14:21:34

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'

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 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$$$.

Tags implementations, #hamiltonian-circuit

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en18 English Aveiro_quanyue 2023-03-14 15:37:27 3 Tiny change: 'ius round is rather di' -> 'ius round rather di'
en17 English Aveiro_quanyue 2023-03-14 15:02:30 5 Tiny change: 'ilton circle $1-2-3-1$' -> 'ilton circuit $1-2-3-1$'
en16 English Aveiro_quanyue 2023-03-14 14:57:31 29
en15 English Aveiro_quanyue 2023-03-14 14:51:42 112
en14 English Aveiro_quanyue 2023-03-14 14:46:27 1 Tiny change: 'l detail 7** I find ' -> 'l detail 7:** I find '
en13 English Aveiro_quanyue 2023-03-14 14:35:03 95
en12 English Aveiro_quanyue 2023-03-14 14:34:24 7
en11 English Aveiro_quanyue 2023-03-14 14:30:57 1 Tiny change: 'hinder your from solv' -> 'hinder you from solv'
en10 English Aveiro_quanyue 2023-03-14 14:30:20 51
en9 English Aveiro_quanyue 2023-03-14 14:29:43 12 Tiny change: 'n't think it requires ' -> 'n't think this problem requires '
en8 English Aveiro_quanyue 2023-03-14 14:29:20 0 (published)
en7 English Aveiro_quanyue 2023-03-14 14:29:02 372
en6 English Aveiro_quanyue 2023-03-14 14:25:56 568
en5 English Aveiro_quanyue 2023-03-14 14:21:34 581
en4 English Aveiro_quanyue 2023-03-14 14:16:35 2038
en3 English Aveiro_quanyue 2023-03-14 14:04:32 1099
en2 English Aveiro_quanyue 2023-03-14 14:01:43 1205
en1 English Aveiro_quanyue 2023-03-14 13:50:31 374 Initial revision (saved to drafts)