codeforces-scrape

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

774D.md (2809B)


      1 Source: https://codeforces.com/problemset/problem/774/D
      2 
      3 D. Lie or Truth
      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 Vasya has a sequence of cubes and exactly one integer is written on each cube. Vasya exhibited all his cubes in a row. So the sequence of numbers written on the cubes in the order from the left to the right equals to *a*1, *a*2, ..., *a**n*.
     22 
     23 While Vasya was walking, his little brother Stepan played with Vasya's cubes and changed their order, so now the sequence of numbers written on the cubes became equal to *b*1, *b*2, ..., *b**n*.
     24 
     25 Stepan said that he swapped only cubes which where on the positions between *l* and *r*, inclusive, and did not remove or add any other cubes (i. e. he said that he reordered cubes between positions *l* and *r*, inclusive, in some way).
     26 
     27 Your task is to determine if it is possible that Stepan said the truth, or it is guaranteed that Stepan deceived his brother.
     28 
     29 Input
     30 
     31 The first line contains three integers *n*, *l*, *r* (1 ≤ *n* ≤ 105, 1 ≤ *l* ≤ *r* ≤ *n*) — the number of Vasya's cubes and the positions told by Stepan.
     32 
     33 The second line contains the sequence *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ *n*) — the sequence of integers written on cubes in the Vasya's order.
     34 
     35 The third line contains the sequence *b*1, *b*2, ..., *b**n* (1 ≤ *b**i* ≤ *n*) — the sequence of integers written on cubes after Stepan rearranged their order.
     36 
     37 It is guaranteed that Stepan did not remove or add other cubes, he only rearranged Vasya's cubes.
     38 
     39 Output
     40 
     41 Print "LIE" (without quotes) if it is guaranteed that Stepan deceived his brother. In the other case, print "TRUTH" (without quotes).
     42 
     43 Examples
     44 
     45 Input
     46 
     47 ```
     48 5 2 4  
     49 3 4 2 3 1  
     50 3 2 3 4 1
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 TRUTH
     57 ```
     58 
     59 Input
     60 
     61 ```
     62 3 1 2  
     63 1 2 3  
     64 3 1 2
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 LIE
     71 ```
     72 
     73 Input
     74 
     75 ```
     76 4 2 4  
     77 1 1 1 1  
     78 1 1 1 1
     79 ```
     80 
     81 Output
     82 
     83 ```
     84 TRUTH
     85 ```
     86 
     87 Note
     88 
     89 In the first example there is a situation when Stepan said the truth. Initially the sequence of integers on the cubes was equal to [3, 4, 2, 3, 1]. Stepan could at first swap cubes on positions 2 and 3 (after that the sequence of integers on cubes became equal to [3, 2, 4, 3, 1]), and then swap cubes in positions 3 and 4 (after that the sequence of integers on cubes became equal to [3, 2, 3, 4, 1]).
     90 
     91 In the second example it is not possible that Stepan said truth because he said that he swapped cubes only between positions 1 and 2, but we can see that it is guaranteed that he changed the position of the cube which was on the position 3 at first. So it is guaranteed that Stepan deceived his brother.
     92 
     93 In the third example for any values *l* and *r* there is a situation when Stepan said the truth.