HackerEarth October Circuits '20 Editorial

Revision en24, by amsen, 2020-11-01 11:51:16

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

Lonely M's array:

First reverse $$$a_1, a_2, .., a_n$$$.

Consider two following arrays:

  • $$$less_i, 1 \leq i \leq 3\times 10^5$$$: maximum length of all subsequence which ends with $$$... \leq i$$$.

  • $$$greater_i, 1 \leq i \leq 3\times 10^5$$$: maximum length of all subsequence which ends with $$$... \geq i$$$.

  • initially both are filled with zero.

Start sweep line form $$$1$$$ to $$$n$$$:

  • for each $$$a_i$$$ maximum length subsequence that ends with $$$... \leq a_i$$$ is $$$max_{j=1}^{a_i}(greater_j) + 1$$$ lets call it $$$X$$$.

  • for each $$$a_i$$$ maximum length subsequence that ends with $$$... \geq a_i$$$ is $$$max_{j=1}^{a_i}(less_j) + 1$$$ lets call it $$$Y$$$.

  • after calculating $$$X$$$ and $$$Y$$$, $$$less_{a_i}$$$ should be updated with $$$X$$$ and also greater_{a_i} should be updated with $$$Y$$$. The answer is $$$max_{i=1}^{3 \times 10^5}(less_i)$$$ because the subsequence should finish with $$$\leq$$$.

There are some RMQ(range maximum queries) and some single elements updates that all can be done using segment trees or fenwick trees (because queries are all either a prefix or suffix) in $$$log(3 \times 10^5)$$$.

So all can be done in $$$n \times log(3 \times 10^5)$$$.

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 &mdash; 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)