HackerEarth October Circuits '20 Editorial

Revision en14, by amsen, 2020-11-01 11:28:25

### Letter most:

For each lowercase letter count number of its occurrences in $s$, maximum of this value for all letters is the answer. All can be done in $O(n)$.

code

### Array modification:

Assume  will be the maximum. it can be proven that all operation should be done in direction of $x$($j=i+1$ for all operation on its left and $j=i-1$ for all operations on its right).

Now consider $pref_x$ is maximum value of $a_x$ if all operations be done in direction of right for all $i=1, 2, ..., x$. And consider $suf_x$ is maximum value of $a_x$ if all operations be done in direction of left for all $i=x, x+1, ..., n$.

It can bee seen that:

$pref_x = \frac{perf_{x-1}}{2} + a_x$.

$suf_x = \frac{suf_{x+1}}{2} + a_x$.

And so the answer is $max_{i=1}^{n}(pref_i + suf_i — a_i)$.

All can be done in $O(n)$.

#### History

Revisions

Rev. Lang. By When Δ Comment
en34 amsen 2020-11-01 12:40:21 0 (published)
en33 amsen 2020-11-01 12:39:47 45 Tiny change: ' $O(n+m)$.' -> ' $O(n+m)$.\n\n[code](https://pastebin.pl/view/96c733c3)'
en32 amsen 2020-11-01 12:37:50 1023
en31 amsen 2020-11-01 12:31:46 45 Tiny change: '(log(n))$.' -> '(log(n))$.\n\n[code](https://pastebin.pl/view/8c953c19)'
en30 amsen 2020-11-01 12:30:29 40
en29 amsen 2020-11-01 12:29:04 1276
en28 amsen 2020-11-01 12:18:13 45 Tiny change: 'in $O(n)$.' -> 'in $O(n)$.\n\n[code](https://pastebin.pl/view/7e04f4c3)'
en27 amsen 2020-11-01 12:11:17 16
en26 amsen 2020-11-01 12:07:48 1171
en25 amsen 2020-11-01 11:56:01 45 Tiny change: '0^5)$.\n\n' -> '0^5)$.\n\n[code](https://pastebin.pl/view/2f533467)\n\n'
en24 amsen 2020-11-01 11:51:16 1304
en23 amsen 2020-11-01 11:41:31 6
en22 amsen 2020-11-01 11:41:16 4
en21 amsen 2020-11-01 11:40:50 16
en20 amsen 2020-11-01 11:39:41 47
en19 amsen 2020-11-01 11:37:56 457
en18 amsen 2020-11-01 11:33:23 45 Tiny change: 'in $O(n)$.' -> 'in $O(n)$.\n\n[code](https://pastebin.pl/view/9234cd82)'
en17 amsen 2020-11-01 11:30:52 8 Tiny change: 'i + suf_i &mdash; a_i)$.\n\' -> 'i + suf_i - a_i)$.\n\'
en16 amsen 2020-11-01 11:30:08 18
en15 amsen 2020-11-01 11:29:13 9
en14 amsen 2020-11-01 11:28:25 2 Tiny change: 'rection of $x$($j=i+1' -> 'rection of$x$($j=i+1'
en13 amsen 2020-11-01 11:28:01 18
en12 amsen 2020-11-01 11:27:12 2 Tiny change: 'ction of $x$($j=i+1$ ' -> 'ction of $$x$$($j=i+1$ '
en11 amsen 2020-11-01 11:26:26 4
en10 amsen 2020-11-01 11:25:27 841
en9 amsen 2020-11-01 11:20:17 3
en8 amsen 2020-11-01 11:19:19 56 Tiny change: 'rrences in $s$ , maximum ' -> 'rrences in $j$, maximum '
en7 amsen 2020-11-01 11:13:13 3 Tiny change: 'ences in $s$, maximum ' -> 'ences in $s$ , maximum '
en6 amsen 2020-11-01 11:12:29 3 Tiny change: 'ences in $s$ , maximum ' -> 'ences in $s$, maximum '
en5 amsen 2020-11-01 11:12:01 1 Tiny change: 'ces in $s$, maximum ' -> 'ces in $s$ , maximum '
en4 amsen 2020-11-01 11:11:03 144
en3 amsen 2020-11-01 11:10:01 135
en2 amsen 2020-11-01 11:09:17 18 Tiny change: 'Letter most:\n------------' -> '### Letter most:'
en1 amsen 2020-11-01 11:08:23 68 Initial revision (saved to drafts)