codeforces-scrape

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

742.md (6424B)


      1 Source: https://codeforces.com/blog/entry/48871
      2 
      3 Hello again, and hope you have been Joon-Joon of the round :P
      4 
      5 **I’m preparing harder version of some of the problems (Div.2 A, B, and Div.1 A, D) and I’ll put them on some gym, so if you are interested in harder version of problems please wait for about one week.**
      6 
      7 You can see and download the problem archives (pretests, **tests**, statements, validator, checker, **solutions**) [here](https://mega.nz/#F!GoB1gCjK!fE_6d5qSSiqt_HMxAmV9GQ). You can see solutions in solutions folder, note that there are several codes there, there is a descriptor for each code (.desc) that shows the verdict of that code.
      8 
      9 ## Preparation details:
     10 
     11 On 25 May [Batman](/profile/Batman "Candidate Master Batman") came up with problem Div.1 D and other problems authored inchmeal.
     12 
     13 9/25/16: Proposal sent to Gleb.
     14 
     15 11/12/16: Answer from Gleb: Your proposal has been redirected to Nikolay [KAN](/profile/KAN "Grandmaster KAN").
     16 
     17 11/15/16: Nikolay has replied, and commented about problems, saying some problems are easy, some are hard, some are ok.
     18 
     19 I changed some of the problems, change the constraints for some others and we talked about solutions through email.
     20 
     21 11/17/16: We switched to Telegram.
     22 
     23 Creating tests, writing generators, writing statements, etc started in the Polygon.
     24 
     25 12/06/16: Round #383 hold.
     26 
     27 gKseni told me how you want to get your money and I had no idea.
     28 
     29 gKseni told me that it is possible to transfer my money and finally May 4, 2017, I received my money through Okpay.
     30 
     31 I have another problem set to prepare another div.1 + div.2 round, but I haven’t enough time now :(.
     32 
     33 Paintings in problems were suggested by me, painted by [Batman](/profile/Batman "Candidate Master Batman") and edited by me. Problem stories and this editorial were suggested and written by me. [KAN](/profile/KAN "Grandmaster KAN") helped us preparing the round very much, we are thankful to him. This table for each person and for each problem shows the number of the committed changes (in polygon) he has made in preparing the problem (it is good for showing how much someone was involved in preparing).
     34 
     35 I used Google Docs for writing everything.
     36 
     37 |  |  |  |  |  |  |  |  |  |
     38 | --- | --- | --- | --- | --- | --- | --- | --- | --- |
     39 | User\Problem | Div.2 A | Div.2 B | Div.1 A | Div.1 B | Div.1 C | Div.1 D | Div.1 E | Total |
     40 | Me | 8 | 9 | 16 | 16 | 10 | 19 | 37 | 114 |
     41 | [Batman](/profile/Batman "Candidate Master Batman") | 3 | 2 | 1 | 0 | 7 | 0 | 1 | 14 |
     42 | [KAN](/profile/KAN "Grandmaster KAN") and testers | 3 | 3 | 5 | 9 | 7 | 7 | 13 | 61 |
     43 
     44 Here is another table, showing the number of expected accepts (in my opinion, before the contest) and the number of accepts (after system testing).
     45 
     46 |  |  |  |  |  |  |  |  |  |  |  |
     47 | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
     48 |  | Div.2 A | Div.2 B | Div.2 C | Div.2 D | Div.2 E | Div.1 A | Div.1 B | Div.1 C | Div.1 D | Div.1 E |
     49 | Expected | 6000 | 4500 | 2000 | 500 | 150 | 600 | 400 | 300 | 50 | 10 |
     50 | Accepted | 3966 | 1723 | 1131 | 684 | 10 | 479 | 474 | 50 | 15 | 1 |
     51 
     52 # Hints
     53 
     54 **Div.2 A**: Write the last digit of 1378*n* for several small values.
     55 
     56 **Div.2 B** : Note that if ![](https://espresso.codeforces.com/97b98d65866bcf1f27adcc875f81808fe3bd0294.png) then ![](https://espresso.codeforces.com/30dff2e2575cabf2588d58866614079413c5a8d1.png).
     57 
     58 **Div.1 A**: If the answer exists, it depends on the lengths of cycles in the functional graph.
     59 
     60 **Div.1 B**: It’s similar to a simple knapsack problem, think on *O*(*n*·*W*) solution using dynamic programming.
     61 
     62 **Div.1 C**: Build a graph and put edges between each 2 * *i*, 2 * *i* + 1 and each BF and GF.
     63 
     64 **Div.1 D**: Keep a mask for each vertex, *i*-th bit of *mask**v* is *true* if the number of edges in the path from root to *v* such that letter *i* is written on them is odd. Now if number of bits in ![](https://espresso.codeforces.com/47000d828d53ef41ca1e419fd8bbb09c4ee9e5e2.png) is 0 or 1, path between *v* and *u* is Dokhtar-kosh.
     65 
     66 **Div.1 E**: Sort all of the options, then the problem becomes easier, solve the new problem with sqrt decomposition.
     67 
     68 # Details
     69 
     70 **Div.2 A**
     71 
     72 Idea, authoring, solution by [Batman](/profile/Batman "Candidate Master Batman"), preparation by [Batman](/profile/Batman "Candidate Master Batman") and me.
     73 
     74 My and [Batman](/profile/Batman "Candidate Master Batman") ’s birth year in [Solar Hijri calendar](https://en.wikipedia.org/wiki/Solar_Hijri_calendar) is 1378.
     75 
     76 **Div.2 B**
     77 
     78 Idea, authoring, solution by [Batman](/profile/Batman "Candidate Master Batman"), preparation by [Batman](/profile/Batman "Candidate Master Batman") and me.
     79 
     80 **Div.1 A**
     81 
     82 Idea, authoring, solution, preparation by me.
     83 
     84 Attractive boys/girls are called Joon-Joon in Persian. Owf is a sound used when we (Persian) are interested in something, especially when we see something attractive, such as our crush :P
     85 
     86 **Div.1 B**:
     87 
     88 Idea, authoring, solution, preparation by me.
     89 
     90 The problem authored by me 2 days before the contest :D (#FastAsFerrari). Attractive girls are called (some word similar to) “Hos” in Persian. It’s a good place to thank [amsen](/profile/amsen "Candidate Master amsen"), whose name (Hir) gave me this idea (to use word “Hos” instead of “attractive girl”).
     91 
     92 **Div.1 C** :
     93 
     94 Idea, authoring, solution by [Batman](/profile/Batman "Candidate Master Batman"), preparation by [Batman](/profile/Batman "Candidate Master Batman") and me.
     95 
     96 “Kooft” is something make people die. “Zahre-mar” meaning is “Venom of Snake”.
     97 
     98 **Div.1 D**:
     99 
    100 Idea by [Batman](/profile/Batman "Candidate Master Batman"), authoring, solution, preparation by me.
    101 
    102 “Dokhtar-kosh” is an adjective, used when something is very very attractive.
    103 
    104 **Div.1 E**:
    105 
    106 Idea, authoring, solution, preparation by me.
    107 
    108 # Solutions
    109 
    110 Tutorial is loading...
    111 
    112 Tutorial is loading...
    113 
    114 Tutorial is loading...
    115 
    116 Tutorial is loading...
    117 
    118 Tutorial is loading...
    119 
    120 Tutorial is loading...
    121 
    122 Tutorial is loading...
    123 
    124 I’d like to finish the editorial with the below poem by [Hafez](https://en.wikipedia.org/wiki/Hafez):
    125 
    126  از صدای سخن عشق ندیدم خوش‌تر   یادگاری که در این گنبد دوار بماند 
    127 
    128 Translation: I have never seen anything that sounds better than **love**, it’s the relic which will remain in the universe.
    129 
    130 Good luck and see you soon in **“Round #383 hard version”** ;)