codeforces-scrape

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

2002B.md (2032B)


      1 Source: https://codeforces.com/problemset/problem/2002/B
      2 
      3 B. Removals Game
      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 Alice got a permutation $a_1, a_2, \ldots, a_n$ of $[1,2,\ldots,n]$, and Bob got another permutation $b_1, b_2, \ldots, b_n$ of $[1,2,\ldots,n]$. They are going to play a game with these arrays.
     22 
     23 In each turn, the following events happen in order:
     24 
     25 * Alice chooses either the first or the last element of her array and removes it from the array;
     26 * Bob chooses either the first or the last element of his array and removes it from the array.
     27 
     28 The game continues for $n-1$ turns, after which both arrays will have exactly one remaining element: $x$ in the array $a$ and $y$ in the array $b$.
     29 
     30 If $x=y$, Bob wins; otherwise, Alice wins. Find which player will win if both players play optimally.
     31 
     32 Input
     33 
     34 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le10^4$). The description of the test cases follows.
     35 
     36 The first line of each test case contains a single integer $n$ ($1\le n\le 3\cdot 10^5$).
     37 
     38 The next line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\le a_i\le n$, all $a_i$ are distinct) — the permutation of Alice.
     39 
     40 The next line contains $n$ integers $b_1,b_2,\ldots,b_n$ ($1\le b_i\le n$, all $b_i$ are distinct) — the permutation of Bob.
     41 
     42 It is guaranteed that the sum of all $n$ does not exceed $3\cdot 10^5$.
     43 
     44 Output
     45 
     46 For each test case, print a single line with the name of the winner, assuming both players play optimally. If Alice wins, print $\texttt{Alice}$; otherwise, print $\texttt{Bob}$.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 2
     54 
     55 2
     56 
     57 1 2
     58 
     59 1 2
     60 
     61 3
     62 
     63 1 2 3
     64 
     65 2 3 1
     66 ```
     67 
     68 Output
     69 
     70 ```
     71 Bob
     72 Alice
     73 ```
     74 
     75 Note
     76 
     77 In the first test case, Bob can win the game by deleting the same element as Alice did.
     78 
     79 In the second test case, Alice can delete $3$ in the first turn, and then in the second turn, delete the element that is different from the one Bob deleted in the first turn to win the game.