codeforces-scrape

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

472C.md (2591B)


      1 Source: https://codeforces.com/problemset/problem/472/C
      2 
      3 C. Design Tutorial: Make It Nondeterministic
      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 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 A way to make a new task is to make it nondeterministic or probabilistic. For example, the hard task of Topcoder SRM 595, Constellation, is the probabilistic version of a convex hull.
     22 
     23 Let's try to make a new task. Firstly we will use the following task. There are *n* people, sort them by their name. It is just an ordinary sorting problem, but we can make it more interesting by adding nondeterministic element. There are *n* people, each person will use either his/her first name or last name as a handle. Can the lexicographical order of the handles be exactly equal to the given permutation *p*?
     24 
     25 More formally, if we denote the handle of the *i*-th person as *h**i*, then the following condition must hold: ![](https://espresso.codeforces.com/7da83a168f60958e75fb0519eaef2bfeb7b2a382.png).
     26 
     27 Input
     28 
     29 The first line contains an integer *n* (1 ≤ *n* ≤ 105) — the number of people.
     30 
     31 The next *n* lines each contains two strings. The *i*-th line contains strings *f**i* and *s**i* (1 ≤ |*f**i*|, |*s**i*| ≤ 50) — the first name and last name of the *i*-th person. Each string consists only of lowercase English letters. All of the given 2*n* strings will be distinct.
     32 
     33 The next line contains *n* distinct integers: *p*1, *p*2, ..., *p**n* (1 ≤ *p**i* ≤ *n*).
     34 
     35 Output
     36 
     37 If it is possible, output "YES", otherwise output "NO".
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 3  
     45 gennady korotkevich  
     46 petr mitrichev  
     47 gaoyuan chen  
     48 1 2 3
     49 ```
     50 
     51 Output
     52 
     53 ```
     54 NO
     55 ```
     56 
     57 Input
     58 
     59 ```
     60 3  
     61 gennady korotkevich  
     62 petr mitrichev  
     63 gaoyuan chen  
     64 3 1 2
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 YES
     71 ```
     72 
     73 Input
     74 
     75 ```
     76 2  
     77 galileo galilei  
     78 nicolaus copernicus  
     79 2 1
     80 ```
     81 
     82 Output
     83 
     84 ```
     85 YES
     86 ```
     87 
     88 Input
     89 
     90 ```
     91 10  
     92 rean schwarzer  
     93 fei claussell  
     94 alisa reinford  
     95 eliot craig  
     96 laura arseid  
     97 jusis albarea  
     98 machias regnitz  
     99 sara valestin  
    100 emma millstein  
    101 gaius worzel  
    102 1 2 3 4 5 6 7 8 9 10
    103 ```
    104 
    105 Output
    106 
    107 ```
    108 NO
    109 ```
    110 
    111 Input
    112 
    113 ```
    114 10  
    115 rean schwarzer  
    116 fei claussell  
    117 alisa reinford  
    118 eliot craig  
    119 laura arseid  
    120 jusis albarea  
    121 machias regnitz  
    122 sara valestin  
    123 emma millstein  
    124 gaius worzel  
    125 2 4 9 6 5 7 1 3 8 10
    126 ```
    127 
    128 Output
    129 
    130 ```
    131 YES
    132 ```
    133 
    134 Note
    135 
    136 In example 1 and 2, we have 3 people: tourist, Petr and me (cgy4ever). You can see that whatever handle is chosen, I must be the first, then tourist and Petr must be the last.
    137 
    138 In example 3, if Copernicus uses "copernicus" as his handle, everything will be alright.