Educational Codeforces Round 165 Editorial

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

1969A - Two Friends

Tutorial

Solution (awoo)

for _ in range(int(input())):
    n = int(input())
    p = [int(x) - 1 for x in input().split()]
    ans = 3
    for i in range(n):
        if p[p[i]] == i:
            ans = 2
    print(ans)

1969B - Shifts and Sorting

Idea: BledDest

Tutorial

Solution (adedalic)

fun main() {
    repeat(readln().toInt()) {
        val s = readln().map { it.code - '0'.code }
        val zeroes = s.count { it == 0 }
        val cnt = intArrayOf(0, 0)
        var ans = 0L
        for (c in s) {
            cnt[c]++
            if (c == 0)
                ans += if (cnt[1] > 0) 1 else 0
            else
                ans += (zeroes - cnt[0])
        }
        println(ans)
    }
}

1969C - Minimizing the Sum

Idea: BledDest

Tutorial

Solution (Neon)

#include <bits/stdc++.h>
 
using namespace std;

using li = long long;
const li INF = 1e18;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    vector<li> a(n);
    for (auto& x : a) cin >> x;
    vector<vector<li>> dp(n + 1, vector<li>(k + 1, INF));
    dp[0][0] = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j <= k; ++j) {
        li mn = INF;
        for (int d = 0; j + d <= k && i + d < n; ++d) {
          mn = min(mn, a[i + d]);
          dp[i + d + 1][j + d] = min(dp[i + d + 1][j + d], dp[i][j] + (d + 1) * mn);
        }
      }
    }
    cout << *min_element(dp[n].begin(), dp[n].end()) << '\n';
  }
}

1969D - Shop Game

Idea: BledDest

Tutorial

Solution (Neon)

#include <bits/stdc++.h>
 
using namespace std;

#define sz(a) int((a).size())
using li = long long;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    vector<int> a(n), b(n);
    for (auto& x : a) cin >> x;
    for (auto& x : b) cin >> x;
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
      return b[i] > b[j];
    });
    li f = 0, p = 0;
    for (int i : ord) p += max(0, b[i] - a[i]);
    li ans = 0;
    multiset<int> s;
    if (sz(s) == k) ans = max(ans, p - f);
    for (int i : ord) {
      p -= max(0, b[i] - a[i]);
      s.insert(a[i]);
      f += a[i];
      if (sz(s) > k) {
        f -= *s.rbegin();
        s.erase(--s.end());
      }
      if (sz(s) == k) ans = max(ans, p - f);
    }
    cout << ans << '\n';
  }
}

1969E - Unique Array

Idea: BledDest

Tutorial

Solution (Neon)

#include <bits/stdc++.h>
 
using namespace std;

#define sz(a) int((a).size())

vector<int> t, p;

void push(int v) {
  if (v * 2 + 2 >= sz(t)) return;
  t[v * 2 + 1] += p[v]; p[v * 2 + 1] += p[v];
  t[v * 2 + 2] += p[v]; p[v * 2 + 2] += p[v];
  p[v] = 0;
}

void upd(int v, int l, int r, int L, int R, int x) {
  if (L >= R) return;
  if (l == L && r == R) {
    t[v] += x; p[v] += x;
    return;
  }
  int m = (l + r) / 2;
  push(v);
  upd(v * 2 + 1, l, m, l, min(m, R), x);
  upd(v * 2 + 2, m, r, max(m, L), R, x);
  t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
}

int get(int v, int l, int r, int L, int R) {
  if (L >= R) return 1e9;
  if (l == L && r == R) return t[v];
  int m = (l + r) / 2;
  push(v);
  return min(
    get(v * 2 + 1, l, m, l, min(m, R)),
    get(v * 2 + 2, m, r, max(m, L), R)
  );
}

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (auto& x : a) cin >> x, --x;
  t = p = vector<int>(4 * n);
  vector<vector<int>> pos(n);
  int ans = 0, st = 0;
  for (int i = 0; i < n; ++i) {
    int x = a[i];
    pos[x].push_back(i);
    int k = sz(pos[x]);
    if (k > 0) upd(0, 0, n, st, pos[x][k - 1] + 1, +1);
    if (k > 1) upd(0, 0, n, st, pos[x][k - 2] + 1, -2);
    if (k > 2) upd(0, 0, n, st, pos[x][k - 3] + 1, +1);
    if (get(0, 0, n, st, i + 1) == 0) {
      ans += 1;
      st = i + 1;
    }
  }
  cout << ans << '\n';
}

int main() {
  int t;
  cin >> t;
  while (t--) solve();
}

1969F - Card Pairing

Idea: BledDest

Tutorial

Solution (BledDest)

#include<bits/stdc++.h>

using namespace std;

mt19937_64 rnd(12341234);

int n, k;
vector<int> deck;
vector<int> dp;
vector<vector<bool>> odd;
vector<bool> full_odd;
vector<long long> val;
vector<long long> hs;      

bool bad(const vector<bool>& v)
{
    for(int i = 0; i < k; i++)
        if(!v[i])
            return false;
    return true;
}

vector<bool> inv(const vector<bool>& v)
{
    vector<bool> res(k);
    for(int i = 0; i < k; i++)
        res[i] = !v[i];
    return res;
}

vector<bool> get_suffix(int l)
{
    vector<bool> v(k);                     
    for(int i = l; i < n; i++) v[deck[i]] = !v[deck[i]];
    return v;
}

int get_next(long long cur, int x)
{
    for(int i = x; i <= n; i += 2)
        if(hs[i] == cur)
            return i;
    return -1;
}                

int main()
{
    cin >> n >> k;
    deck.resize(n);
    for(int i = 0; i < n; i++) cin >> deck[i];
    for(int i = 0; i < n; i++) --deck[i];
    val.resize(k);
    for(int i = 0; i < k; i++)
        while(val[i] == 0)
            val[i] = rnd();

    int max_score = 0;
    dp.resize(n + 1);
    full_odd.resize(k);
    odd.resize(n + 1, vector<bool>(k));
    hs.resize(n + 1);
    long long cur_hash = 0;
    for(int i = 0; i < n; i++)
    {
        cur_hash ^= val[deck[i]];
        if(full_odd[deck[i]]) max_score++;
        full_odd[deck[i]] = !full_odd[deck[i]];
        odd[i + 1] = full_odd;
        hs[i + 1] = cur_hash;
    }   

    for(int i = k; i <= n; i++)
        dp[i] = 1e9;                          
    long long start = 0ll;
    for(int i = 0; i < k; i++) start ^= val[i];
    int pos = get_next(start, k);
    if(pos == -1)
    {
        cout << max_score << endl;  
    }
    else
    {
        dp[pos] = 0;
        int ans = 1e9;
        for(int p = k; p <= n; p += 2)
        {
            if(dp[p] > 1e8) continue;   
            vector<bool> suff = get_suffix(p);
            vector<int> o, e;
            for(int j = 0; j < k; j++)
                if(suff[j])
                    e.push_back(j);
                else
                    o.push_back(j);
            int es = e.size();
            int os = o.size();
            bool flag = true;
            for(int i = 0; i < os && flag; i++)
                for(int j = 0; j < i && flag; j++)
                {
                    int x = o[i];
                    int y = o[j];
                    int add = 0;         
                    long long h = hs[p] ^ val[x] ^ val[y];
                    int pos = get_next(h, p);
                    if(pos == -1)                  
                    {
                        flag = false;
                        ans = min(ans, dp[p] + add);
                    }
                    else
                        dp[pos] = min(dp[pos], dp[p] + add);
                }

            for(int i = 0; i < os && flag; i++)
                for(int j = 0; j < es && flag; j++)
                {
                    int x = o[i];
                    int y = e[j];
                    int add = 1;         
                    long long h = hs[p] ^ val[x] ^ val[y];
                    int pos = get_next(h, p);    
                    if(pos == -1)
                    {
                        flag = false;
                        ans = min(ans, dp[p] + add);
                    }
                    else
                        dp[pos] = min(dp[pos], dp[p] + add);
                }

            for(int i = 0; i < es && flag; i++)
                for(int j = 0; j < i && flag; j++)
                {
                    int x = e[i];
                    int y = e[j];
                    int add = 2;                             
                    long long h = hs[p] ^ val[x] ^ val[y];
                    int pos = get_next(h, p);
                    if(pos == -1)
                    {
                        flag = false;
                        ans = min(ans, dp[p] + add);
                    }
                    else
                        dp[pos] = min(dp[pos], dp[p] + add);
                }
        }
        cout << max_score - ans << endl;
    }       
}

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); } }

Comments (49)

Write comment?

Thunder8971

8 months ago, # |

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

AkiLotus

8 months ago, # ^ |

← Rev. 2 →

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

ahmetalp

I think I have another solution for D: 258763428

But, I am not sure why it works :)

throwaway6999

6 months ago, # ^ |

helpfull

Indroneel10

4 months ago, # ^ |

Why the dip in your graph?

ZergTricky

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?

BledDest

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.

AquaBlaze

← Rev. 3 →

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

ab1aze

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

theRealChainman

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

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

jonnnnnsinaga

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

nguyenquocthao00

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.

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?

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.

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

You missed checking result when i+1==k

Oh ya I forgot to consider that. Thank youu!!

nishchay_13

Hi,any non DP solution for problem C?

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

animeshz916

Can you expand on it a bit more? seems interesting...

Solution in C++
https://mirror.codeforces.com/contest/1969/submission/258986735
Somehow the C++ version gives TLE, even though it's the same as Go version.

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

Noobish_Monk

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

stonk

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

Sanae

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.

FireFlavor

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

7 months ago, # ^ |

sure,it is.

brave-kid

I solved $$$D$$$ with dp

PimpedButterfly

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?

xyw_6

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

dhamdhereshriram

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 ?

Mckenna_Grace

7 months ago, # |

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?

s.kapoor19

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.

jose_5056

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

Spoiler

oh yes, now I see my mistake

Demolisher_719

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

pedronicholas13

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.

guitarguy

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

Wow, it was right under my nose, thank you!

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

Problem C is very similer to atcoder dp contest problem N.

Edit: No, it is not.XD

Arth2022

please someone explain the solution of problem C in detail . Thank you

akshatchaudhary

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.

XeF2

6 months ago, # |

Good work !!

naman__k01

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

hope it will be helpful :)

Arnav_01

4 months ago, # |

I did not understand the solution for problem B , kindly help me . Thanks

just_average_ok

2 months ago, # |

E can be solved with xor-hashing + prefix sums.

awoo's blog