codeforces-scrape

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

1816B.md (2165B)


      1 Source: https://codeforces.com/problemset/problem/1816/B
      2 
      3 B. Grid Reconstruction
      4 
      5 time limit per test
      6 
      7 1 second
      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 Consider a $2 \times n$ grid, where $n$ is an even integer. You may place the integers $1, 2, \ldots, 2n$ on the grid, using each integer exactly once.
     22 
     23 A path is a sequence of cells achieved by starting at $(1, 1)$, then repeatedly walking either downwards or to the right, and stopping when $(2, n)$ is reached. The path should not extend beyond the grid.
     24 
     25 The cost of a path is the alternating sum of the numbers written on the cells in a path. That is, let the numbers written on the cells be $a_1, a_2, \ldots, a_k$ (in the order that it is visited), the cost of the path is $a_1 - a_2 + a_3 - a_4 + \ldots = \sum_{i=1}^k a_i \cdot (-1)^{i+1}$.
     26 
     27 Construct a way to place the integers $1, 2, \ldots, 2n$ on the grid, such that the minimum cost over all paths from $(1, 1)$ to $(2, n)$ is maximized. If there are multiple such grids that result in the maximum value, output any of them.
     28 
     29 Input
     30 
     31 The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. The description of test cases follows.
     32 
     33 The first and the only line of each test case contains a single integer $n$ ($2 \leq n \leq 10^5$, $n$ is even) — the number of the columns in the grid.
     34 
     35 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     36 
     37 Output
     38 
     39 For each test case, output $2$ lines, each containing $n$ integers — the desired grid. If there are multiple solutions, output any of them.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 3
     47 
     48 2
     49 
     50 4
     51 
     52 6
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 3 2
     59 1 4
     60 8 2 6 4
     61 1 5 3 7
     62 11 5 9 1 7 3
     63 6 10 2 8 4 12
     64 ```
     65 
     66 Note
     67 
     68 In the first test case, there are only two paths from cell $(1, 1)$ to cell $(2, 2)$. Their costs are $3-1+4=6$ and $3-2+4=5$. Then the minimum cost is $5$, which is the maximum possible value.
     69 
     70 In the second test case, there are four paths from cell $(1, 1)$ to cell $(2, 4)$. Their costs are $8-1+5-3+7=16$, $8-2+5-3+7=15$, $8-2+6-3+7=16$, and $8-2+6-4+7=15$. Then the minimum value is $15$, which is the maximum possible value.