codeforces-scrape

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

1800E1.md (3277B)


      1 Source: https://codeforces.com/problemset/problem/1800/E1
      2 
      3 E1. Unforgivable Curse (easy version)
      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 This is an easy version of the problem. In this version, $k$ is always $3$.
     22 
     23 The chief wizard of the Wizengamot once caught the evil wizard Drahyrt, but the evil wizard has returned and wants revenge on the chief wizard. So he stole spell $s$ from his student Harry.
     24 
     25 The spell — is a $n$-length string of lowercase Latin letters.
     26 
     27 Drahyrt wants to replace spell with an unforgivable curse — string $t$.
     28 
     29 Drahyrt, using ancient magic, can swap letters at a distance $k$ or $k+1$ in spell as many times as he wants. In this version of the problem, you can swap letters at a distance of $3$ or $4$. In other words, Drahyrt can change letters in positions $i$ and $j$ in spell $s$ if $|i-j|=3$ or $|i-j|=4$.
     30 
     31 For example, if $s = $ "talant" and $t = $ "atltna", Drahyrt can act as follows:
     32 
     33 * swap the letters at positions $1$ and $4$ to get spell "aaltnt".
     34 * swap the letters at positions $2$ and $6$ to get spell "atltna".
     35 
     36 You are given spells $s$ and $t$. Can Drahyrt change spell $s$ to $t$?
     37 
     38 Input
     39 
     40 The first line of input gives a single integer $T$ ($1 \le T \le 10^4$) — the number of test cases in the test.
     41 
     42 Descriptions of the test cases are follow.
     43 
     44 The first line contains two integers $n, k$ ($1 \le n \le 2 \cdot 10^5$, $k = 3$) — the length spells and the number $k$ such that Drahyrt can change letters in a spell at a distance $k$ or $k+1$.
     45 
     46 The second line gives spell $s$ — a string of length $n$ consisting of lowercase Latin letters.
     47 
     48 The third line gives spell $t$ — a string of length $n$ consisting of lowercase Latin letters.
     49 
     50 It is guaranteed that the sum of $n$ values over all test cases does not exceed $2 \cdot 10^5$. Note that there is no limit on the sum of $k$ values over all test cases.
     51 
     52 Output
     53 
     54 For each test case, output on a separate line "YES" if Drahyrt can change spell $s$ to $t$ and "NO" otherwise.
     55 
     56 You can output the answer in any case (for example, lines "yEs", "yes", "Yes" and "YES" will be recognized as positive answer).
     57 
     58 Example
     59 
     60 Input
     61 
     62 ```
     63 7
     64 
     65 6 3
     66 
     67 talant
     68 
     69 atltna
     70 
     71 7 3
     72 
     73 abacaba
     74 
     75 aaaabbc
     76 
     77 12 3
     78 
     79 abracadabraa
     80 
     81 avadakedavra
     82 
     83 5 3
     84 
     85 accio
     86 
     87 cicao
     88 
     89 5 3
     90 
     91 lumos
     92 
     93 molus
     94 
     95 4 3
     96 
     97 uwjt
     98 
     99 twju
    100 
    101 4 3
    102 
    103 kvpx
    104 
    105 vxpk
    106 ```
    107 
    108 Output
    109 
    110 ```
    111 YES
    112 YES
    113 NO
    114 YES
    115 NO
    116 YES
    117 NO
    118 ```
    119 
    120 Note
    121 
    122 The first example is explained in the condition.
    123 
    124 In the second example we can proceed as follows:
    125 
    126 * Swap the letters at positions $2$ and $5$ (distance $3$), then we get the spell "aaacbba".
    127 * Swap the letters at positions $4$ and $7$ (distance $3$), then you get the spell "aaaabbc".
    128 
    129 In the third example, we can show that it is impossible to get the string $t$ from the string $s$ by swapping the letters at a distance of $3$ or $4$.
    130 
    131 In the fourth example, for example, the following sequence of transformations is appropriate:
    132 
    133 * "accio" $\rightarrow$ "aocic" $\rightarrow$ "cocia" $\rightarrow$ "iocca" $\rightarrow$ "aocci" $\rightarrow$ "aicco" $\rightarrow$ "cicao"
    134 
    135 In the fifth example, you can show that it is impossible to get the string $s$ from the string $t$.
    136 
    137 In the sixth example, it is enough to swap the two outermost letters.