Unofficial Editorial for Educational Round 94 (Div. 2)

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Haven't done one of these for a while! Here are my approaches to the problems:

1400A - String Similarity

We just need to make sure our string of $$$n$$$ characters matches each of the $$$n$$$ substrings in at least one spot. The easiest way to do this is to take every other character from $$$s$$$. Code: 90908018

Another fun solution: we can generate random strings and check them until we find one that matches everything. This works because the probability of failing to match any particular substring is $$$\frac{1}{2^n}$$$, so as $$$n$$$ gets bigger the probability of failing gets extremely low. Code: 90999219

1400B - RPG Protagonist

First iterate on the number of swords we will personally take. Then we should greedily take as many war axes as we can until we run out of money. At this point, our follower needs to take as many items as possible. They can do this by greedily taking whichever of swords or war axes are cheaper until they run out, followed by taking the more expensive of the two. Code: 90918673

1400C - Binary String Reconstruction

Note that $$$s_i = 1$$$ means "either $$$w_{i - x} = 1$$$ or $$$w_{i + x} = 1$$$," whereas $$$s_i = 0$$$ means "both $$$w_{i - x} = 0$$$ and $$$w_{i + x} = 0$$$." We can greedily solve this by starting out our string $$$w$$$ with all 1's, then marking $$$i - x$$$ and $$$i + x$$$ as 0 whenever we are forced to because $$$s_i = 0$$$. Then we can simply check whether all of the $$$s_i = 1$$$ conditions are valid to confirm. Code: 90915688

1400D - Zigzags

We can rethink this as counting the number of equal pairs $$$(a_i, a_j) = (a_k, a_l)$$$ where $$$i < j < k < l$$$. To do this we loop over $$$j$$$ from right to left and make sure we have all $$$(a_k, a_l)$$$ pairs where $$$k > j$$$ counted in a map. Then we simply iterate over $$$i$$$ and add up the number of occurrences of each $$$(a_i, a_j)$$$ in the map.

For implementation details, note that we don't actually want to use a map and make our code slower. We can just use an array of size $$$n^2$$$ and convert the pair $$$(a_i, a_j)$$$ to the number $$$a_i \cdot n + a_j$$$ since the $$$a_i$$$ are in the range $$$[1, n]$$$. As a bonus, even if the $$$a_i$$$ were larger than $$$n$$$, we could just compress them down to $$$[1, n]$$$ and repeat the solution above. Code: 91019003

1400E - Clear the Multiset

Notice that we can reorder the operations in any way we want without affecting the result. So let's do all of the first-type operations before the second-type operations. Then it's clear that the number of second-type operations we'll need is the number of nonzero elements left over after the first-type operations. So we just want to choose first-type operations to minimize the number of first-type operations plus the number of nonzero elements left after we're done.

Let's say we have an array $$$a$$$ where $$$a_m$$$ is the minimum value (if there is a tie, you can pick any tied index). I only have a messy proof for this at the moment, but it turns out we only need to consider two options: either take all $$$n$$$ second-type operations, or use $$$a_m$$$ first-type operations on the entire array and then recursively solve $$$a_1 - a_m, ..., a_{m - 1} - a_m$$$ and $$$a_{m + 1} - a_m, ..., a_n - a_m$$$ separately. This leads to a simple $$$n^2$$$ solution: 90999997.

Note that by using RMQ we can improve this to $$$\mathcal{O}(n \log n)$$$ or even $$$\mathcal{O}(n)$$$. The idea is very similar to the solution to problem G here.

1400F - x-prime Substrings

The key observation is that since $$$x$$$ is only up to 20, there can't be that many different $$$x$$$-prime strings total--turns out there are only about 2400 for the worst case of $$$x = 19$$$. So we can generate all of them and perform a DP where our state is represented by the longest prefix of any of the strings we currently match. We can do this by building a trie of all of the $$$x$$$-prime strings. We then need to be able to transition around in this trie; it turns out this is exactly what Aho-Corasick does for us. In particular, knowing which node of the Aho-Corasick tree we are currently at gives us the full information we need to determine whether or not we will match one of the strings after adding more characters later. This leads to a fairly simple DP: 90977148

1400G - Mercenaries

In order to take care of the $$$l_i$$$ and $$$r_i$$$ constraints, we can iterate on the number of mercenaries we'll choose and find the number of choices for each count. The key constraint in this problem is that $$$m$$$ is at most 20, which means that there can only be a few connected components that aren't just a single node. In particular, the largest possible connected component size is 21 (since a connected graph with $$$m$$$ edges has at most $$$m + 1$$$ nodes).

This means that for each connected component we can iterate over all of the subsets of nodes in that component and check whether the subset is a valid choice (i.e., is an independent set). We can then do a DP for each component where dp(mask, k) = the number of submasks of mask that have k ones and represent a valid independent set subset of the component.

Finally we can iterate over the total number of mercenaries we want. We can then do a knapsack over each of the components, making sure to only consider nodes in each component where $$$l_i$$$ and $$$r_i$$$ work with our number of mercenaries. Finally we determine how many valid $$$l_i, r_i$$$ mercenaries are available outside of our components, and the rest is a simple choose function. Code: 90977154

#include<iostream> using namespace std; int main() { int t; cin >> t; while (t--) { int n; cin >> n; int arr[n]; for (int i=0; i<n; i++) { cin >> arr[i]; } int ans = 0; for (int i=0; i<n-1; i++) { int mid[3005] = {0}; int right[3005] = {0}; if (i+1 < n) mid[arr[i+1]]++; for (int j=i+3; j<n; j++) right[arr[j]]++; int count = mid[arr[i+1]]*right[arr[i+1]]; int k = i+2; while (k<n) { if (arr[i] == arr[k]) { ans += count; } // increment k k++; mid[arr[k-1]]++; // as prev k will be in middle elements if (k < n) right[arr[k]]--; if (k < n && right[arr[k]] < 0) right[arr[k]] = 0; // frequency can't be -ve count += (right[arr[k-1]]); // asnewly added pairs due to increment of k if (k < n) count -= (mid[arr[k]]); if (count < 0) count = 0; } } cout << ans << endl; } return 0; }

this is virtual zero in the end as a helper v 0 1 2 4 3 5 6 2 1 0 // numbers 1 1 2 0 2 1 0 0 0 // max(difference, 0) ^ this is virtual zero in the beginning as a helper.

this is virtual zero in the end as a helper v 0 1 2 4 3 5 6 2 1 0 // numbers 0 0 0 1 0 0 4 1 1 // differences ^ this is virtual zero in the beginning as a helper.

Comments (112)

Show archived | Write comment?

Bojack_human

4 years ago, # |

https://codeforces.me/contest/1400/submission/90994198 , this solution just got hacked can someone help me find my mistake?

→ Reply

psruk

4 years ago, # ^ |

+17

For test case n = 1, arr = {0} it returns 1 instead of 0 because your solution for all test cases where n = 1 returns 1.

thanks a lot man.

thesinhajee

neal Can you explain the implementation in D again? I couldn't get how did you convert the pair(a[i],a[j]) to a[i]*n+a[j]. Thanks, in advance!

neal

+33

The idea is if $$$a$$$ and $$$b$$$ are both numbers in $$$[0, n)$$$ (meaning at least 0 and at most $$$n - 1$$$), then $$$an + b$$$ maps the pair $$$(a, b)$$$ to a unique number in $$$[0, n^2)$$$. This is the same idea as how 2D arrays work.

I got it, thanks a lot again!

018429

neal Can you explain the implementation in D 'if the ai were larger than n, we could just compress them down to [1,n]'

+19

This is the standard idea of coordinate compression, where the actual values of the $$$a_i$$$ don't matter, only their relative comparisons (<, =, >). So we can replace every $$$a_i$$$ with their index in the sorted array instead. For example $$$[5, 12, 9]$$$ -> $$$[0, 2, 1]$$$.

thanks~

shubham7999

Neil can you clear how you made this formula ai * n + bi because if at some indexes if both ai and bi are N then it can overshoot N^2 isn't the size of array should be (N^2+N) both for upper bound?? Correct me where I am wrong I m confused in it..

The easiest thing to do is subtract one to convert $$$[1, n]$$$ to $$$[0, n)$$$, but making the array go up to $$$n^2 + n$$$ is also fine.

Lokesh_27

neal In Problem D Can you please explain why j is made to move from N-1 to 0 and not from 0 to N-1?

Thanks in Advance!!

Kevin114514

← Rev. 2 →

Deleted

spookywooky

Obviously the algorythm works the same if going from left to right, it is just a choice.

Lezendary_sandwich

The problem can easily be done in O(n) space complexity

Sorry, I understood only the ones I solved anyway.

D, what is "we loop over j" here, and what are "pairs coming after j"?

E, I tried to implement something similar, solving for segemnts. I still do not get how we take minimum here, minimum of what?

+11

D: updated the description to try to make it clearer.

E: we are taking $$$a_m$$$ as the minimum element of the array $$$a$$$.

clyring

+16

Interesting! I have independently reconstructed the Aho-Corasick DFA in the past but did not know its name. My solution to problem F is superficially very different, using a bitmask-DP, but I expect that the reachable bitmasks are nearly in one-to-one correspondence with the states of the Aho-Corasick DFA. The $$$k$$$-th bit in a mask corresponds to whether or not there exists a substring ending at the current position with sum $$$k$$$ and no internal substring with a proper factor of $$$x$$$ as its sum.

The transitions can be performed fairly easily and quickly for any fixed $$$x$$$ using bitwise operators and a pre-computed mask describing the factors of $$$x$$$ without knowing anything about the trie. See 91004935 for a not-very-clean implementation of this idea. Since no two consecutive bits are set in any accessible mask (since 1 is a factor of $$$x$$$) and since the least-significant bit was always set, I estimated the worst-case number of accessible states was at most $$$F_{19} = 4191$$$, also for $$$x = 19$$$.

black_trees

+23

Actually, the question 1400E is the same as question 448C.

You can use 448C's code to pass question 1400E.

expect2004

Unfortunately, they are not same.

I just submit 448C's code and got Accepted during contest. However, I was hacked by FelixArg with the data below

1
0

NewAccelWorld

This is because of a tiny difference in the constraint.

For 448C, the lower bound of values in the array is 1, whereas for 1400E the lower bound is 0.

It depends whether your code handles this corner case.

You are right.

My submissions can Accepted 1400E and 448C lol.

but I didn't submit 448C's code to pass 1400E. :)

tcapeta

← Rev. 4 →

upd:done

arjunbangari

For a segment, you are reducing each element by the minimum but adding only 1 to the answer whereas the minimum value should be added to the answer ( Read statement of operation 1 carefully ) . Also you are not considering cases like 10 10 10, you will add 10 to the answer, but the optimal answer is 3 as in one move you can make any one element zero by operation 2.

Mr.Doap

Here you even have to use the operation 2 to make any number 0. Have you considered that?

ThinkB4ChangingHandle

Can someone please explain me the nlogn approach for the problem E? I solved it in O(n^2) after the contest. I did not understand the nlogn approach in the editorial.

abdstar

Thanks for the editorial :)

AB.devil

+29

Other solution of A — Just take nth character n times.

Clix

+12

Um the problem E was in this contests. https://codeforces.me/problemset/problem/448/C

However I submitted 448C's code, only to be hacked by FelixArg with the data below

yes the only difference was 0 <= ai <= 1e9 in this problem.

I can't agree more.

However, the only difference makes it possible for the multiset to be empty in the very beginning. In the case, my programme may print 1 instead of 0.

Lain

+30

For D, there's another way with DP (though it barely fits under memory limit). Consider this separate question — given a string, find the number of subsequences of the form "abab". This can be solved in $$$O(n^2)$$$ with $$$dp_{a,b,len}$$$ , where $$$len$$$ is the length of the subsequence so far — 0 if $$$a$$$, 1 if $$$ab$$$, 2 if $$$aba$$$, and 3 if $$$abab$$$

See this submission

Dragonado

I had to stare at your code for a good 10 minutes to understand the DP transitions. You're a genius.

dytto

i spent 30 min still don't get it.. could you please explain it?

Bit tough to explain in words, but I'll try my best.

The outer loop iterates over all the array elements. Let a[j] be $$$val$$$. In a subsequence of type "abab", $$$val$$$ could be either $$$a$$$ or $$$b$$$. We need to consider both cases.

First, let us consider the case where it is $$$a$$$. One possibility is this is just the first element of our subsequence — so dp[val][i][0] needs to be incremented for all possible i. since any of them could become our $$$b$$$. The other possibility is that this is the third element. Now, let us check — how many subsequences of type "ab" have I found already? That's dp[val][i][1]! So let us add that to dp[val][i][2]

Next, we consider the case where it is $$$b$$$. I'll leave that to you, it should be clear from the previous discussion. The reason it can be confusing is the order in which I made the updates is a bit weird — this is because $$$a$$$ can be equal to $$$b$$$. This update order makes sure we don't count things multiple times.

Something else is that the answer will be the sum od dp[i][j][3] for all i and j. But you can't do that because of the memory limits, so we can just add directly to the answer.

coder_nik

Could you please explain what is dp[i][j][k] store??

It stores the number of subsequences of type "ijij" of length k+1. As in, k = 0 stores the number of subsequences of length 1 which would just be "i", k = 1 stores number of subsequences of length 2 which would just be "ij", etc.

runoxinabox

Awesome solution! and thanks for sharing.

Do you think there is a way to implement this type of DP recursively rather than iteratively? Just trying to gain some more intuition on this sort of DP method.

an0nmy0us

https://codeforces.me/contest/1400/submission/90939112 can anyone please tell why this is wrong?

also in C I used logic that if s.i-x!=s.i+x then its impossible else i tried to make ans greedily https://codeforces.me/contest/1400/submission/90955591 but it is giving wrong ans

Thank you in advance

Jyunpp

I also confused at first in Problem C but point is that given string is s.(result of process, not w) so your greedy logic's counter example (x=1) here

w : 1101011 <- original

s : 1110111 <- result of process, you are given this with x=1

when i==2, s.i-x != s.i+x (each values are 1, 0)

but w is 1101011, possible

Dontgiveup20

https://codeforces.me/contest/1400/submission/90948235 can someone help me to find why I am getting WA in this

MinusRatingPhobia

+10

I think B and C should have been swapped.

FreshP_0325

I couldn't agree anymore. I took much more time to solve problem B.

guru_bhai

can anybody elaborate more on B, it would be really helpful , thankyou.

I_will_come_back

we have two bags A and B of capacity p and f respectively now we go to store we have cnts swords of weight s units each and cntw war axe weight w units each now we have to take maximum amunt of weapons in our bags....

My approach is same as given in editorial:-

At first let us iterate over no of sword we can take(0 to cnts) then for each iteration(suppose i = 3) so we are left with p-i*s unit capacity of our bag so we can take min(cntw,p/w) units of war axe.(in this way our Bag A will be filled)

now we are left with Bag B which has f units so first check which of swords and war axe has less weight(because if we take less weight things our bag will be filled with max weapon consuming less space)

suppose s<=w:-

fill the bag B with min(cnts,f/s) and decrease f by min(cnts,f/s)*s then add no of war axe we can take which is min(cntw,f/w)

so this will be your ans for each iteration then print he max answer for each iteration.

for more clarity you can see my solution:- https://codeforces.me/contest/1400/submission/91020704

sorry for bad english.

Edit :- also you have to decrease the counts as per steps

7_dots

Problem A. If I output from 0 to n-1 of string s why is it getting wa?

naeem4265

10100

for this case you print 101 but substring 010 there is no similar

Whiplash99

My idea is a bit different for A and D.

For A, notice that $$$s[n]$$$ is present in all the substrings. So, we can just set all the characters of $$$w$$$ to $$$s[n]$$$. Code.

For D, we can iterate over all $$$j$$$'s and all $$$k$$$'s. We iterate over $$$j$$$ from left to right, and for each $$$j$$$, we iterate over $$$k$$$ from $$$N$$$ to $$$j+1$$$, like two pointers. We maintain two frequency arrays, one for $$$i$$$ and one for $$$l$$$. Let's call the frequency array for $$$i$$$, $$$left$$$, and for $$$l$$$, $$$right$$$. Each time we shift $$$j$$$ to the right, we increment the count of $$$a[j]$$$ in our frequency array: $$$left[a[j]]$$$++. Each time we shift $$$k$$$ to the left, we increment the count of $$$a[k]$$$ in our frequency array: $$$right[a[k]]$$$++. Finally, for any pair $$$(j,k)$$$, its contribution to the answer will be $$$left[a[k]]*right[a[j]]$$$. Code.

decoder__

Splendid explanation !! In case anyone needs help in the c++ code https://codeforces.me/contest/1400/submission/91027103

_runtimeTerror_

Yes , in D it is extremely simple to iterate over j and k and the rest is div2 B level problem .

← Rev. 3 →

**left[a[k]]∗right[a[j]] ** can you please explain how contribution will be this?

edit:- i get it .. thankyou for great approach!

For each $$$a[j]$$$ and $$$a[k]$$$, $$$j<k$$$, we need to find the number positions $$$i$$$ and the number of positions $$$l$$$, such that $$$i<j$$$, $$$k<l$$$ and $$$a[i]=a[k]$$$ and $$$a[j]=a[l]$$$.

Then, for each pair $$$(j,k)$$$, the total number of valid pairs $$$(i,l)$$$ which satisfy the condition will be the count of such positions $$$i$$$, multiplied the count of such positions $$$l$$$, as each of those valid $$$i$$$'s can be paired with each of those valid $$$l$$$'s and vice versa.

$$$left[a[k]]$$$ stores the number of times $$$a[k]$$$ has appeared to the left of $$$j$$$, as $$$a[i]$$$ needs to be equal to $$$a[k]$$$, while $$$right[a[j]]$$$ stores the number of times $$$a[j]$$$ has appeared to the right of $$$k$$$, as $$$a[l]$$$ needs to be equal to $$$a[j]$$$.

okay okay, thankyou!

r57shell

I did almost the same. Instead of keeping left and right I just made 2D dp preprocessing, which is basically prefix sums for each i. dp[i][j] is how many times value a[i] was appeared up to position j. 90946281 This preprocessing is additional $$$O(n^2)$$$ but solution is already $$$O(n^2)$$$ then why not? :) Also, notice that it actually works for any a[i] and it doesn't need coordinate compression if a[i] was bigger (:

pinkman7009

Does anyone have a binary search solution for problem B?

gupta_samarth

I don't see how binary search works directly. One way to do it is, iterate over number of swords you take, and then the problem is converted to "maximum number 1 person can carry", and for 1 person case, you can use ternary search.

moo.

Well I guess you can change the blog name to "Official Editorial" now :D

TheLethalCode

I have a different approach for problem G (though wasn't able to solve it during the contest), which uses Inclusion-Exclusion.It isn't hard to find for each $$$i$$$ in $$$[1,n]$$$, the number of people who are willing to form teams of size $$$i$$$. Lets call this $$$P_i$$$. From this we can calculate the number of teams that can be formed as $$$\sum_{i = 1}^n {P_i \choose i} $$$ when there are no fights between mercenaries.

But when there are fights we want to exclude certain teams we choose. This can be done by Inclusion-Exclusion. Iterate over a bitmask of size of $$$m$$$ and consider that we have a team which includes all the pairs of fights whose corresponding bits have been set. We can find the range of the sizes of the team so formed, and let's call this, $$$l_{mask}$$$ and $$$r_{mask}$$$. Now to include/exclude such teams formed, we just add/subtract $$$\sum_{i = l_{mask}}^{r_{mask}} {{P_i - x} \choose {i - x}} $$$, where $$$x$$$ is the number of people we have in the fights we are considering. Since $$$x$$$ can only be upto $$$2m$$$, its easy to precompute these values as prefix sums. Here is my code.

Mcayitel

Your way explaining is so simple and covers different approaches.

Simple, short and to the point explanation!

AllThingsWillPassAway

trash pretest and trash me

poonam__agrawal

can anyone please tell me what is wrong in this https://codeforces.me/contest/1400/submission/91026040

shuba400

if((i-k>=0) &&(i+k<n))
{
    if((ap[i+k]=='0')&& (ap[i-k]=='0'))
	      {
	           f=-1;
	           break;
	       }
}

This paritcular line seems wrong to me. try to change if((ap[i+k]=='0')&& (ap[i-k]=='0')) to if((ap[i+k]=='0') || (ap[i-k]=='0')) Because we need to check only if any one of the value is 0 or not. But your code seems to be printing -1 only if both are -1

	            if((i+k>=n)&& (i-k<0))
	            ap[i]='0';

Also why did you do this???

Problem-D

https://codeforces.me/contest/1400/submission/91027517

Can someone please tell me why is this getting WA.

My approach — Store the frequency of each element upto a particular index i and also store the index of that element. Then iterate over the indexes of each element

Our main objective is to count number of tuples (i,j,k,l). So consider the index we are iterating over as k.

Then for each element we need to calculate the number of (i,j,l).

For calculating number of valid l, I just need to know the number of elements after our working indexes.(Which can be calculated from the frequency array that I have created).

As for number of(i,j) pairs, I am using dp to calculate those and than multiplying both number of pair(i,j) and (l) and then update the answer

But I am not able to understand why is this approach giving WA on test case 2

john.pl

For problem F, I know how Aho-Corasik works, but can't figure out how to apply dp, can someone help me??

no_life_

Can someone help me with problem D. Why my code is wrong (it's gving WA for sample test case)

chenreddy

If it's wrong for the sample testcase, add print statements and debug it.

ritikagupta8734

What is the problem with my approach to Question B : 90956692 Can someone help?

seniLogik

I think you better see the test case by yourself , and reflect from that.

a_r_d

It is mentioned that solution of D using map will be slow. It gives TLE at test case 26. But the complexity of the solution seems to be $$$n^2logn$$$ which should be sufficient for 2 second time limit. What is the reason for TLE using map?

https://codeforces.me/contest/1400/submission/91036632

streaker_rules

How can I confirm that solution for B is right, Yeah I know it's greedy but there should be a POC for that.

Praxidike

can you please explain why you are calculating minimum — outside in problem E:)

See https://codeforces.me/blog/entry/81916?#comment-687022

d-agrawal

Thank you for this unofficial editorial!

AjaySabarish

Thanks for the wonderful explanation, neal but in Problem E, can you please explain the significance out the "outside" variable in your code and why are we subtracting it? 90999997

If you analyze the solution, by the time we call solve(first, last), we have already subtracted max(A[first - 1], A[last + 1]) from the subarray, which is why we compute that.

Alternatively, we could just pass in outside to the function (and switch to half-open intervals) like this: 91063322

thanks got it now, but why should we take half open intervals?

Half-open intervals are just generally nicer to code and think about.

thanks

Monazo1997

Did anyone use the idea explained in EDU — Segment Tree — Problem 3D? It is not the fastest solution, it is $$$O(n^2 . log n)$$$ but it became very useful to me. Thanks Codeforces for everything!

TamimEhsan

For problem D we can also solve it with prefix sum array where the occurences will be saved. At first we will create prefix sum array for all the elements from 1 to n. Time complexity will be O(n^2) Suppose we have a tuple 1,3,1,3 (ai,aj,ak,al) We will iterate j from 0 to n and k from i+1 to n and set aj and ak as the jth and kth index respectively. Thus we need to find the number of occurences of ak before j and number of aj after k which can be done via prefix sum array.

thewolf

In Problem F, what is the worst case string which has about 2400 x-prime substrings for x = 19?

No no, you're misunderstanding. There are only about 2400 different x-prime strings possible for x = 19.

Ahh.. I totally misunderstood, I see it now. Thanks for the reply and the editorial!

Brutevision

Thankyou so much neal.It took me an hour to understand the approach and implementation of Problem-D. Worth it.

udayan14

In question E, padding the array with 0s was very clever. I was thinking of passing the current minimum value as an argument, but this looks better. I knew the idea but struggled to implement it during the contest.

sumit_gaurav

I have tried to make editorial for this round . Language for communication : Hindi

code in c++

A — https://www.youtube.com/watch?v=e9pfuRz54cY&t=7s | English

B- https://www.youtube.com/watch?v=nm93QSZqvUM | English

C — https://www.youtube.com/watch?v=M6DRvxN7s-o. |Hindi

D — https://www.youtube.com/watch?v=jeX_1lNK6UA | Hindi

E — for now it is still in process ;-)

shubhanshushekharp

Very nice video!!!

Thanks!

encountered

Nice editorials bro. Keep it up.

Thanks! :-)

-12

I solved 1400E - Clear the Multiset with dp in $$$O(n^2)$$$. I thought someone described it already but no. I don't see

Idea is simple. Notice that without second action it's just sum of max of difference and 0. Why? Well, because it's similar to brackets depth. So, how second type may help to do it better? It may help to decrease some spikes/hills in less steps. Also notice that you don't need to apply twice second type of action on same position. This means that actually for any position there is: either we use second type, or we don't. Assume there is optimal solution. For any position where it wasn't use second type of action there is uniquely defined previous position of same kind (position where wasn't used second type of action). But this also means that all of positions between were using second type of action. This leads to dp. dp[pos] will tell how many actions of both types you need to make non-decreasing sequence up to pos without touching value at position pos. To calculate dp[pos] you need to try make it from each i < pos using greedy strategy for values between i and pos. it's just take minimum, sum, and difference. Minimum calculated based on idea that you may go backwards from pos and maintain minimum on this subarray. 90985209

I would like to know why downvotes.

utr491

Very nice explanation! Maybe you got so many downvotes because the first sentence reflects some arrogance but again you are CM so maybe you have the right to be arrogant. Thanks for the explanation though. The best one among all I read for this question and the fence painting one. Thanks!

Can you explain in details why it does feel arrogant? Because I thought I said that I didn't see anyone that described similar solution. Is thinking that someone should have already described it — arrogant? Well, I said this because of my experience. Most of time I want to share my solution and it's already described by someone else.

I decided to put more effort into much more detailed explanation of this solution. Here we go.

More details

First, consider task without second type of action. Here is approach that sounds like what I described:

This works because of following analogy with brackets:

        ()
       (-)
   ()  (-)
   (-----)
  (-------)
 (---------)
 124 3 56 21 // height (or brackets depth)

Each difference is number of opened brackets. We take maximum with 0 to avoid counting of closing brackets. But actually, my solution using opposite difference instead. So differences would be number of closing brackets:

Now, to get idea, we need to understand what partial sum is. Partial sum here is how many actions you need to make sequence non-decreasing up to certain position. For example, first 0 0 0 1 differences tells us how to make 0 1 2 3 3. And another example 0 0 0 1 0 0 tells us how to make 0 1 2 3 3 5 6 sequence. And last example 0 0 0 1 0 0 4 sum gives us answer how to make 0 1 2 2 2 2 2.

Now, back to second actions. We will make non-decreasing sequence with help of second actions. As I described in brief explanation: for any answer there is uniquely defined position of previous place where we didn't use second action. This means we know height of it. So we know two heights a[j] and a[i] (where j < i) and also we know that we do i-j-1 of second type actions. If a[j] < a[i] then by second type of actions we can reduce everything in this segment to be a[j]. In this way we will have non-decreasing from a[j] to a[i]. Except... if there is something that less than a[j]. So we need to take minimum on this segment. Then, we have to close brackets from a[j] down to this minimum. Then, we have to reopen them up to a[j]. But we don't count openning brackets. Therefore cost of type one actions is a[i] — min. Similarly if a[j] > a[i] then we have to close all brackets down to a[i] plus we may need to close more if there is something less than a[i]. So again we need to take minimum. And again a[j] — min type one actions we need. In both cases we also do i-j-1 type two actions. In this way we get how many actions we need to get non-decreasing sequence up to pos. Answer is obviously dp at position of ending virtual zero. (to avoid writing additional code)

Rishi_Kant

Please help me in C. Here is my solution 91134362. Please tell me where I did mistake.

Now that the contest is over, it shows the reason your solution failed. At first glance it seems that you didn't check if j-x is greater than 0.

neal 1400E - Clear the Multiset solution without proof in editorial is trend nowadays? It's starting to get annoying. I did solve it in other way with proof of my solution, so at least I'm sure that both solutions give same answers on system tests. But I still don't think it's ok.

Hi, regarding problem E, I am unable to understand why the order of operations does not matter. Can you(or somebody else) please elaborate on that? Nevermind. Got it.

tiktak2

How to solve B if 'cnts' and 'cntw' are infinity?

-7

only choose elements with less weight

that is if swards are lighter only choose sward else axes.

tiagonapoli

Hey neal, did you manage to prove the claim on the editorial for problem E? The claim makes much sense, but I'm struggling to prove it

SarthakBansal

Honestly, Problem D is one of the most finely crafted Problems I've seen. Absolutely loved it!

parveen1981

My idea for Problem D if anyone interested:
Maintain frequency index vector for each integer from $$$1$$$ to $$$n$$$. Now let's say we want to find out number of pairs for $$$x$$$ and $$$y$$$. Let's say
$$$freq[x]= k_1, k_2, k_3, ...$$$
$$$freq[y]= l_1, l_2, l_3, ...$$$
Here $$$k_i$$$ is the index where $$$x$$$ occur and similarly for y. We want to merge these two lists and while merging we will maintain a string/array which consists of $$$0's$$$ and $$$1's$$$. We will put $$$0$$$ if we are taking from $$$x$$$ and $$$1$$$ if we are taking from $$$y$$$. Now the problem remains is as follows: We are given a string consisting of $$$0's$$$ and $$$1's$$$, we need to find number of subsequences of type $$$0101$$$ and $$$1010$$$ in this string which can be calculated with dp. Also, we can handle the case for same number (say $$$x$$$) separately. See my submission.

3 years ago, # |

My proof for problem E

ASHWANTH_K

17 months ago, # |

For problem E, will this work? First, I shall fix the number of type-2 operations, say $$$K$$$.

It's always optimal to do $$$K$$$-2nd type operation on $$$K$$$-largest numbers.
So, I removed $$$K$$$ largest number from the list and tried to find the number of type-1 operations required.
It turns out that the number of first-type operations is the maximum number in every mountain.

$$$a_i < a_{i+1} < a_{i+2} ... < a_k > a_{k+1}> a_{k+2} ..> a_j$$$ , I add $$$a_k$$$ to my answer.
So answer = $$$ min(k + \sum_{}{} a_k)$$$ for all $$$0 <= k <= N $$$

DuongForeverAlone

5 months ago, # |

I know the blog has been published a long time ago, I still want to give out a little more of details in problem F for people who try to upsolve it at the moment.

Denote $$$dp[i][u]$$$ as the minimum number of character you need to erase if you are at the position $$$i$$$, and standing at node $$$u$$$ of the trie. Before any transition, make sure the current node $$$u$$$ is not a terminal node of the trie (the leaf node, or the last character of a string in the trie), otherwise the current state form a x-string. For the transition to the next character ($$$i$$$ to $$$i + 1$$$), there are two possibilities:

Erase the $$$(i + 1)$$$ th character. In this case, the state $$$(i, u)$$$ will be transited to $$$(i + 1, u)$$$, because we will stay at the current node after erasing. Then $$$dp[i + 1][u] = min(dp[i + 1][u], dp[i][u] + 1)$$$ (adding one here because we perform the erase operation).
Not erase the $$$(i + 1)$$$ th character. In this case, the state $$$(i, u)$$$ will be transited to $$$(i + 1, v)$$$, where $$$v$$$ is the next node in the trie after we use the edge $$$s_{i + 1}$$$ ($$$s$$$ is the initial string). If $$$v$$$ is not a terminal node, then $$$dp[i][v] = min(dp[i][v], dp[i][u])$$$.

Hopefully this will help.

WizzyRocky

5 weeks ago, # |

Problem E is the same problem as 448C - Painting Fence with rating 1900