codeforces-scrape

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

634A.md (2354B)


      1 Source: https://codeforces.com/problemset/problem/634/A
      2 
      3 A. Island Puzzle
      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 A remote island chain contains *n* islands, labeled 1 through *n*. Bidirectional bridges connect the islands to form a simple cycle — a bridge connects islands 1 and 2, islands 2 and 3, and so on, and additionally a bridge connects islands *n* and 1. The center of each island contains an identical pedestal, and all but one of the islands has a fragile, uniquely colored statue currently held on the pedestal. The remaining island holds only an empty pedestal.
     22 
     23 The islanders want to rearrange the statues in a new order. To do this, they repeat the following process: First, they choose an island directly adjacent to the island containing an empty pedestal. Then, they painstakingly carry the statue on this island across the adjoining bridge and place it on the empty pedestal.
     24 
     25 Determine if it is possible for the islanders to arrange the statues in the desired order.
     26 
     27 Input
     28 
     29 The first line contains a single integer *n* (2 ≤ *n* ≤ 200 000) — the total number of islands.
     30 
     31 The second line contains *n* space-separated integers *a**i* (0 ≤ *a**i* ≤ *n* - 1) — the statue currently placed on the *i*-th island. If *a**i* = 0, then the island has no statue. It is guaranteed that the *a**i* are distinct.
     32 
     33 The third line contains *n* space-separated integers *b**i* (0 ≤ *b**i* ≤ *n* - 1) — the desired statues of the *i*th island. Once again, *b**i* = 0 indicates the island desires no statue. It is guaranteed that the *b**i* are distinct.
     34 
     35 Output
     36 
     37 Print "YES" (without quotes) if the rearrangement can be done in the existing network, and "NO" otherwise.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 3  
     45 1 0 2  
     46 2 0 1
     47 ```
     48 
     49 Output
     50 
     51 ```
     52 YES
     53 ```
     54 
     55 Input
     56 
     57 ```
     58 2  
     59 1 0  
     60 0 1
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 YES
     67 ```
     68 
     69 Input
     70 
     71 ```
     72 4  
     73 1 2 3 0  
     74 0 3 2 1
     75 ```
     76 
     77 Output
     78 
     79 ```
     80 NO
     81 ```
     82 
     83 Note
     84 
     85 In the first sample, the islanders can first move statue 1 from island 1 to island 2, then move statue 2 from island 3 to island 1, and finally move statue 1 from island 2 to island 3.
     86 
     87 In the second sample, the islanders can simply move statue 1 from island 1 to island 2.
     88 
     89 In the third sample, no sequence of movements results in the desired position.