### awoo's blog

By awoo, history, 3 months ago, translation,

1969A - Two Friends

Idea: BledDest

Tutorial
Solution (awoo)

1969B - Shifts and Sorting

Idea: BledDest

Tutorial

1969C - Minimizing the Sum

Idea: BledDest

Tutorial
Solution (Neon)

1969D - Shop Game

Idea: BledDest

Tutorial
Solution (Neon)

1969E - Unique Array

Idea: BledDest

Tutorial
Solution (Neon)

1969F - Card Pairing

Idea: BledDest

Tutorial
Solution (BledDest)
• +66

 » 3 months ago, # |   0 Good editorial, but for problem C I have a question, If we increase K to a number M. Which is the maximum value that M can achieve auch that there exist a solution that fits in 5 seconds?
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 "there exist a solution that fits in 5 seconds" is a rather vague requirement imo, since it depends on many factors outside of your own codes (i.e. OS and hardware).As far as we keep on the $\mathcal{O}(nk^2)$ as benchmarking, and assuming using my own solution which ran in 0.3s (rounded down for simplicity), we could reach a $k$ of about $\lfloor {10 \times \sqrt{\frac{5}{0.3}}} \rfloor = 40$.Of course 0.3s might not be the fastest $\mathcal{O}(nk^2)$ solution out there. If benchmarking using other faster ones, resulting $k$ might be slightly bigger (not too much, since the complexity relates to $k$ quadratically). Also this estimation is rather rough due to various constant factor not yet addressed in the time complexity.
 » 3 months ago, # |   0 I think I have another solution for D: 258763428But, I am not sure why it works :)
•  » » 6 weeks ago, # ^ |   0 helpfull
 » 3 months ago, # |   0 About problem F: How do you handle the case, when the deck becomes empty and we still have duplicate cards on the hand? How do you choose the pair to go with?
•  » » 3 months ago, # ^ |   +1 This is handled by the fact that the dynamic programming stores the number of pairs we "broke" instead of the number of pairs we made, and it is subtracted from the number of pairs we can make from a sequence of cards in the best case scenario (i. e. if we could pair any two cards without having both of them in hand at the same time). The value in dp increases by $1$ every time we play a non-paired card such that the remaining number of cards of that type is odd, since it means that the number of pairs we could possibly make with that type of card decreases by $1$.So, the pairs that are left in our hand after we've drawn the whole deck are simply not counted as "broken", we don't subtract them from the number of possible pairs we can make.
 » 3 months ago, # | ← Rev. 3 →   +1 Mad respect to everyone who went for $\mathcal{O}(n^2)$ in Problem F
•  » » 3 months ago, # ^ |   0 Actually, assume that $dp[i]=dp[j]+?$ , we can find that $j$ corresponds to at most one $(x,y)$ (the kinds we delete). To find all the $(x,y)$, we may use a queue to simulate the process, thus it runs in $O(n^2)$.see my code: 259118010
 » 3 months ago, # |   +1 How is O(N^3) fast enough for problem F, given you have N = 1000 possibly?
•  » » 3 months ago, # ^ | ← Rev. 2 →   +8 Although $N \leq 1000$, we pick out two cards at a time. So, the "actual" $N$ is actually 500. Though, in general, a low-constant $\mathcal{O}(N^3)$ should be fast enough for $N=1000$
 » 3 months ago, # |   +3 In problem D, for a fixed set of alice's items, isn't it better for bob to take items' that profits Alice the most ? ( the one with bigger $B[i]$ — $A[i]$ )
•  » » 3 months ago, # ^ |   0 No, Alice has already paid for these item, Bob can only take k free items and take the rest from Alice. So Bob takes k items with the max b value.
•  » » » 3 months ago, # ^ |   0 Just want to make sure. The solution basically boils down iterating through all divide points where we will take and also minimizing $K$ elements from the left side to be given freely to Bob and finding all "profit" element from the right side of the element?
•  » » » » 3 months ago, # ^ | ← Rev. 3 →   +1 Yes. But you can ignore all items where a[i]>=b[i], as these items will always make Alice lose profit.If with item i, a[i] >= b[i], i in the item Bob will pay Alice, then profit of item i is b[i]-a[i]<=0, so do not include item i.If number of items with a[i] < b[i] is less than k, then Alice won't buy anything.If we already have k items, each with a[i] < b[i] and Bob will get them free, if we need to include item i in the list of free item, then an item j will be removed. We have a[j] < b[j] <= b[i] <= a[i], so a[j] < a[i] and the cost Alice will have to pay will increase.
•  » » » » » 3 months ago, # ^ |   0 My solution got WA. Do you mind to see my solution? 258978737
•  » » » » » » 3 months ago, # ^ |   0 You missed checking result when i+1==k  for(int i = 0 ; i < n;i++){ if(i + 1 <= k){ // the element on the left side is atmost only K element pq.push(vpi[i].second); sumLeft += vpi[i].second; // add the missing case i+1==k if (i+1==k){ ans = max(ans,suffixSum[i+1]-sumLeft); } }else{ sumLeft += vpi[i].second; // insert the new element pq.push(vpi[i].second); sumLeft -= pq.top(); // delete the biggest element pq.pop(); int sumRight = suffixSum[i+1]; ans = max(ans,sumRight-sumLeft); } } 
•  » » » » » » » 3 months ago, # ^ |   0 Oh ya I forgot to consider that. Thank youu!!
 » 3 months ago, # |   0 Hi,any non DP solution for problem C?
 » 3 months ago, # |   0 Problem E can be solved using monotonic stack.We maintain a stack with item is (nexti, seen_values), nexti decreasing. Traverse from left to right.nexti is the index that if reaching, will create a subarray with no unique elements. seen_values is the set of elements in the subarray.https://mirror.codeforces.com/contest/1969/submission/258961901
•  » » 3 months ago, # ^ |   0 Can you expand on it a bit more? seems interesting...
•  » » » 3 months ago, # ^ |   0 Solution in C++https://mirror.codeforces.com/contest/1969/submission/258986735Somehow the C++ version gives TLE, even though it's the same as Go version.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +3 There is a similar idea, but instead of using seen_values to check if the element is already encountered, here use previous index to check, and stack item is (start, end)The time complexity is O(n) https://mirror.codeforces.com/contest/1969/submission/258805932
 » 3 months ago, # |   +1 There is a non-greedy approach for problem E.Suppose $dp_i$ is the answer for the prefix with len $i$ if the last updated element was $i$. We wan't to do transitions like $dp_i = min_{j  » 3 months ago, # | ← Rev. 3 → 0 can anyone help me provide a clearer explanation for problem C please? How can we get the answer by using min of dp[n]. Updated: I got it now, sorry for bothering •  » » 3 months ago, # ^ | 0 It depends on your dp statements.You must have seen the tutorial$dp[i]$means if we considered the first elements and already done$j$operations,and the best answer.After considering all n elements ,we get the answer. •  » » » 3 months ago, # ^ | 0 Isn't dp[n][k] should be the minimum? •  » » » » 2 months ago, # ^ | 0 sure,it is.  » 3 months ago, # | 0 I solved$D$with dp  » 3 months ago, # | 0 In question C, if we are able to reach till i + d + 1 using d operations then why aren't we taking the minimum till that index as well?  » 3 months ago, # | 0 For me , it's hard to solved the problem C. Also , the tutorial is too short making me difficultly to understand! May be i am beginner to DP.>_<.  » 3 months ago, # | 0 In Problem C where the editorial said that the segment of length d+1 can be converted to a minimum using d steps. But what if all of the elements in the segment are equal let's say (2) then their is no need to waste any operations so wouldnt the transitions change. Why is the dp still working ?  » 2 months ago, # | ← Rev. 3 → 0 Problem F can be changed into another question.There are n points with different colors on a line,which numbered from$1$to$n$.Each time we make a segment whose endpoints have same color. What we are currently requesting is the maximum number of line segments we can make,satisfying that every point between$a_{2i}$and$a_{2i+1}$is covered no more than$k-2$times and every point between$a_{2i-1}$and$a_{2i}$is covered no more than$k-1$times.This is too much like a problem that can be solved with greed or flow.I'm still figuring out the solution.Can somebody teach me how to solve it?  » 2 months ago, # | 0 In problem B if I do the operation on index [2,5], making the cost 4 resulting string: 10001 and I do the operation on index [1,4] making the cost 8 now. resuting string:00011. this makes the cost 8 rather than 9, I dont think the answer given is write. My code is giving all other test cases right, but not this case. •  » » 2 months ago, # ^ | 0 You are supposed to put last character to first position not first character to last position. SpoilerTransformation of 1000 would be 0100 not 0001. •  » » » 2 months ago, # ^ | 0 oh yes, now I see my mistake  » 2 months ago, # | ← Rev. 2 → 0 I have a doubt in problem C why will a normal greedy solution fail in this case. Please anyone reply to this i'm not able to understand what i am getting wrong or where am i failing. So for each k i am just traversing the whole array and the swap that reduces my some the most i just do that and i do this at most k times. For reference i am attaching my solution here. 261251605 •  » » 2 months ago, # ^ | 0 I have the same question, but I have a guess:For example, consider the array [10, 1, 2, 11]. We can obtain [1, 1, 2, 11] and [10, 1, 2, 2], which, while giving the same total sum, leads to different arrays.My guess is that for some test cases where this also happens, the total sum changes after more operations on the different arrays with same sum. •  » » » 2 months ago, # ^ | ← Rev. 2 → 0 Maybe you can try 1 10 11 2, and k = 2. ->1 1 11 2 -> 1 1 1 2 -> 9+10 = 19 ->1 10 2 2 -> 1 1 2 2 -> 9+9 = 18 •  » » » » 2 months ago, # ^ | 0 Wow, it was right under my nose, thank you! •  » » » » 2 months ago, # ^ | 0 Also, if you wouldn't mind, could you do an example of the dp algorithm with the same array? I'm reading the tutorial but I'm still not getting it  » 2 months ago, # | ← Rev. 3 → 0 Problem C is very similer to atcoder dp contest problem N.Edit: No, it is not.XD  » 2 months ago, # | 0 please someone explain the solution of problem C in detail . Thank you •  » » 6 weeks ago, # ^ | ← Rev. 3 → +3 Hey, So my solution was also through dp, but a little different from the editorial. Here it is:$dp[i][j]$refers to min sum from$a[1..i]$using at most$j$operations. Now, I declare a$dp$array of size$(n+1) \times (k+1)$. (Note that I am using 1-based indexing for$a$)Initialisation:$dp[0][j] = 0 \, \forall j$(since no elements are there) and$dp[i][0] = pre[i]$, where$pre[i] = a_1 + a_2 + \dots a_i$(prefix-sum till$a_i$) [Obvious, when you can't perform any operations, the ans will be the sum simply]Transition: This is a little tricky part, but still simple to think. You can have three possibilities: Do not do any operation, i.e.,$dp[i][j] = dp[i-1][j] + a[i-1]$($a[i-1]$is to take care of my 1-based indexing) "Propagate" this last element$a_i$for some$k$steps. In simple terms, if my original array was$[a_1 , a_2, \dots ,a_i]$. It now becomes$[a_1,a_2, \dots a_{i-k-1} , a_i , \dots , a_i]$. After that I simply take$dp[i-k-1][j-k]$. So the solution in this case is$dp[i-k-1][j-k] + a[i-1]*(k+1)$(Why$k+1$? .. think). In this, step you just have to be sure that$k$doesn't exceed either$i-1$or$j$. (Again think why?) "Propagate" any$a_k$till the last element. (Obv.$i-k \le j$). Again, if the original array was$[a_1 , a_2, \dots ,a_i]$, it will now become$[a_1,a_2, \dots a_{k-1} , a_k , \dots , a_k]$. Now, after this we can simply add$dp[k][rem]$, where$rem$is the number of remaining steps. So, in this case the answer becomes$dp[i][j] = dp[k][rem] + a[k-1]*x$(Can you think why we took$dp[k][rem]$and not$dp[k-1][rem]?$). Also, think what$x$will be! And that's it! Our final solution looks like:$dp[i][j] = min(case 1,case 2,case 3)\$My submission for reference: 265745935 . Hopefully, the solution was easy to understand. If you cannot deduce any of the bracketed stuff, kindly let me know in the comments.
 » 6 weeks ago, # |   0 Good work !!
 » 4 weeks ago, # |   +3 Another Approach for problem B:we can find the first position of '1' and keep it updating once we encounter a '0' afterwards. and also keep adding substring length to answer. Solution
•  » » 4 weeks ago, # ^ |   +3 hope it will be helpful :)