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

Правка en5, от 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$$$.

Теги implementations, #hamiltonian-circuit

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en18 Английский Aveiro_quanyue 2023-03-14 15:37:27 3 Tiny change: 'ius round is rather di' -> 'ius round rather di'
en17 Английский Aveiro_quanyue 2023-03-14 15:02:30 5 Tiny change: 'ilton circle $1-2-3-1$' -> 'ilton circuit $1-2-3-1$'
en16 Английский Aveiro_quanyue 2023-03-14 14:57:31 29
en15 Английский Aveiro_quanyue 2023-03-14 14:51:42 112
en14 Английский Aveiro_quanyue 2023-03-14 14:46:27 1 Tiny change: 'l detail 7** I find ' -> 'l detail 7:** I find '
en13 Английский Aveiro_quanyue 2023-03-14 14:35:03 95
en12 Английский Aveiro_quanyue 2023-03-14 14:34:24 7
en11 Английский Aveiro_quanyue 2023-03-14 14:30:57 1 Tiny change: 'hinder your from solv' -> 'hinder you from solv'
en10 Английский Aveiro_quanyue 2023-03-14 14:30:20 51
en9 Английский Aveiro_quanyue 2023-03-14 14:29:43 12 Tiny change: 'n't think it requires ' -> 'n't think this problem requires '
en8 Английский Aveiro_quanyue 2023-03-14 14:29:20 0 (published)
en7 Английский Aveiro_quanyue 2023-03-14 14:29:02 372
en6 Английский Aveiro_quanyue 2023-03-14 14:25:56 568
en5 Английский Aveiro_quanyue 2023-03-14 14:21:34 581
en4 Английский Aveiro_quanyue 2023-03-14 14:16:35 2038
en3 Английский Aveiro_quanyue 2023-03-14 14:04:32 1099
en2 Английский Aveiro_quanyue 2023-03-14 14:01:43 1205
en1 Английский Aveiro_quanyue 2023-03-14 13:50:31 374 Initial revision (saved to drafts)