codeforces-scrape

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

1663.md (9127B)


      1 Source: https://codeforces.com/blog/entry/101494
      2 
      3 All problems were created and prepared by me and [magnus.hegdahl](/profile/magnus.hegdahl "Candidate Master magnus.hegdahl"). Thanks to [BucketPotato](/profile/BucketPotato "International Master BucketPotato"), [Monogon](/profile/Monogon "Grandmaster Monogon"), and [Priyam2k](/profile/Priyam2k "Expert Priyam2k") for valuable feedback and testing. Special thanks to [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") for coming up with the idea and preparing the unique checker for [1663H - Cross-Language Program](/contest/1663/problem/H "April Fools Day Contest 2022"). I hope you enjoyed the contest, and found it to be an interesting series of puzzles.
      4 
      5 Example solution code written by [Agnimandur](/profile/Agnimandur "Master Agnimandur") is provided for each problem.
      6 
      7 ### [1663A - Who Tested?](/contest/1663/problem/A "April Fools Day Contest 2022")
      8 
      9 **Clue 1**
     10 
     11 The problem statement is the title of the problem.
     12 
     13 **Clue 2**
     14 
     15 Re-read the original announcement blog.
     16 
     17 **Solution**
     18 
     19 If you carefully read [the announcement blog](https://codeforces.com/blog/entry/101364), you will notice that I especially thanked [BucketPotato](/profile/BucketPotato "International Master BucketPotato") for testing. Just print "BucketPotato".
     20 
     21 **Solution Code (Python)**
     22 
     23 ```
     24 print("bucketpotato")
     25 ```
     26 
     27 ### [1663B - Mike's Sequence](/contest/1663/problem/B "April Fools Day Contest 2022")
     28 
     29 **Clue 1**
     30 
     31 Did you notice the peculiar constraints on the variable $r$?
     32 
     33 **Clue 2**
     34 
     35 "Mike" is of course [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"). "Mike's sequence" has to do with Codeforces ratings.
     36 
     37 **Clue 3**
     38 
     39 3000 is the cutoff for the highest rating: Legendary Grandmaster.
     40 
     41 **Solution**
     42 
     43 Mike's sequence are the Codeforces rating thresholds: [1200,1400,1600,1900,2100,2300,2400,2600,3000]. Your task is simply to print the threshold immediately above the provided rating $r$.
     44 
     45 **Solution Code (Python)**
     46 
     47 ```
     48 R = int(input())
     49 ratings = [1200,1400,1600,1900,2100,2300,2400,2600,3000]
     50 higher = [r for r in ratings if r > R]
     51 print(higher[0])
     52 ```
     53 
     54 ### [1663C - Pōja Verdon](/contest/1663/problem/C "April Fools Day Contest 2022")
     55 
     56 **Clue 1**
     57 
     58 [Aenar Targaryen](https://awoiaf.westeros.org/index.php/Aenar_Targaryen) was a dragonlord of Old Valyria.
     59 
     60 **Clue 2**
     61 
     62 The main clue is the title: "Pōja Verdon".
     63 
     64 **Solution**
     65 
     66 Aenar Targaryen was a dragonlord of Valyria (an empire from a *A Song of Ice and Fire*) who moved his family to Westeros right before Valyria was destroyed.
     67 
     68 `pōja` means `their` and `verdon` means `sum` (or `amount` based on context) in High Valyrian (you can easily translate this on [Duolingo](https://www.duolingo.com/dictionary/hv)).
     69 
     70 In a nutshell: Print the sum of the array.
     71 
     72 **Solution Code (Python)**
     73 
     74 ```
     75 n = int(input())
     76 nums = list(map(int,input().strip().split()))
     77 print(sum(nums))
     78 ```
     79 
     80 ### [1663D - Is it rated - 3](/contest/1663/problem/D "April Fools Day Contest 2022")
     81 
     82 **Clue 1**
     83 
     84 Did you notice that the problem had a special "constraints" section? That's highly unusual for a *Codeforces* problem.
     85 
     86 **Clue 2**
     87 
     88 The length of S is 3. Are there any famous three letter programming contests?
     89 
     90 **Solution**
     91 
     92 The capital variable letters and the "constraints" section are designed to mimic how [atcoder.jp](http://atcoder.jp) formats their problem statements.
     93 
     94 The problem is asking whether the [Atcoder contest](https://atcoder.jp) (ABC,ARC,AGC) is rated for a rating $X$. (Note that the judge ignores Atcoder heuristic contests for simplicity).
     95 
     96 * ABC's are rated for $[0,1999]$
     97 * ARC's are rated for $[0,2799]$
     98 * AGC's are rated for $[1200,\infty]$
     99 
    100 **Solution Code (Python)**
    101 
    102 ```
    103 s = input().strip()
    104 x = int(input().strip())
    105 if (s=="ABC" and x<2000) or (s=="ARC" and x<2800) or (s=="AGC" and x>=1200):
    106     print('yes')
    107 else:
    108     print('no')
    109 ```
    110 
    111 ### [1663E - Are You Safe?](/contest/1663/problem/E "April Fools Day Contest 2022")
    112 
    113 **Clue 1**
    114 
    115 Do you recognize the story of the Minotaur?
    116 
    117 **Clue 2**
    118 
    119 The problem is a word search, but not for the word "minotaur".
    120 
    121 **Solution**
    122 
    123 Perhaps you recognize the story of the minotaur? Less known is the hero who saved the kids from the minotaur: his name was Theseus [thee-see-us].
    124 
    125 The problem is just a word search (horizontal, vertical, diagonal) for `theseus`. You should only go in the forward direction when you search for a word.
    126 
    127 **Bonus Clues (for other problems)**
    128 
    129 The grid contains other clues embedded in it. Perhaps you can find `esoteric`, `java`, and `script` (hints for problem G). You might be able to find `atcoder` (hint for problem D). Also `hero` (hinting at Theseus for this problem).
    130 
    131 There are also some red herring words out there.
    132 
    133 **Solution Code (C++)**
    134 
    135 ```
    136 #include <bits/stdc++.h>
    137 using namespace std;
    138 
    139 void good() {
    140     cout << "YES";
    141     exit(0);
    142 }
    143 
    144 int main() {
    145     int N; cin >> N;
    146     char grid[N][N];
    147     for (int i = 0; i < N; i++) {
    148         string row; cin >> row;
    149         for (int j = 0; j < N; j++) grid[i][j] = row[j];
    150     }
    151 
    152     string word = "theseus";
    153     for (int i = 0; i < N; i++) {
    154 		for (int j = 0; j < N; j++) {
    155 			if (i < N-7) {
    156 				string w = "";
    157 				for (int k = 0; k < 7; k++) w += grid[i+k][j];
    158 				if (w == word) good();
    159 			}
    160 			if (j < N-7) {
    161 				string w = "";
    162 				for (int k = 0; k < 7; k++) w += grid[i][j+k];
    163 				if (w == word) good();
    164 			}
    165 			if (i < N-7 && j < N-7) {
    166 				string w = "";
    167 				for (int k = 0; k < 7; k++) w += grid[i+k][j+k];
    168 				if (w == word) good();
    169 			}
    170 		}
    171     }
    172     cout << "NO";
    173 }
    174 ```
    175 
    176 ### [1663F - In Every Generation...](/contest/1663/problem/F "April Fools Day Contest 2022")
    177 
    178 **Clue 1**
    179 
    180 Where is the quote from?
    181 
    182 **Clue 2**
    183 
    184 "buffy", "the", "vampire", "slayer"
    185 
    186 **Clue 3**
    187 
    188 "buffy" (length 5), "the" (length 3), "vampire" (length 7), "slayer" (length 6). Remember how $3 \le |s| \le 7$? Now go back to the sample and see what you can do.
    189 
    190 **Solution**
    191 
    192 The quote is from the well known TV series [Buffy the Vampire Slayer](https://en.wikipedia.org/wiki/Buffy_the_Vampire_Slayer).
    193 
    194 Perhaps you notice the lengths of the words `buffy`, `the`, `vampire`, `slayer` are unique integers in the set {3,5,6,7}.
    195 
    196 Given the string $s$, simply "add" that string with the target word of the same length.
    197 
    198 Here's how adding two letters work:
    199 
    200 1. Convert both letters to numbers in $[0,25]$.
    201 2. Add the two numbers up modulo 26.
    202 3. Convert the number back into a letter.
    203 
    204 You can verify your addition algorithm is correct by checking whether "tourist" + "vampire" = "ooggqjx" (as provided in the sample).
    205 
    206 Finally, if the length of $s$ is $4$, the answer is "none", because there is no word of length 4 in Buffy the Vampire Slayer.
    207 
    208 **Solution Code (Python)**
    209 
    210 ```
    211 s = input().strip()
    212 words = ["","","","the","","buffy","slayer","vampire"]
    213 if len(s)==4:
    214     print("none")
    215 else:
    216     target = words[len(s)]
    217     ans = ""
    218     for i in range(len(s)):
    219         a = ord(s[i])-ord('a')
    220         b = ord(target[i])-ord('a')
    221         ans += chr((a+b)%26 + ord('a'))
    222     print(ans)
    223 ```
    224 
    225 ### [1663G - Six Characters](/contest/1663/problem/G "April Fools Day Contest 2022")
    226 
    227 **Clue 1**
    228 
    229 Input is a normal string of letters, but output consists of non-letter *characters*?
    230 
    231 **Clue 2**
    232 
    233 Think of an esoteric programming language.
    234 
    235 **Clue 3**
    236 
    237 [JSF](https://en.wikipedia.org/wiki/JSFuck) (an esoteric programming language equivalent to Javascript that only uses 6 characters).
    238 
    239 **Solution**
    240 
    241 The April Fool's Contests love of esoteric programming languages, combined with the reference to "six characters", will eventually lead you to JSFuck.
    242 
    243 The six characters is a pun: the input is a string of length 6 like "abcdef", but the output is a string \textit{consisting} of only 6 characters: `[ ] ( ) ! +`.
    244 
    245 Brief research will demonstrate a mapping from each english letter to a JSFuck string. Two letters can be concatenated with "+".Note that the optimal mapping will make your solution file approximately 12KB in size, well within the 64KB requirement of Codeforces.
    246 
    247 However, the mapping from each letter to javascript is not unique! However, the legend mentions that Aenar needs to go to the string's "home". JSFuck's home website is [here](https://jsfuck.com), which is where the jury's mapping is created from.
    248 
    249 Alternatively, instead of hardcoding the generated strings, you can simply use the encoding algorithm provided in the [Github](https://github.com/aemkei/jsfuck).
    250 
    251 **Solution Code (Python and Javascript)**
    252 
    253 Hard-coding strings: [152393980](/contest/1663/submission/152393980 "Submission 152393980 by Agnimandur")
    254 
    255 Algorithmically generating strings (in Javascript): [152398972](/contest/1663/submission/152398972 "Submission 152398972 by BigDelta") (credit to [BigDelta](/profile/BigDelta "Master BigDelta"))
    256 
    257 ### [1663H - Cross-Language Program](/contest/1663/problem/H "April Fools Day Contest 2022")
    258 
    259 **Solution**
    260 
    261 Google research into how Pascal and C++ work will eventually lead you to a solution like this. Many people used the fact that `\` can be used to continue single line comments to the next line in C++ but not in Pascal.
    262 
    263 ```
    264 // \
    265 begin end.
    266 int main() {}
    267 ```