neal's blog

By neal, 22 months ago,

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

• +416

 » 22 months ago, # |   0 https://codeforces.com/contest/1400/submission/90994198 , this solution just got hacked can someone help me find my mistake?
•  » » 22 months 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.
•  » » » 22 months ago, # ^ |   0 thanks a lot man.
 » 22 months ago, # |   +4 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!
•  » » 22 months ago, # ^ |   +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.
•  » » » 22 months ago, # ^ |   0 I got it, thanks a lot again!
•  » » » 22 months ago, # ^ |   +4 neal Can you explain the implementation in D 'if the ai were larger than n, we could just compress them down to [1,n]'
•  » » » » 22 months ago, # ^ |   +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]$.
•  » » » » » 22 months ago, # ^ |   0 thanks~
•  » » » » » 22 months ago, # ^ |   0 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..
•  » » » » » » 22 months ago, # ^ |   0 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.
•  » » » » » » » 22 months ago, # ^ |   0 So first we are decreasing all array element by 1??
•  » » » » » » » 22 months ago, # ^ |   0 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!!
•  » » » » » » » » 22 months ago, # ^ | ← Rev. 2 →   0 Deleted
•  » » » » » » » » » 22 months ago, # ^ |   +1 Obviously the algorythm works the same if going from left to right, it is just a choice.
•  » » » » » 22 months ago, # ^ |   0 We should use a float array in this case, right? because sometimes the numbers get mapped to a float while compressing?
•  » » » 22 months ago, # ^ |   +6 The problem can easily be done in O(n) space complexity
 » 22 months ago, # |   0 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?
•  » » 22 months ago, # ^ |   +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$.
 » 22 months ago, # | ← Rev. 2 →   +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$.
 » 22 months ago, # |   +23 Actually, the question 1400E is the same as question 448C.You can use 448C's code to pass question 1400E.:)
•  » » 22 months ago, # ^ | ← Rev. 2 →   +4 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 
•  » » » 22 months ago, # ^ |   +3 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.
•  » » » » 22 months ago, # ^ |   +8 You are right.My submissions can Accepted 1400E and 448C lol.but I didn't submit 448C's code to pass 1400E. :)
 » 22 months ago, # |   0 Can anyone please explain me why the last test case in the third question is -1.I am not getting it.
•  » » 22 months ago, # ^ |   0 Because there isn't any string possible, which can give you s=110 (x=1). Try to build the answer by taking the answer string w=111. Now according to the rules given: s[0]=1 => w[0-1](does not exist), w[0+1]=w[1]=1 (Must be 1 because other index does not exist). s[1]=1 => w[1-1]=w[0]=1 OR w[1+1]=w[2]=1. s[2]=0 => w[2-1]=w[1] != 1 (this should not be equal to one as the answer string s has 0 at i position) and w[2+1](does not exist). Now look at statement 1, and 3. 1 says that w[1] must be equal to 1, while 3 says that w[1] must not be equal to one. So no string w exists to give answer string s according to the given rules.
•  » » » 22 months ago, # ^ |   0 Thanks
 » 22 months ago, # | ← Rev. 4 →   +3 upd:done
•  » » 22 months ago, # ^ |   +1 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.
•  » » 22 months ago, # ^ |   0 Here you even have to use the operation 2 to make any number 0. Have you considered that?
•  » » 22 months ago, # ^ |   0 Here you even have to use the operation 2 to make any number 0. Have you considered that?
 » 22 months ago, # | ← Rev. 2 →   0 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.
 » 22 months ago, # |   0 Can someone tell me how to solve problem-B using binary search? Or are we using binary search along with greedy approach in the above editorial? Either way, I'm not able to gain the intuition.
 » 22 months ago, # |   +11 Thanks for the editorial :)
 » 22 months ago, # |   +29 Other solution of A — Just take nth character n times.
 » 22 months ago, # | ← Rev. 2 →   +12 Um the problem E was in this contests. https://codeforces.com/problemset/problem/448/C
•  » » 22 months ago, # ^ |   +4 However I submitted 448C's code, only to be hacked by FelixArg with the data below 1 0 
•  » » » 22 months ago, # ^ |   +3 yes the only difference was 0 <= ai <= 1e9 in this problem.
•  » » » » 22 months ago, # ^ |   0 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.
 » 22 months ago, # |   +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
•  » » 22 months ago, # ^ |   +3 I had to stare at your code for a good 10 minutes to understand the DP transitions. You're a genius.
•  » » » 22 months ago, # ^ |   0 i spent 30 min still don't get it.. could you please explain it?
•  » » » » 22 months ago, # ^ | ← Rev. 2 →   +3 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.
•  » » 22 months ago, # ^ |   0 Could you please explain what is dp[i][j][k] store??
•  » » » 22 months ago, # ^ |   0 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.
•  » » 22 months ago, # ^ |   0 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.
 » 22 months ago, # |   0 https://codeforces.com/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.com/contest/1400/submission/90955591 but it is giving wrong ansThank you in advance
•  » » 21 month(s) ago, # ^ |   0 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) herew : 1101011 <- originals : 1110111 <- result of process, you are given this with x=1when i==2, s.i-x != s.i+x (each values are 1, 0)but w is 1101011, possible
 » 22 months ago, # | ← Rev. 2 →   0 can anyone tell me where my code for problem B is failing(hidden testcase)Edit:- NVM got it
 » 22 months ago, # |   0 https://codeforces.com/contest/1400/submission/90948235 can someone help me to find why I am getting WA in this
 » 22 months ago, # |   +10 I think B and C should have been swapped.
•  » » 22 months ago, # ^ |   +1 I couldn't agree anymore. I took much more time to solve problem B.
 » 22 months ago, # |   0 can anybody elaborate more on B, it would be really helpful , thankyou.
•  » » 22 months ago, # ^ | ← Rev. 2 →   +1 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.com/contest/1400/submission/91020704sorry for bad english.Edit :- also you have to decrease the counts as per steps
•  » » » 22 months ago, # ^ |   0 okay got it, thanksalot! really appreciate the help :-))
•  » » » 22 months ago, # ^ |   0 How can we intuitively figure out that the algorithm of taking the maximum number of swords greedily is wrong? And justify that the iteration is necessary?
•  » » » » 22 months ago, # ^ |   0 We are doing iterations because we don't know whether it will be profit for us to take as many sword as we can have in our bag maybe if we take some war axe then we might get better result so this type of confusion may lead to iterative approach where we are checking for every amount of sword we take..... also this solution make many things clear to me.. Thanks I_will_come_back.
 » 22 months ago, # |   0 Problem A. If I output from 0 to n-1 of string s why is it getting wa?
•  » » 22 months ago, # ^ | ← Rev. 2 →   0 1310100for this case you print 101 but substring 010 there is no similar
 » 22 months ago, # |   +33 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.
•  » » 22 months ago, # ^ |   +4 Splendid explanation !! In case anyone needs help in the c++ code https://codeforces.com/contest/1400/submission/91027103
•  » » 22 months ago, # ^ |   0 Yes , in D it is extremely simple to iterate over j and k and the rest is div2 B level problem .
•  » » 22 months ago, # ^ | ← Rev. 3 →   +3 **left[a[k]]∗right[a[j]] ** can you please explain how contribution will be this?edit:- i get it .. thankyou for great approach!
•  » » » 22 months ago, # ^ |   0 For each $a[j]$ and $a[k]$, $j •  » » » » 22 months ago, # ^ | +3 okay okay, thankyou! •  » » 22 months ago, # ^ | 0 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 (:  » 22 months ago, # | 0 Does anyone have a binary search solution for problem B? •  » » 22 months ago, # ^ | 0 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. •  » » 22 months ago, # ^ | 0 •  » » » 22 months ago, # ^ | 0 thanks!  » 22 months ago, # | 0 Well I guess you can change the blog name to "Official Editorial" now :D  » 22 months ago, # | 0 My idea for A was to calculate no. of 1's and 0's and which ever is the maximum , print it n timesCode can be found at: https://codeforces.com/contest/1400/submission/91002140  » 22 months ago, # | 0 Hi, in problem D My idea was — loop i and k (k>i) and for each (i,k) pair i'm trying to find freq of elements in-between those — freq of elements betwn i and k and freq of elements betwn k and n (end of the array)I know this is Brute Force of N^3. But want to know my approach. Help me out. •  » » 22 months ago, # ^ | 0 This will lead to overcounting as well  » 22 months ago, # | +19 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.  » 22 months ago, # | ← Rev. 3 → +10 Your way explaining is so simple and covers different approaches.  » 22 months ago, # | +10 Simple, short and to the point explanation!  » 22 months ago, # | +1 trash pretest and trash me  » 22 months ago, # | ← Rev. 2 → 0 can anyone please tell me what is wrong in this https://codeforces.com/contest/1400/submission/91026040 •  » » 22 months ago, # ^ | ← Rev. 2 → 0 if((i-k>=0) &&(i+k=n)&& (i-k<0)) ap[i]='0'; Also why did you do this??? •  » » » 22 months ago, # ^ | 0 thanks!  » 22 months ago, # | ← Rev. 2 → 0 Problem-Dhttps://codeforces.com/contest/1400/submission/91027517Can 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 elementOur 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 answerBut I am not able to understand why is this approach giving WA on test case 2  » 22 months ago, # | 0 For problem F, I know how Aho-Corasik works, but can't figure out how to apply dp, can someone help me??  » 22 months ago, # | 0 Will there be an official editorial as well?  » 22 months ago, # | 0 @neal In problem B, what if the counts of swords and axes are huge? What will the solution be then?  » 22 months ago, # | 0 Can someone help me with problem D. Why my code is wrong (it's gving WA for sample test case) #include using namespace std; int main() { int t; cin >> t; while (t--) { int n; cin >> n; int arr[n]; for (int i=0; i> arr[i]; } int ans = 0; for (int i=0; i •  » » 22 months ago, # ^ | 0 If it's wrong for the sample testcase, add print statements and debug it. •  » » » 22 months ago, # ^ | 0 Done that already. If I fix code for test case 1, it fails for the other one. I’m confused what I’m doing wrong in the solution as I’m following what others have mentioned in the comments.  » 22 months ago, # | ← Rev. 2 → 0 What is the problem with my approach to Question B : 90956692 Can someone help? •  » » 22 months ago, # ^ | 0 I think you better see the test case by yourself , and reflect from that. •  » » » 22 months ago, # ^ | 0 Thank You @varolahhuman7 I got my mistake  » 22 months ago, # | 0 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.com/contest/1400/submission/91036632 •  » » 22 months ago, # ^ | ← Rev. 2 → 0 Deleted •  » » » 22 months ago, # ^ | 0 I have used long long everywhere with #define int long long.  » 22 months ago, # | 0 How can I confirm that solution for B is right, Yeah I know it's greedy but there should be a POC for that.  » 22 months ago, # | 0 can you please explain why you are calculating minimum — outside in problem E:) •  » » 22 months ago, # ^ | 0 •  » » » 22 months ago, # ^ | 0 Thanks:)  » 22 months ago, # | +8 Thank you for this unofficial editorial!  » 22 months ago, # | 0 anyone who did problem B using binary search? •  » » 22 months ago, # ^ | 0 From a previous comment: Here  » 22 months ago, # | 0 please somebody help me with my code for the problem C-Binary String Reconstruction. the code is running fine on the test cases but shoes wrong ans;Approach- I firstly created a string ans of same size as string s with each element to be 'a'. Then I itereate over string s and if s[i]=='0' then I put ans[i+x] ='0' (if i+x is within length of s) and ans[i-x] = '0' (if i-x is within length of s).Then I iterate over s once again ,if s[i]=='1' then if ans[i+x]='0' (if i+x is within length of s) and a[i-x]='0' then i set flag as 1; at last iterate over string ans and replace all the remaining 'a' with '1'; At last if flag=1, print -1 else print ans; https://codeforces.com/contest/1400/submission/91052214please help me out  » 22 months ago, # | 0 https://codeforces.com/contest/1400/problem/A for creating w you can just pick up odd positions char form s(1,2,3,..,2n-1) and make string w like if s=0101101 then w=0011  » 22 months ago, # | 0 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 •  » » 22 months ago, # ^ | 0 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 •  » » » 22 months ago, # ^ | 0 thanks got it now, but why should we take half open intervals? •  » » » » 22 months ago, # ^ | 0 Half-open intervals are just generally nicer to code and think about. •  » » » » » 22 months ago, # ^ | 0 thanks •  » » 22 months ago, # ^ | 0 It is parent array's minimum/previous minimum,which affects the new child array's minimum,thus should be subtracted,isn't it ?  » 22 months ago, # | 0 Does anyone have problem D python solution. BF solution is getting TLE  » 22 months ago, # | 0 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!  » 22 months ago, # | ← Rev. 3 → 0 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.  » 22 months ago, # | 0 Can anyone please tell me why my solution for problem C is invalid. Thanks!http://codeforces.com/contest/1400/submission/91075357  » 22 months ago, # | ← Rev. 9 → 0 *****************Why a O(2n) code getting TLE in problm C****************Can anyone tell me please why this submission 90966915 is showing TLE? It was accepted till final standing and after final standing I've submitted the same code in offline also & which was accepted, see here 91082748 . I can't understand whats wrong with me. advance thanks.neal •  » » 22 months ago, # ^ | 0 I copy-pasted your submission 91117140 and it ran in$1918 ms$and then I submitted it again with some comments and got TLE on test 7 91117335. Basically your code is slow because of the for loop you make to ans+='0'.Instead, using resize makes it run on$31 ms$.You got lucky that your code got accepted at all after the contest. These are minor fluctuations in judging time say ~$150ms$. Your code is basically slow.  » 22 months ago, # | ← Rev. 2 → 0 Now I wanted to generalize problem D. A few days ago I solved a question where we had to calculate all the substrings of length 2 and in a way where we can later query all the results for each pair and I came up with the following approach :- Code ll grid[10][10]; ll cc[10]; string s; cin >> s; int n = sz(s); for(int i = 0; i < n; i++) { for(int j = 0; j < 10; j++) { grid[j][s[i] - '0'] += cc[j]; } cc[s[i] - '0']++; } Now inspired by problem D from this contest, I would like to ask how would we solve if we later had to do an operation query(i, j, k, l) and get the count for the tuple (i, j, k, l), where a[i], a[j], a[k] and a[l] have values independent of each other ? Any help would be really appreciated...  » 22 months ago, # | 0 could D be done using seg tree's ?  » 22 months ago, # | 0 https://codeforces.com/contest/1400/submission/90956921 Can someone please explain that why is this code not working for C part.  » 22 months ago, # | ← Rev. 2 → 0 In Problem F, what is the worst case string which has about 2400 x-prime substrings for x = 19? •  » » 22 months ago, # ^ | +3 No no, you're misunderstanding. There are only about 2400 different x-prime strings possible for x = 19. •  » » » 22 months ago, # ^ | 0 Ahh.. I totally misunderstood, I see it now. Thanks for the reply and the editorial!  » 22 months ago, # | +10 Thankyou so much neal.It took me an hour to understand the approach and implementation of Problem-D. Worth it.  » 22 months ago, # | 0 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.  » 22 months ago, # | ← Rev. 2 → +5 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 | EnglishB- https://www.youtube.com/watch?v=nm93QSZqvUM | EnglishC — https://www.youtube.com/watch?v=M6DRvxN7s-o. |HindiE — for now it is still in process ;-) •  » » 22 months ago, # ^ | +6 Very nice video!!! •  » » » 22 months ago, # ^ | +3 Thanks! •  » » 22 months ago, # ^ | +6 Nice editorials bro. Keep it up. •  » » » 22 months ago, # ^ | +3 Thanks! :-)  » 22 months ago, # | ← Rev. 3 → -12 I solved 1400E - Clear the Multiset with dp in$O(n^2)$. I thought someone described it already but no. I don't seeIdea 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 •  » » 22 months ago, # ^ | 0 I would like to know why downvotes. •  » » » 22 months ago, # ^ | 0 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! •  » » » » 22 months ago, # ^ | 0 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. •  » » 22 months ago, # ^ | 0 I decided to put more effort into much more detailed explanation of this solution. Here we go. More detailsFirst, consider task without second type of action. Here is approach that sounds like what I described:  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 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:  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. 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)  » 22 months ago, # | 0 Please help me in C. Here is my solution 91134362. Please tell me where I did mistake. •  » » 22 months ago, # ^ | 0 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.  » 22 months ago, # | +4 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.  » 22 months ago, # | ← Rev. 2 → 0 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.  » 22 months ago, # | ← Rev. 2 → 0 In Problem E, I have used a logic similar to the editorial. I have tested with several test cases. Can't identify the error. Can someone help me here? https://codeforces.com/contest/1400/submission/91254239 I used a similar logic for Painting Fences https://codeforces.com/problemset/problem/448/C Got Accepted: https://codeforces.com/problemset/submission/448/91261876  » 22 months ago, # | +3 How to solve B if 'cnts' and 'cntw' are infinity? •  » » 22 months ago, # ^ | ← Rev. 2 → -7 only choose elements with less weightthat is if swards are lighter only choose sward else axes.  » 21 month(s) ago, # | 0 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  » 20 months ago, # | 0 Honestly, Problem D is one of the most finely crafted Problems I've seen. Absolutely loved it!  » 18 months ago, # | ← Rev. 6 → 0 Slightly different way to do D (Zigzags). Keep four arrays, onerr[N], tworr[N][N], threerr[N][N], fourr[N][N] where onerr[i] keeps track of how many elements are i so far in the array tworr[i][j] keeps track of how many times i j shows up as a subsequence so far in the array threerr[i][j] keeps track of how many times i j i shows up as a sequence so far in the array fourrr[i][j] keeps track of how many times i j i j shows up as a sequence so far in the array Then we iterate through the array, and each time we get to arr[i], we update fourr, then threerr, then tworr, and finally onerr. Two update them, we add the next; ie. for each 1<=j<=n, fourrr[j][arr[i]] += threerr[j][arr[i]]; and similarly for the others.Then we add up everything in fourr and output the sum.  » 15 months ago, # | 0 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.
 » 12 months ago, # |   0
 » 10 months ago, # | ← Rev. 2 →   0 nealIn Problem C , If we do like first we will work on overlapping range and check for i-x and i+x if they are same or notif they are , we will check for remaining ranges ie 0 to x-1 and n-x to n accordingly print anselse print -1I tried above approach but didn't got accepted . https://codeforces.com/contest/1400/submission/126777754Can anyone plz tell me why this approach is not working ??