codeforces-scrape

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

2164.md (3126B)


      1 Source: https://codeforces.com/blog/entry/148126
      2 
      3 ## A Sequence Game
      4 
      5 Idea from [cmk666](/profile/cmk666 "Legendary Grandmaster cmk666"), Prepared by [cmk666](/profile/cmk666 "Legendary Grandmaster cmk666")
      6 
      7 **Hint 1**
      8 
      9 Think some straightforward necessary conditions. They are also sufficient.
     10 
     11 **Tutorial**
     12 
     13 Tutorial is loading...
     14 
     15 ## B Even Modulo Pair
     16 
     17 Idea from [244mhq](/profile/244mhq "Legendary Grandmaster 244mhq"), Prepared by [NetSpeed1](/profile/NetSpeed1 "Legendary Grandmaster NetSpeed1")
     18 
     19 **Hint 1**
     20 
     21 Consider a brute force solution. What's the actual complexity of it?
     22 
     23 **Tutorial**
     24 
     25 Tutorial is loading...
     26 
     27 ## C Dungeon
     28 
     29 Idea from [Link_Cut_qwq](/profile/Link_Cut_qwq "Grandmaster Link_Cut_qwq"), Prepared by [Xiaohuba](/profile/Xiaohuba "Master Xiaohuba")
     30 
     31 **Hint 1**
     32 
     33 If you gain a new sword after killing a monster, its damage will be greater or equal than the previous sword.
     34 
     35 **Hint 2**
     36 
     37 When will we attempt to kill monsters with $c_i = 0$?
     38 
     39 **Hint 3**
     40 
     41 Consider a greedy approach.
     42 
     43 **Tutorial**
     44 
     45 Tutorial is loading...
     46 
     47 ## D Copy String
     48 
     49 Idea from [JoesSR](/profile/JoesSR "Legendary Grandmaster JoesSR"), Prepared by [JoesSR](/profile/JoesSR "Legendary Grandmaster JoesSR")
     50 
     51 **Tutorial**
     52 
     53 Tutorial is loading...
     54 
     55 ## E Journey
     56 
     57 Idea from [Link_Cut_qwq](/profile/Link_Cut_qwq "Grandmaster Link_Cut_qwq"), Prepared by [Xiaohuba](/profile/Xiaohuba "Master Xiaohuba")
     58 
     59 **Hint 1**
     60 
     61 Consider when we do not need *transferring*.
     62 
     63 **Hint 2**
     64 
     65 How to calculate the minimum cost when *transferring* between two vertices?
     66 
     67 **Hint 3**
     68 
     69 Come up with a greedy approach.
     70 
     71 **Tutorial**
     72 
     73 Tutorial is loading...
     74 
     75 ## F1/F2 Chain Prefix Rank
     76 
     77 Idea from [JoesSR](/profile/JoesSR "Legendary Grandmaster JoesSR"), Prepared by [JoesSR](/profile/JoesSR "Legendary Grandmaster JoesSR")
     78 
     79 **Tutorial**
     80 
     81 Tutorial is loading...
     82 
     83 ## G Pointless Machine
     84 
     85 Idea from [Daniel777](/profile/Daniel777 "International Grandmaster Daniel777"), Prepared by [zjy2008](/profile/zjy2008 "Legendary Grandmaster zjy2008")
     86 
     87 **Hint 1**
     88 
     89 We can know the degree of each vertex within two queries.
     90 
     91 **Hint 2**
     92 
     93 First come up with an solution that require $2\lceil\log_2(n)\rceil+1$ queries.
     94 
     95 **Hint 3**
     96 
     97 Partition the vertex to 3 groups instead of 2.
     98 
     99 **Tutorial**
    100 
    101 Tutorial is loading...
    102 
    103 ## H PalindromePalindrome
    104 
    105 Idea from [zjy2008](/profile/zjy2008 "Legendary Grandmaster zjy2008"), Prepared by [zjy2008](/profile/zjy2008 "Legendary Grandmaster zjy2008")
    106 
    107 **UPD: Unfortunately, the original analysis regarding the number of "relevant" pairs of disjoint substrings was incorrect. The proof was derived from an online blog concerning the range distinct palindrome substring query problem, but that proof turned out to be flawed. Consequently, we previously believed the complexity of the standard solution to be $O((n + q) \log n)$; however, after the contest, we discovered that it is actually $\Theta(n \log^2 n + q \log n)$ (and this lower bound is reachable). We apologize for any confusion caused.**
    108 
    109 **Hint 1**
    110 
    111 Consider classifying the cases based on the relative positions of two palindromic substrings.
    112 
    113 **Tutorial**
    114 
    115 Tutorial is loading...