HackerEarth October Circuits '20 Editorial

Revision en10, by amsen, 2020-11-01 11:25:27

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