HackerEarth October Circuits '20 Editorial

Правка en29, от amsen, 2020-11-01 12:29:04

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

code

Two papers I:

For an edge $$$E$$$, consider number of matchings that includes $$$E$$$. if this number is even $$$E$$$ can be ignored. So the answer is xor of all $$$E$$$'s weight which belongs to odd number of matching.

Consider the tree is rooted from vertex $$$1$$$ and: 

  • $$$dpDown_{v, 0}$$$: parity of number of matchings for subtree of $$$v$$$ which using $$$v$$$ is forbidden for matchings.

  • $$$dpDown_{v, 1}$$$: parity of number of matchings for subtree of $$$v$$$ which using $$$v$$$ is allowed for matchings.

Both dps can be calculated easily by a dfs from root and updating parent's dps from childs.

For an edge from $$$v$$$ to $$$par_v$$$(parent of $$$v$$$), parity of number of matching which include this edge is:

$$$dpDown_{v, 0} \times \prod_{u\ is\ par_v's\ child\ except\ v} dpDown_{u, 1} \times X$$$, that $$$X$$$ is parity of number of matchings for all vertices else subtree of $$$par_v$$$. $$$X$$$ can be calculated and passed through dfs.

So for all of edges can seen that are they in odd number of edges or even by another dfs and passing and updating $$$X$$$ through dfs arguments.

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

code

Expectation:

Consider two dps:

  • $$$dpCnt_{from, to, len}$$$: number of grids with two rows and $$$2^{len}$$$ columns that are colored in black and white and its first column is $$$from$$$ and its last column is $$$to$$$.

  • $$$dpSum_{from, to, len}$$$: sum of number of maximal connected components of all grids with two rows and $$$2^{len}$$$ columns that are colored in black and white and its first column is $$$from$$$ and its last column is $$$to$$$.

for each $$$len$$$ its dps can be calculated by cutting it in two halfs, fix $$$from$$$ and $$$to$$$ for both halfs and it can be seen that:

  • $$$dp_cnt_{from , to, len} = \sum (dp_cnt_{from, to_l, len-1} \times dp_cnt_{from_r, to, len-1})$$$.

  • $$$dp_sum_{from , to, len} = \sum (dp_sum_{from, to_l, len-1} \times dp_cnt_{from_r, to, len-1} + dp_cnt_{from, to_l, len-1} \times dp_sum_{from_r, to, len-1} - X \times dp_cnt_{from, to_l, len-1} \times dp_cnt_{from_r, to, len-1} $$$.

  • which $$$X$$$ is number of components that are unified from touching $$$to_l$$$ and $$$from_r$$$. For answer dps can be merged like described above in a way that sum their $$$2^{len}$$$s is $$$n$$$.

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

История

 
 
 
 
Правки
 
 
  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)