codeforces-scrape

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

1623.md (4575B)


      1 Source: https://codeforces.com/blog/entry/98463
      2 
      3 In my opinion, all of the problems have a very simple solution and actually require no special data structure at all. To demonstrate the point, I will also use EvErYoNe'S fAvOrItE lAnGuAgE: **Pascal**.
      4 
      5 I will also include some notes, which are not related to the solution at all, but I find them interesting, so I will also include them in.
      6 
      7 ## [A. Robot Cleaner](https://codeforces.com/contest/1623/problem/A)
      8 
      9 Obviously, the problem is solvable using simulation. But it is solvable in $O(1)$ time as well, and I will discuss it.
     10 
     11 **Tutorial**
     12 
     13 Tutorial is loading...
     14 
     15 **Problem note**
     16 
     17 * Yes, I purposely make the constraint small. Firstly, the simulation solution is straightforward to think of, and I think everyone should be able to do it. But secondly, I wanted to see high-rated people suffering from going too fast :).
     18 * I hope that you like the animation! If you didn't know it yet, I use the library called [Manim](https://www.manim.community/), created by [3Blue1Brown](https://www.youtube.com/c/3blue1brown). He has a lot of great content about math with excellent animation. So if you wanted to see the illustrations in higher quality, or see the illustration of the other input, here is my [Jupyter Notebook on Google Colab](https://colab.research.google.com/drive/1vktCjRZiiGr0grAw68lTaZDqvJ8OJin3?authuser=1#scrollTo=2YqkyZZl_glG), that you can run directly and see it. The first example is already rendered but seems like the file is too big, and Google asks for a login first to see it.
     19 * Making the animation is one process, but uploading it is another. Polygon only supported a PNG file with the maximum size of 1 MB, so I need to first compress the GIF, and then convert it to APNG (animated PNG). The process is a little painful tho. Not only do I need the external tool for compression, but I need to reduce the playtime of the animation as well (so the other example besides the first one is faster).
     20 
     21 Pascal solution: [140968868](https://codeforces.com/contest/1623/submission/140968868). C++ solution: [140968900](https://codeforces.com/contest/1623/submission/140968900)
     22 
     23 ## [B. Game On Ranges](https://codeforces.com/contest/1623/problem/B)
     24 
     25 There are a lot of solutions to this problem. The solution I described below might be the simplest in my opinion.
     26 
     27 **Tutorial**
     28 
     29 Tutorial is loading...
     30 
     31 This problem can be solved in $O(n\log n)$ as well, and even $O(n)$ with some black magic like counting sort, but that is not required during the contest.
     32 
     33 **Problem note**
     34 
     35 * The game process is actually inspired by *Quick sort*: the range, picked by Alice, is the sorting range, and the number, picked by Bob, is the pivot.
     36 * Testers really like sorting. Some of the testers demand ***order*** for the input, so they need to do the sorting. But Nah, that is totally not required :)
     37 
     38 Pascal solution: [140968967](https://codeforces.com/contest/1623/submission/140968967). C++ solution: [140968942](https://codeforces.com/contest/1623/submission/140968942)
     39 
     40 ## [C. Balanced Stone Heaps](https://codeforces.com/contest/1623/problem/C)
     41 
     42 **Tutorial**
     43 
     44 Tutorial is loading...
     45 
     46 There is not much to note about this problem.
     47 
     48 Pascal solution: [140968985](https://codeforces.com/contest/1623/submission/140968985) C++ solution: [140969004](https://codeforces.com/contest/1623/submission/140969004)
     49 
     50 ## [D. Robot Cleaner Revisit](https://codeforces.com/contest/1623/problem/D)
     51 
     52 **Tutorial**
     53 
     54 Tutorial is loading...
     55 
     56 Using the $O(1)$ solution in problem $A$, this problem is solvable in $O(n + m)$ as well, but that is not required.
     57 
     58 **Problem note**
     59 
     60 * This is the *not planned* problem in the problem set.
     61 * All of the solutions that I saw, including the solution by testers and in the comments, use some sort of formulas, which I actually don't understand yet :).
     62 
     63 Pascal solution: [140969014](https://codeforces.com/contest/1623/submission/140969014) C++ solution: [140969025](https://codeforces.com/contest/1623/submission/140969025)
     64 
     65 ## [E. Middle Duplication](https://codeforces.com/contest/1623/problem/E)
     66 
     67 **Tutorial**
     68 
     69 Tutorial is loading...
     70 
     71 **Problem note**
     72 
     73 * The colors for the illustration are friendly to color-blind :).
     74 * If you are using a dark theme you will see a small hidden message in the illustration :). You can also see it by just changing the background to black (using F12 in the browser and changing the CSS).
     75 
     76 Pascal solution: [140969053](https://codeforces.com/contest/1623/submission/140969053) C++ solution: [140969037](https://codeforces.com/contest/1623/submission/140969037)