codeforces-scrape

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

1488.md (8106B)


      1 Source: https://codeforces.com/blog/entry/88522
      2 
      3 First of all, I would like to thank all testers of the round: [Um_nik](/profile/Um_nik "Легендарный гроссмейстер Um_nik"), [IlyaLos](/profile/IlyaLos "Международный мастер IlyaLos"), [Roms](/profile/Roms "Мастер Roms"), [nuipojaluista](/profile/nuipojaluista "Эксперт nuipojaluista"), [Supermagzzz](/profile/Supermagzzz "Мастер Supermagzzz"), [Stepavly](/profile/Stepavly "Мастер Stepavly"), [hg333](/profile/hg333 "Мастер hg333"). Also huge thanks to co-authors of the contest: [Neon](/profile/Neon "Кандидат в мастера Neon"), [adedalic](/profile/adedalic "Международный мастер adedalic"), [vovuh](/profile/vovuh "Мастер vovuh") and [awoo](/profile/awoo "Гроссмейстер awoo").
      4 
      5 I hope you enjoyed participating in the round!
      6 
      7 Okay, now for the editorial itself:
      8 
      9 [1488A - От нуля до Y](/contest/1488/problem/A "Kotlin Heroes: Episode 6")
     10 
     11 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [Neon](/profile/Neon "Кандидат в мастера Neon")
     12 
     13 **Tutorial**
     14 
     15 Tutorial is loading...
     16 
     17 [1488B - Удаление ПСП](/contest/1488/problem/B "Kotlin Heroes: Episode 6")
     18 
     19 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest")
     20 
     21 **Tutorial**
     22 
     23 Tutorial is loading...
     24 
     25 [1488C - Двое полицейских](/contest/1488/problem/C "Kotlin Heroes: Episode 6")
     26 
     27 Idea: [vovuh](/profile/vovuh "Мастер vovuh"), preparation: [vovuh](/profile/vovuh "Мастер vovuh")
     28 
     29 **Tutorial**
     30 
     31 Tutorial is loading...
     32 
     33 [1488D - Марафон решения задач](/contest/1488/problem/D "Kotlin Heroes: Episode 6")
     34 
     35 Idea: [vovuh](/profile/vovuh "Мастер vovuh"), preparation: [awoo](/profile/awoo "Гроссмейстер awoo")
     36 
     37 **Tutorial**
     38 
     39 Consider the minimum possible answer. Since you have to do all $s$ problems in $n$ days, you can do $\lfloor \frac s n \rfloor$ in some of them and then $\lceil \frac s n \rceil$ in the rest of the days. Thus, $\lceil \frac s n \rceil$ is the minimum possible $a_n$.
     40 
     41 Now it would be great if the function that tells if some $x$ can be the number of problems during the last day was monotonous for all $x$ from $\lceil \frac s n \rceil$ to $\infty$. So that function first returns true for some prefix of values, then it returns false. Intuitively, it sounds monotonous: the smaller values allow a lot of freedom for the construction and the larger values fail because they require too many problems in total.
     42 
     43 The difficulty rises from the fact we not only have to prove that, but we also have to find a way to ask the result of that function quickly.
     44 
     45 If we didn't have to, the proof would not be too hard.
     46 
     47 **Proof**
     48 
     49 Consider some distribution of $s$ problems such that the last element is $x \gt \lceil \frac s n \rceil$. Let's move some problems around to make the last element $x-1$. So there is a block of days with $x$ problems at the end. There also is a block of days with the number of problems equal to the first day. You can always move the problem from the first day of the ending block to the last day of the beginning block.
     50 
     51 Let's call the first day of the ending block $r$ and the last day of the beginning block $l$. Observe that the condition between $r-1$ and $r$ never breaks. Since the difference between $a_{r-1}$ and $a_r$ decreased, if it was two-fold or less then it's still two-fold or less. Same for $l$ and $l+1$. In the case of $l=r-1$, the difference between $a_l$ and $a_r$ must have been at least $2$, thus, $a_l \le a_r$ after the move. The difference can't be $1$ because then it is exactly the same construction we have built for the minimum case, thus $x=\lceil \frac s n \rceil$. The condition between $r$ and $r+1$ also can't break. If $r$ is the last day, then there is no $r+1$. Otherwise, $a_r$ becomes equal to $a_{r+1} - 1$. Since all the values are positive, that difference can't become above two-fold. Same reasoning goes for $l$ and $l-1$.
     52 
     53 So that move is always valid. That move also decreases the size of the ending block by $1$. Thus, at some point the ending block will be of size $1$, so making a move from it will decrease the last value by $1$. That proves that for any $x$ that can be the last value, $x-1$ can also be the last value. Thus, the function is indeed monotonous.
     54 
     55 Now that we are absolutely sure that the function is monotonous, let's change our approach.
     56 
     57 Obviously, we should try binary search on $x$. So we have the total number of problems $s$, the number of days $n$ and some fixed number of problems during the last day $x$.
     58 
     59 Our second educated guess can be of the following kind. Given fixed $n$ and $x$, all the possible values of $s$ that can correspond to some construction are some segment of integers. That can actually be proven in the similar manner.
     60 
     61 **Proof**
     62 
     63 Consider the smallest value of $s$ that can be obtained: the last day has $x$ problems, the second to last has $\lceil \frac x 2 \rceil$ and so on.
     64 
     65 In any construction there is a block of days with the number of problems equal to the first day. You can always add a problem to the last day of that block, thus increasing the total number of problems by $1$. The casework is basically the same as in the first proof.
     66 
     67 That construction also implies that the smallest value of $s$ grows as $x$ grows.
     68 
     69 So we can binary search for a solution for $x$ from $\lceil \frac s n \rceil$ to $s$. $f(x)$ can be the smallest total number of problems such that there exists a distribution. Since that value is monotonous, you can look for the largest $x$ such that $f(x) \le s$.
     70 
     71 To calculate the function you can observe that the sequence $x$, $\lceil \frac x 2 \rceil$, $\left\lceil \frac{\lceil \frac x 2 \rceil}{2} \right\rceil$, $\dots$ has only ones after $\log(x)$ values.
     72 
     73 Overall complexity: $O(\log^2 s)$ per testcase.
     74 
     75 [1488E - Палиндромные пары](/contest/1488/problem/E "Kotlin Heroes: Episode 6")
     76 
     77 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [awoo](/profile/awoo "Гроссмейстер awoo")
     78 
     79 **Tutorial**
     80 
     81 Tutorial is loading...
     82 
     83 [1488F - Dogecoin](/contest/1488/problem/F "Kotlin Heroes: Episode 6")
     84 
     85 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest") and [Neon](/profile/Neon "Кандидат в мастера Neon"), preparation: [Neon](/profile/Neon "Кандидат в мастера Neon")
     86 
     87 **Tutorial**
     88 
     89 Tutorial is loading...
     90 
     91 [1488G - Раскраска чисел](/contest/1488/problem/G "Kotlin Heroes: Episode 6")
     92 
     93 Idea: [Neon](/profile/Neon "Кандидат в мастера Neon"), preparation: [Neon](/profile/Neon "Кандидат в мастера Neon")
     94 
     95 **Tutorial**
     96 
     97 Tutorial is loading...
     98 
     99 [1488H - Построй из суффиксов](/contest/1488/problem/H "Kotlin Heroes: Episode 6")
    100 
    101 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [awoo](/profile/awoo "Гроссмейстер awoo")
    102 
    103 **Tutorial**
    104 
    105 Tutorial is loading...
    106 
    107 [1488I - Вторжение демонов](/contest/1488/problem/I "Kotlin Heroes: Episode 6")
    108 
    109 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest")
    110 
    111 **Tutorial**
    112 
    113 Tutorial is loading...
    114 
    115 [1488J - Цветочный магазин](/contest/1488/problem/J "Kotlin Heroes: Episode 6")
    116 
    117 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [Neon](/profile/Neon "Кандидат в мастера Neon") and [adedalic](/profile/adedalic "Международный мастер adedalic")
    118 
    119 **Tutorial**
    120 
    121 Tutorial is loading...