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

Revision en2, by Aveiro_quanyue, 2023-03-14 14:01:43

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

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)