Very fast editorial. Problems were good also.

I was not even able to solve A :(

Why DP in C? It's just overcomplication, isnt it?

UPD: Idk, i just... Bruh

fastest editorial ever? nice

very fun, wish I could do more than 3

In problem C, wish there was a test case in the sample, where the input had an edge connecting from child node to parent node.

Initially I assumed that, the edges were always from parent to child, and wasted time.

I know it is my fault for making wrong assumption. But still :(.

Cool

O(n) solution for B.

The smallest possible lexicographic permutation is 1,2,3,4... Assume that this is the answer. Now just check if any element of the answer array matches with input permutation. if yes, swap it with next element. It's easy to see that no conflict would arise in this manner. There's edge case for last index, we have to swap it with previous element.

My submission- https://mirror.codeforces.com/contest/1689/submission/160104354

The problem IDs in the editorial are shown as the gym IDs (probably, some testing mashup). Please fix it.

// My solution for A:

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


void solve();
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 

    int tc;
    cin >> tc; 

    while(tc--)  
    {
        solve(); 
    }
    return 0;
}
void solve(){
    int n, m, k; cin >> n >> m >> k;
    string a, b, c = ""; cin >> a >> b; 
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    int i = 0, j = 0, turn = 0;
    if(a[i] > b[j])
    turn = 1;
    if(a[i] == b[j] && n > m)
    turn = 1;
    while(i < n && j < m)
    {
        if(turn == 0)
        {
            c += a[i]; i++;
            for(int t = 1; i<n && a[i]<=b[j] && t < k; i++, t++)
            c += a[i];
            turn = 1;
        }
        else
        {
            c += b[j]; j++;
            for(int t = 1; j<m && b[j]<=a[i] && t < k; j++, t++)
            c += b[j];
            turn = 0;
        }
    }
    cout << c << endl;
}

balanced round with good problems keep it up

cool problems and well organized overall a very good contest.thanks:)

Problem C can be solved greedily. I just find the shortest path from root to the node which have less than 2 children and infected those node and saved all other nodes by deleting the first node of every subtree connected to these infected nodes.

int ans;
int cnt;
void dfs(int i,vi &vis,int dis,vi adj[]){
    vis[i]=1;
    int sz=adj[i].size();
    if(sz<3){
        if(dis<ans){
            ans=min(ans,dis);
            cnt=sz;
        }else if(dis==ans){
            cnt=min(cnt,sz);
        }
        return;
    }
    for(auto x:adj[i]){
        if(vis[x]==0){
            dfs(x,vis,dis+1,adj);
        }
    }
}
void cases()
{
    int n;
    cin>>n;
    vi adj[n+1];
    for(int i=0;i<n-1;i++){
        int x,y;
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    if(adj[1].size()==1){
        cout<<n-2<<endl;
        return;
    }
    ans=INT_MAX;
    vi vis(n+1);
    vis[1]=1;
    cnt=3;
    for(auto x:adj[1]){
        dfs(x,vis,1,adj);
    }
    if(cnt==1)
        cout<<n-(ans+1)-ans<<endl;
    else{
        cout<<n-2*(ans+1)<<endl;
    }
}

Why is this getting MLE ?

My code for C : 160135752

The hint 3 in problem E tells that answer is 0, 1 or 2. But we have an answer 3 in the example.

Can someone please explain problem C? Since it is a binary tree there will always be at max two edges from the root node. I calculated the indegree of both and subtracted the minimum to find the max nodes which can be saved but this approach is giving wrong answer on test 3. Pls Help

https://p.ip.fi/4svQ

they didn't thought that C can be solved using DFS?

For D, another approach is to use the fact that $$$abs(x) = max(x, -x)$$$.

Let $$$S$$$ be the set of black cell, then we need to minimize: $$$max(abs(i - x) + abs(j - y))$$$ for every combination of $$$1\leq i \leq n, 1\leq j \leq m, (x, y) \in S$$$.

This is just $$$max(max(i - x, x - i) + max(j - y, y - j))$$$.

Just expand the inner $$$max$$$ and we will have 4 cases to check, similar to the official tutorial.

160104327

I think this idea ($$$abs(x) = max(x, -x)$$$) is pretty common but still very powerful, probably would have taken much more time to solve D if I didn't know it.

Problem D can also be solved by dp.
But we have to maintain 4 dp tables. One table dp[i][j] stores max distance of a black point from i,j in top left of the matrix and other tables will store for other three part of matrix which is top-right, bottom-left and bottom-right . Max distance of a point from black point will be max of the value from all four table and then we can take minimum of all these and that will be our answer .

I was thinking of applying a greedy approach for problem C, why is it not enough to find the closest path from root to leaf or a node which has just 1 children. after we find the path length we can just get the answer by (N — (x + (x-1)) + 1 ( 1 for the case if the last node found had 1 child).

What i was thinking is for every step we have two choices either remove one branch or the other, when we remove one branch we also delete a node, thus (x + (x-1)), these are the nodes removed or infected, after that just subtract this from total N.

The approach is wrong but i can;t figure out why, can someone help please?

Okay, got the error, the approach was right, the problem was i was BFS so i had to take care of the fact that if there are two nodes in which one has only one child and there is other node which does not have a child, i will go with the one which does not have a child and in that case the formula will be n-(x+(x-1)) only

$$$O(n(log(max ai))^2)$$$ solution to E.

For what purpose there was this limitation in A, that "no character is contained in both strings."?

anyone plz discuss the approach of problem D. it will be very helpful for me, why it's maximize i+j and i-j, and , minimized i+j and i-j also.

Not figuring out definitely correct (strict $$$O(nm)$$$ complexity) solution for D, but use some tricks to get it passed.

It is plausible to assume that $$$ans$$$ is close to the "center" of black cells (here I adopt $$$center=\frac{max-min}{2}$$$ for both x and y axis), then iterate over and move to adjacent cells util max Manhattan distance descend to optimum.

I'm not sure if max Manhattan distance has the same property of monotonicity as Euclidean distance (a classical problem is covering points on the plane with smallest circle). If that property holds, binary search may also work.

In problem C, can someone provide a smaller test case in which deleting the child with a higher subtree will lead to the wrong result? Thanks in advance!!

The tests for A are very weak. I can see many solution hackable. I can't see the hack button. But here is the test case:

1
4 4 3
aaab
aaad

if this works swap the strings

1
4 4 3
aaad
aaab

Example: https://mirror.codeforces.com/contest/1689/submission/160093968 :

correct answer: aaaaaab,
output: aaaaaad

UPDATE: Almost every solution is hackable. Why I can't see hack button?

1689E - ANDfinity can be optimized to $$$O(n A^2)$$$, where $$$A=\log{\max a_i}$$$
We can count $$$cnt[i][j]$$$ how many times pair of bits $$$i,j$$$ was in all $$$a_k$$$ it's works in $$$O(A^2)$$$ per element and then check if this grpah connected
To check if bit set just check $$$a[i][i] > 0$$$, if we have array $$$cnt$$$ DFS works in $$$O(A^2)$$$
So when we adding or subtracting 1 we can just update cnt we are doing it $$$O(n)$$$ times
code: 160147889

Oh! Problem D had such simple solution. But I overkilled it with binary search.

dang I was really close with D, but I wrongly thought that 4 squares shouldn't be sufficient and end up making convex hull

B was too googlable, it was simply "minimum derangement" but overall the contest was nice!

[DELETED]

Can someone explain D please. I don't understand what 4 regions is getting created

in D, As per editorial, we are selecting 4 points with different cases. Now what if you find answer to a point which is not able to belong to the correct case. I mean case1 is for both positive but is not getting achieved. explain plz?

Please tell me why my BFS code is not working on Prob C.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
using ll = long long;

#define all(a)             (a).begin(), (a).end()
#define rall(a)            (a).rbegin(), (a).rend()
#define sz(a)              (int) ((a).size())
#define pb                 push_back
#define fi                 first
#define se                 second
#define f0r(i, a, b)       for(int i = (a); i < (b); ++i)
#define f0rr(i, a, b)      for(int i = (a - 1); i >= (b); --i)
#define trav(i, v)         for(auto &i : (v))

template<class T> using V = vector<T>;
template<class T, class T1> using P = pair<T, T1>;
template<class T, class T1> using VP = vector<pair<T, T1>>;
template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
template<typename T> T pow(T a, T b) { T res = 1; f0r(i, 0, b) res = res * a; return res; }
template<typename T> void ckmax(T &a, T b) { a = max(a, b);  }
template<typename T> void ckmin(T &a, T b) { a = min(a, b);  }

int dx4[] = {0, 1, 0, -1};
int dy4[] = {1, 0, -1, 0};
int dx8[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy8[] = {-1, 0, 1, 1, 1, 0, -1, -1};

const ll linf = 1000000000000000000;
const int inf = 1000010000;
// <===================================================================================================>

vector<vector<int> > g;
vector<int> subTree, vis;

void dfs(int u) {
   vis[u] = 1;
   trav(v, g[u]) {
      if(vis[v]) continue;
      dfs(v);
      subTree[u] += subTree[v];
   }
   vis[u] = 0;
}

int main(){
   cin.tie(nullptr)->sync_with_stdio(false);

   int tt = 1;
   cin >> tt;
   f0r(T, 1, tt + 1) {
      int n;
      cin >> n;
      subTree.assign(n, 1);
      vis.assign(n, 0);
      g = vector<vector<int>> (n);
      f0r(i, 0, n - 1) {
         int u, v;
         cin >> u >> v;
         u--, v--;
         g[u].pb(v);
         g[v].pb(u);
      }
      dfs(0);
      int ans = 0;
      queue<int> que;
      que.push(0);
      while(true || !que.empty()) {
         int u = que.front();
         que.pop();
         vis[u] = 1;
         vector<int> ver;
         trav(i, g[u]) if(!vis[i]) ver.pb(i);
         if(sz(ver) == 0) break;
         if(sz(ver) == 1) {
            ans += (subTree[ver[0]] - 1);
            break;
         }
         if(subTree[ver[0]] > subTree[ver[1]]) {
            ans += (subTree[ver[0]] - 1);
            que.push(ver[1]);
         } else {
            ans += (subTree[ver[1]] - 1);
            que.push(ver[0]);
         }
      }
      cout << ans  << "\n";
   }
   return 0;
}

Prob A is not diffcult, but cost me 48 minutes to solve it, becaue I add multi characters to string c in one operation. o(╥﹏╥)o

Can someone tell me in 1689D - Lena and Matrix why taking average of leftmost and rightmost row and column (i.e. x=avg of(max row i+ min row i) and y=(max column j+ min column j) and taking all pssible value of (x,y) by taking ceil and floor value(i.e. 4 case) and checking which gives minimum distance for all black co0rdinates is giving wrong answer.(160145986). Any counter example to show this method is wrong??

I have a doubt the code given for A gives wrong answer for

1

6 4 2

aaaaaa

aaaa

given_answer:aaaaaaaa

expected:aaaaa

I was thinking that we should also consider whether string a is small or stering b at a moment when both has same smallest character. Please correct me.

The editorial's solution for problem D 1689D - Lena and Matrix may be too slow for languages like Python. I found a small speedup that allows Python code to pass the time limit.

Instead of "iterating over all squares in the matrix and finding the most distant black square", not all squares in the matrix actually need to be checked. For example, points outside the black diagonal rectangle (as shown in the editorial) clearly can't be optimal, and hence don't need to be checked.

Intuitively, points near the middle of the black diagonal rectangle have the best chance of being optimal and should be checked. I'm not sure how to prove that this is sufficient other than "Proof by AC" ;)

The time complexity is still O(nm) but maybe with a smaller constant factor.

Slow version, where all squares are checked (TLE in Python): https://mirror.codeforces.com/contest/1689/submission/160175658

Fast version, where only 4 middle squares are checked: https://mirror.codeforces.com/contest/1689/submission/160175205

A more complicated but mathematical(?) solution for D via direct analysis of manhattan distance.

First note that if any black square is between two other black squares in the same row or column then in the optimal configuration the longest distance will not be to that square. This can be shown by computing the manhattan distances to an arbitrary point directly. One of the squares on its left/right side will have greater distance. So removing those squares we have $$$O(n+m)$$$ black squares left.

Now fix some row $$$a.$$$ We find the optimal column(s) $$$b$$$ that minimize the distance for squares in this row. Thus, we want to minimize $$$\max ( |a-x_i| + |b-y_i| )$$$ for $$$b \in [1,m].$$$ Each of the $$$|a-x_i|$$$ are constants, so we have functions of the form $$$c + |x - d|.$$$ It's easy to see (by looking at the graphs) that the maximum of two such functions $$$\max(c_1 + |x - d_1|, c_2 + |x - d_2|)$$$ is another such function $$$c_3 + |x - d_3|.$$$ It follows that the function $$$f(b) = \max ( |a-x_i| + |b-y_i| )$$$ is bitonic, and we can binary search to find the optimal $$$b$$$ value(s) for this row.

Solution runs in $$$O(n^2 \log n)$$$ because for each of $$$n$$$ rows binary search takes $$$\log n$$$ and and each one we check we compute $$$O(n)$$$ numbers to find $$$f(b)$$$ at that column $$$b.$$$

163193116

In D, we are checking 4 points. But for each point we are checking, there should be 4 cases for signs. What if the points we have chosen can only make 3 sign cases and cannot make the 4th sign case. Explain please.

Hehe finally got my O(nm + number of black points) solution for problem D to work :)

just in case of a harder problem in which n = 10e9, m = 10e9, and only the black points are given

https://mirror.codeforces.com/contest/1689/submission/160184723

Can anyone explain why the maximum answer can be 2 for E?

Can someone point out my mistake in C!? What I did is: At each level of BFS, I found the node with largest number of nodes in subtrees. Added that amount to result and continue BFS with rest nodes of that level. My Solution

For 1st problem I tried a test case 1 5 5 2 aabbc aabbd The correct answer for this should be aaaabbbbc, but even their solution is giving aaaabbbbd. If someone is getting correct answer please check by reversing the string order and please correct me if a I am going wrong somewhere.

Can we do D in O(K) where K denotes the number of black squares?

I think there is an $$$O(n$$$ $$$log(max(a_i))$$$ $$$+$$$ $$$log^2(max(a_i)))$$$ solution for problem E. Details is as follows:

First of all, the current solution can be sped up to $$$O(n$$$ $$$log^2(max(a_i)))$$$ by using dynamic connectivity or creating a spanning tree which connects all the nodes for every $$$a_i$$$, updating it for every $$$+1$$$ or $$$-1$$$ operation and running DSU to check if the bits are connected. That way, the precomputation part will be $$$O(n$$$ $$$log(max(a_i)))$$$, and the checking part can be done in $$$O(log^2(max(a_i)))$$$.

For the second optimization, I claim that only checking $$$log(max(a_i))$$$ times is sufficient for us to determine whether there exists a construction for answer $$$=$$$ $$$1$$$.

First of all, we have to precompute the connectivity of the 30 bits in the given configuration (after adding $$$1$$$ to every $$$a_i$$$ $$$=$$$ $$$0$$$) using DSU. Then, we store the index of the LSB (least significant bit) of every connected component in a set (which I'll call $$$R$$$). To check answer = $$$0$$$ we simply have to check if $$$|R|$$$ $$$=$$$ $$$1$$$.

Lemma 1: $$$+1$$$ operations only work if $$$|R|$$$ $$$=$$$ $$$2$$$ and $$$min(R_i)$$$ $$$=$$$ $$$0$$$.

Lemma 2: $$$-1$$$ operations only work when LSB of current value $$$\geq$$$ $$$max(R_i)$$$ and the current component doesn't disconnect after the operation.

Lemma 3: We will find a solution after checking at most $$$log(max(a_i))$$$ distinct values that has LSB $$$\geq$$$ $$$max(R_i)$$$.

Hence, we can find the answer with overall time complexity $$$O(n$$$ $$$log(max(a_i))$$$ $$$+$$$ $$$log^2(max(a_i)))$$$. The $$$O(n$$$ $$$log(max(a_i)))$$$ is from the precomputation for the graph, and $$$O(log^2(max(a_i)))$$$ is for the queries.

Here is my implementation of the above solution. If you spot any flaws in my solution, please comment below; I would very much appreciate it. Also, sorry for my bad English ._.

Problem C can be solved using a simple preorder traversal, with only an adjacency list as extra memory. Essentially:

dfs(current, current_kill, &min_kill):
   if current has 0 child:
        min_kill = min(current_kill, min_kill);
   else if current has 1 child:
        min_kill = min(current_kill+1, min_kill);
   else:
        dfs(current.left, current_kill+2, min_kill);
        dfs(current.right, current_kill+2, min_kill); 

If the current node has no children, then the infection has reached it's end, and the current killed node count can be compared to the global min_kill count.

If the current node has one child, it can be stopped by pruning that one child. This ends the infection, and increases the kill count by 1 extra, so we compare current_kill+1 instead.

If the current node has 2 children, we will try pruning each child. This causes the child to die, and the other node to be infected, so dfs is called again with current_kill+2.

This strategy will explore every path that the infection can take and store the minimum killed nodes in a single variable.

I tried the approach of Manhattan distance and rotating technique for problem D.Many people have solved this problem by DP. Can any one please explain your DP appraoch?

Thank you in advance for helping.

n0sk1ll, How to prove the solution for B?

Is there rigorous proof for question D?

I have some questions about the solution to problem A. What if I have taken all the characters in string A but there is still more than k characters in string B?

For problem E, there exists easier way to check if graph is connected.

Repeat $$$log$$$ $$$max$$$ $$$a_i$$$ times following :

• If $$$a_0$$$ $$$\text &$$$ $$$a_i>0$$$ set $$$a_0$$$ to $$$a_0|a_i$$$

Finally if there exists some $$$a_i$$$ that $$$a_i$$$ $$$\text&$$$ $$$a_0=0$$$ then graph is disconnected.

In problem E, the check for connectivity can be done in $$$O(n \log{max(b_i)})$$$ in another way too:

Construct bipartite graph with one set of nodes corresponding to elements of the array, and one set of nodes corresponding to bits, edge exists between element $$$i$$$ and bit $$$x$$$ if $$$x$$$'th bit is set in $$$a_i$$$. Finally, just check this constructed graph.

In D you can just rotate co-ordinates in 45 Degress that makes stuff really easy

Testcases for A are weak. https://mirror.codeforces.com/contest/1689/submission/238293004 In this submission the output for 1 2 1 2 ab a The output of code-aa Actual output-a I'm not sure if the testcases can be changed now but just noticed the error so thought I should comment it.

C can be solved using PostOrder traversal. DP is overkill.

My implementation: 278017190