### awoo's blog

By awoo, history, 3 weeks 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)
• +58

 » 3 weeks 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 weeks 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 weeks ago, # |   0 I think I have another solution for D: 258763428But, I am not sure why it works :)
 » 3 weeks 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 weeks 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 weeks ago, # | ← Rev. 3 →   +1 Mad respect to everyone who went for $\mathcal{O}(n^2)$ in Problem F
•  » » 3 weeks 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 weeks ago, # |   +1 How is O(N^3) fast enough for problem F, given you have N = 1000 possibly?
•  » » 3 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks ago, # ^ |   0 My solution got WA. Do you mind to see my solution? 258978737
•  » » » » » » 3 weeks 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 weeks ago, # ^ |   0 Oh ya I forgot to consider that. Thank youu!!
 » 3 weeks ago, # |   0 Hi,any non DP solution for problem C?
 » 3 weeks 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://codeforces.com/contest/1969/submission/258961901
•  » » 3 weeks ago, # ^ |   0 Can you expand on it a bit more? seems interesting...
•  » » » 3 weeks ago, # ^ |   0 Solution in C++https://codeforces.com/contest/1969/submission/258986735Somehow the C++ version gives TLE, even though it's the same as Go version.
•  » » » 3 weeks 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://codeforces.com/contest/1969/submission/258805932
 » 3 weeks 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 weeks 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 weeks 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 weeks ago, # ^ | 0 Isn't dp[n][k] should be the minimum? •  » » » » 10 days ago, # ^ | 0 sure,it is.  » 3 weeks ago, # | 0 I solved$D$with dp  » 3 weeks 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?  » 2 weeks 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.>_<.  » 2 weeks 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 ?  » 10 days 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?
 » 7 days 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.
•  » » 6 days 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.
•  » » » 5 days ago, # ^ |   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } oh yes, now I see my mistake
 » 6 days 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
•  » » 3 days 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.
•  » » » 3 days 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
•  » » » » 37 hours ago, # ^ |   0 Wow, it was right under my nose, thank you!
•  » » » » 37 hours 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
 » 3 days ago, # | ← Rev. 3 →   0 Problem C is very similer to atcoder dp contest problem N.Edit: No, it is not.XD