awoo's blog

Educational Codeforces Round 165 Editorial
By awoo, history, 2 weeks ago, translation, In English

1969A - Two Friends

Idea: BledDest

Tutorial
Solution (awoo)

1969B - Shifts and Sorting

Idea: BledDest

Tutorial
Solution (adedalic)

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)
  • Vote: I like it
  • +58
  • Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    2 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    "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.

    → Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think I have another solution for D: 258763428

But, I am not sure why it works :)

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
»
2 weeks ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

Mad respect to everyone who went for $$$\mathcal{O}(n^2)$$$ in Problem F

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

How is O(N^3) fast enough for problem F, given you have N = 1000 possibly?

→ Reply
  • »
    »
    2 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

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

    → Reply
»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        2 weeks ago, # ^ |
        ← Rev. 3   Vote: I like it +1 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          My solution got WA. Do you mind to see my solution? 258978737

          → Reply
          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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);
        }
    }
            → Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi,any non DP solution for problem C?

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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<i} dp_j + 1$$$ for good $$$j$$$, where $$$j$$$ is the position of previous update. Since we can set an element to some value which isn't in the array, we only need to care about subsegments of interval $$$(j, i)$$$. To check whether all subsegments are unique, for each $$$r$$$ we want to precalculate max $$$l$$$ such that segment $$$[l, r]$$$ is not unique. Let's call this $$$l$$$ $$$bad_r$$$.

To find $$$bad_i$$$ we want to find all unique subarrays. Turns out we can do that. Suppose element $$$i$$$ makes the subarray unique. What can we say about $$$L$$$ and $$$R$$$ (ends of segment)?

$$$prv_i < L \le i$$$, $$$i \le R < nxt_i$$$

Where $$$prv_i$$$ is the previous occurence of $$$a_i$$$ or $$$-1$$$, and $$$nxt_i$$$ is the next occurence of $$$a_i$$$ or $$$n$$$ (in zero-indexation).

So all unique segments are union of rectangles $$$(prv_i + 1, i, i + 1, nxt_i)$$$ (I define rectangles as a quadruple $$$(x1, y1, x2, y2)$$$, rectangle has all points $$$(x, y)$$$ satisfying $$$x1 \le x < x2$$$, $$$y1 \le y < y2$$$). All non-unique segments are out of this union. To find $$$bad_r$$$ we can do scanline with segment tree and for each $$$r$$$ search the right-most $$$0$$$ (or $$$-1$$$ if all values are greater than $$$0$$$).

Now our $$$dp$$$ can be reformulated as $$$dp_i = min_{bad_{i-1} \le j < i}(dp_j) + 1$$$. This can be counted using another segment tree or with monotonous stack and binary search. The answer is either $$$0$$$ when $$$bad_{n-1} = -1$$$ or minimum amongst $$$dp_i$$$ with $$$i \ge bad_{n-1}$$$

→ Reply
»
2 weeks ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Isn't dp[n][k] should be the minimum?

      → Reply
      • »
        »
        »
        »
        5 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        sure,it is.

        → Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved $$$D$$$ with dp

→ Reply
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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.>_<.

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

→ Reply
»
5 days ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
34 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are supposed to put last character to first position not first character to last position.

    Spoiler
    → Reply
»
5 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply