codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2275E.md (2763B)


      1 Source: https://codeforces.com/problemset/problem/2275/E
      2 
      3 E. Repentance Is Already on the Way
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Because of K1o0n's friend Gorilla's rampage, the two main parallel roads were blocked in city $\mathbb{X}$. Now the residents have to use the old roads connecting the city's buildings.
     22 
     23 Along each main road there are $n$ buildings. The buildings on the first road belong to companies $a_1, a_2, \ldots, a_n$. The buildings on the second road belong to companies $b_1, b_2, \ldots, b_n$. One company may own several buildings.
     24 
     25 The old roads are arranged as follows:
     26 
     27 * buildings $a_i$ and $b_i$ are connected by a road;
     28 * buildings $a_i$ and $b_{i+1}$ ($i + 1 \le n$) are connected by a road;
     29 * buildings $a_i$ and $b_{i-1}$ ($2 \le i$) are connected by a road.
     30 
     31 All old roads are bidirectional. There are no other available roads in the city.
     32 
     33 A road between buildings of the same company has length $2$ kilometers. A road between buildings of different companies has length $1$ kilometer.
     34 
     35 K1o0n decided to personally drive around the city and assess the consequences of his friend's mischief. He starts at building $a_1$ and wants to visit each of the $2n$ buildings exactly once. He may finish the trip at any building.
     36 
     37 To make Gorilla think carefully about his behavior, K1o0n took him along and decided to choose the longest route. Find the maximum possible length of their route.
     38 
     39 Input
     40 
     41 The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of testcases.
     42 
     43 The first line of each testcase contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of buildings on each main road.
     44 
     45 The second line of each testcase contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the buildings on the first main road.
     46 
     47 The third line of each testcase contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 10^9$) — the buildings on the second main road.
     48 
     49 It is guaranteed that the sum of $n$ over all testcases does not exceed $2 \cdot 10^5$.
     50 
     51 Output
     52 
     53 For each testcase, output one integer — the longest route that K1o0n can take Gorilla on.
     54 
     55 Example
     56 
     57 Input
     58 
     59 ```
     60 5
     61 
     62 1
     63 
     64 5
     65 
     66 5
     67 
     68 4
     69 
     70 1 2 3 4
     71 
     72 1 9 2 3
     73 
     74 5
     75 
     76 7 7 7 7 7
     77 
     78 7 7 7 7 7
     79 
     80 5
     81 
     82 1 3 2 4 5
     83 
     84 2 3 5 2 4
     85 
     86 2
     87 
     88 1 2
     89 
     90 1 2
     91 ```
     92 
     93 Output
     94 
     95 ```
     96 2
     97 
     98 10
     99 
    100 18
    101 
    102 12
    103 
    104 5
    105 ```
    106 
    107 Note
    108 
    109 In the second testcase, one can construct the route shown in the picture. Its length is $10$ kilometers. It can be shown that a longer route is impossible.
    110 
    111  ![](https://espresso.codeforces.com/0ff8231560accf399fcbbfd06d9231f5d3375fe7.png) Second testcase. 
    112 
    113 In the third testcase, no matter which route you choose, Gorilla will suffer with K1o0n for the entire $18$ kilometers of the road.