HackerEarth October Circuits '20 Editorial

Правка en20, от amsen, 2020-11-01 11:39:41

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)$$$.

code

Plan for nothing:

Consider an array $$$c_1, c_2, .., c_n$$$, for all intervals like $$$[l, r]$$$ do the following operation:

$$$c_l = c_l + 1$$$.

if $$$r < n$$$, $$$c_{r+1} = c_{r+1} - 1$$$. Then consider $$$pref_i = c_1 + c_2 + ... c_i$$$. a day is good for date if and only if $$$pref_i = 0$$$.

So the answer will be minimum $$$i$$$ that $$$pref_i = 0$$$ and if it doesn't exist answer is $$$-1$$$.

code

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
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)