1689A - Lex String

Author: wxhtzdy

1689B - Mystic Permutation

Author: n0sk1ll

Riblji_Keksic found the O(n) solution.

1689C - Infected Tree

Author: n0sk1ll

1689D - Lena and Matrix

Author: n0sk1ll

1689E - ANDfinity

Author: wxhtzdy

• 20 hours ago, # ^ | Problem were really good, thanks [user:n0sk1||] and wxhtzdy and all the contributors of the contest. I was really a good contest for me.

• 21 hour(s) ago, # ^ | It's OK

• 19 hours ago, # ^ | Don't worry. I also felt that A was tougher than usual.

• 21 hour(s) ago, # ^ | what's your approach?

  • 20 hours ago, # ^ | ← Rev. 3 →   +7 You can check out my solution https://codeforces.com/contest/1689/submission/160137279 . The idea is that we can make infection infect only one vertex at a time, or non at all, If vertex is has two children, we delete one of them and make infection spread on the other child, so both child dies, this happens unless one of their child only has one child so infection can not spread at all anymore, this can happen to the root too, you just cut one source and infection can not spread at all.

• 21 hour(s) ago, # ^ | ig we can just store subtree count of every node & later add by processing in valid manner

  • 20 hours ago, # ^ | yep, but is that not already considered dp?

• 21 hour(s) ago, # ^ | we can solve c without dp.the approch is simply follow along the infected path along the binary tree using dfs/bfs,take minimum of the available infected paths and saved =(n-(infected)) my solution approch

  • 20 hours ago, # ^ | ← Rev. 2 →   0 Can anyone see why WA. 3rd Problem I'm storing the child counts in visited and then moving optimally along less children. 160139740

    • 19 hours ago, # ^ | you counter a case when the children is equal Thats the case when your approach doesn't work that's why we use dp to store both possible path and take the max

      • 19 hours ago, # ^ | Thanks very much, I was just coming to this solution too.

  • 10 hours ago, # ^ | I too have a similar approach it doesn't require dp just simple bfs and simple observation.

  • 6 hours ago, # ^ | Why do you multiply s by 2 here? mx=min(mx,(2*s)-1);

• 20 hours ago, # ^ | Yes it had much simpler solution

• 20 hours ago, # ^ | Agreed. For anyone who isn't aware, the non-DP approach is to let vv be the least deep vertex with at most one child. Then, the number of vertices that must be lost is d(v)+c(v)+1d(v)+c(v)+1, where d(v)d(v) is the depth of vv (where the root has depth 11) and c(v)c(v) is the number of children of vv.

  • 20 hours ago, # ^ | I am probably being stupid, but why is d(v) being multiplied by 2?

    • 20 hours ago, # ^ | For each two-child vertex down which the virus spreads, you lose both the child onto which the virus spreads and the other child, which you must shut down to keep the virus from spreading onto the other branch.

      • 20 hours ago, # ^ | Got it, thank you

  • 20 hours ago, # ^ | whats the proof for this?

    • 19 hours ago, # ^ | After reading Geothermal's second comment, I had to think carefully and visualize a tree that had layers of two-child vertices followed by a single- or no-child vertex. Then it became clear.

• 20 hours ago, # ^ | Yeah, brute force worked, i also submitted dp solution later ,both solutions runtime was same.

• 10 hours ago, # ^ | I don't think so there was recently a contest in which they update the rating and the editorial was out the minute contest and system testing ended. It was Instant no delay.

• 20 hours ago, # ^ | So true dude i got three RE and as soon as i saw the test case and made a little tweak it worked

• 20 hours ago, # ^ | I wasted half of my time trying to code a greedy algorithm, and only realized halfway through that it was supposed to be dp, so that was kinda sad lol.

  • 20 hours ago, # ^ | i also wasted alot of time on greedy and its implemetation,then in last 20 min all of the sudden observation came and coded it real quick and got ACed

• 21 hour(s) ago, # ^ | Fixed, sorry.

• 7 hours ago, # ^ | yes you are right

• 7 hours ago, # ^ | Why didn't you give this contest then?

  • 6 hours ago, # ^ | I gave it from another ID my friend!!

• 20 hours ago, # ^ | Nice Observation! What is cnt in your code?

  • 20 hours ago, # ^ | cnt represent that the last node has any child or not . If the last node has no child then there is no subtree connected to that node and in that case there is one less node to delete. That's why when cnt is 1(no child) the output is n-2*(ans+1)+1 which is equal to n-(ans+1)-ans and in the case where cnt is 2(has one child) the output is n-2*(ans+1)

• 20 hours ago, # ^ | I solved C absolutely the same way as you

• 76 minutes ago, # ^ | what does this part of the code do? if(sz<3){ if(dis<ans){ ans=min(ans,dis); cnt=sz; }else if(dis==ans){ cnt=min(cnt,sz); } return; }

  • 70 minutes ago, # ^ | If sz is less than 3 this means that the node has only one child or no child so the path ends here and I am just taking the minimum of all the path from root to the node having no or one child and cnt just stores that the last node has a child or not

• 20 hours ago, # ^ | Your solve function is called recursively infinite times as it is calling its parent node in some test cases like the below one. Test Case: 5 2 3 5 1 4 2 1 2

  • 19 hours ago, # ^ | Fixed , thank you ! Still , it is curious why it got MLE instead of TLE in this case.

    • 16 hours ago, # ^ | I think it would be TLE if it was an iterative loop, but recursively 3 seconds is more than enough to exceed the memory limit.

• 20 hours ago, # ^ | Perhaps they exclude the mandatory "+1" to the zeros initially

• 13 hours ago, # ^ | I'm not sure what you mean but you can make more than 1 saving move

• 10 hours ago, # ^ | ← Rev. 3 →   +15 When I tested the round, I immediately recognized the problem as one where you need to transform the coordinates in such a way that the Manhattan metric becomes the Chebyshev metric (which corresponds to rotation by 45 degrees and appropriate scaling). |x|=max{x,−x}|x|=max{x,−x} is basically why that transformation works. I was also opposed to adding this problem in the contest because 1658E - Gojou and Matrix Game is a strictly harder version of the problem.

• 19 hours ago, # ^ | ← Rev. 2 →   +3 Even just 2 dp tables are sufficient... One storing max distance of a black cell with x coordinate < i & other with x coordinate >= i for a given (i,j)

  • 13 hours ago, # ^ | ← Rev. 2 →   0 nice solution. I missed the idea of using first and last rows per column

• 19 hours ago, # ^ | From what I understand you are trying to say, your approach is correct! This is actually the same approach that Geothermal had: https://codeforces.com/submissions/Geothermal You may have had some calculation error. Here is what he had to say: "Agreed. For anyone who isn't aware, the non-DP approach is to let v be the least deep vertex with at most one child. Then, the number of vertices that must be lost is d(v)+c(v)+1, where d(v) is the depth of v (where the root has depth 1) and c(v) is the number of children of v." (Why is the depth multiplied by 2 in your code?) "For each two-child vertex down which the virus spreads, you lose both the child onto which the virus spreads and the other child, which you must shut down to keep the virus from spreading onto the other branch."

  • 19 hours ago, # ^ | and make sure you check for the path to a 0 child node as well.

• 19 hours ago, # ^ | If smallest character in s equals to smallest character in t, which should we choose?

  • 18 hours ago, # ^ | Sorry, I still dont get it, what is wrong with this submission 160146764 ?

    • 10 hours ago, # ^ | ← Rev. 2 →   0 If you take a character from string a, you are not resetting the count for the other string to 0. Assume given strings are a = "aaacdd" and b = "bcde", and k=10. Your vector ab will be then ["ddcaaa", "edcb"]. Initially, your cnt = [0,0] and ans is empty. After first three iterations, ans becomes "aaa", cnt = [3,0], and ab = ["ddc", "edcb"]. Now in fourth iteration, ans becomes "aaab" but cnt = [3,1]. It should become [0,1].

  • 9 hours ago, # ^ | Can you please check my solution if that condition is not included: comment link

• 7 hours ago, # ^ | ← Rev. 3 →   0 you can see an atcoder's problem in there. The official editorial has a detailed explanation

• 18 hours ago, # ^ | ← Rev. 3 →   0 here root 1 : left child subtree (with root 2) has the same number of vertices that can be saved by right child subtree(with root 3). so if you cut left child subtree in the end answer will equal 2 but if you cut right child subtree in the end will equal 3

  • 9 hours ago, # ^ | For same number of subtrees, I deleted the one with higher number of children

    • 6 hours ago, # ^ | here both subtree of 2 and 3 have the same number of children

1
4 4 3
aaab
aaad

1
4 4 3
aaad
aaab

correct answer: aaaaaab,
output: aaaaaad

• 19 hours ago, # ^ | ← Rev. 2 →   +11 Testcases are not weak. Read the problem A again :)

• 19 hours ago, # ^ | ← Rev. 2 →   +17 Hey, same symbol cannot appear in both strings a and b!

  • 19 hours ago, # ^ | Ah sorry

• 10 hours ago, # ^ | ← Rev. 2 →   0 Its wrong.

• 9 hours ago, # ^ |

• 13 hours ago, # ^ | Can you please explain how you used binary search I thought of doing so, searching for optimal distance but got dtucked on how to verify if the rhombus around all black points intersect at some pointfor current mid

  • 12 hours ago, # ^ | ← Rev. 2 →   0 There are four sides in rhombus. In all the cells of two opposite sides i + j remains the same and in all the cells in other two opposite sides i — j remains same where i and j are row and column number. So I divided them into two sets of ranges of two types where in first type, each range is of the form [i + j — mid, i + j + mid] and in other type, ranges are of form: [i — j — mid, i — j + mid]. Then just find the intersection of both type of ranges and iterate over every cell (i, j) to check if i + j lies in intersected range of first type of ranges and i — j lies in the intersected range of second type of ranges.

• 7 hours ago, # ^ | The regions are top-left rectangle, top-right rectangle, bottom-left rectangle and bottom-right rectangle, which are created by lines parallel with coordinate axes passing through our yellow point. I'll add this in the editorial.

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

• 7 hours ago, # ^ | Please use spoiler to write your code. Spoiler

• 7 hours ago, # ^ | you have to stop when any of the string is empty and since "a" is lexographically smaller than "aa" so its better to empty the second string first to get optimal string

  • 7 hours ago, # ^ | yaa exactly but many submissions including the editorial one gives the wrong answer as answer should be aaaaa. Correct me plz

• 7 hours ago, # ^ | ← Rev. 2 →   +3 Actually in given question same character does not appear in both strings. But lets say we allow same character to occur, then the answer in your case would be aaaaaaaaaaaaaaaaaa (9 times aa)

  • 7 hours ago, # ^ | Oh okay got it forgot to read that. Why the answer should be 9 times a we take 2 aa from string b then one a from string a and again 2 aa from string b. Now b is empty hence answer should be aaaaa. But yaa I have to read the problem more carefully

    • 7 hours ago, # ^ | Yes you are right here, lexicographically smaller string should be smaller!

• 5 hours ago, # ^ | ← Rev. 3 →   0 not only can we binary search we can solve a system of equations to get exactly an x and y that will minimize the manhattan distance! this is done by noting that the maximum distance for a number of points would be max( a-xi + b-yi, xi-a + b-yi, a-xi + yi-b, xi-a + yi-b ) where i is the ith black square then we can see that we can compute the max manhattan distance is max( a+b + max(-xi-yi), b-a + max(xi+yi), a-b + max(-xi+yi), -b-a + max(xi+yi)) to minimize the maximum manhattan distance would be the equivalent of solving a+b + max(-xi-yi) = -b-a + max(xi+yi) b-a + max(xi-yi) = a-b + max(-xi+yi) though the problem with this is that a and b are not always integers in my submission i checked the four nearest integer points ¯_(ツ)_/¯ couldn't think of a better solution https://codeforces.com/contest/1689/submission/160184723

• 5 hours ago, # ^ | Even if we have just one B all 4 cases will be covered.

  • 5 hours ago, # ^ | ← Rev. 2 →   0 I mean while checking for a certain white element, the black which we considered giving maximum or minimum for (let's say) case 3(+-) is not being in case 3 with the current white we are checking. We take a black (2,3) with min i-j = -1 (case 3). When we are checking for white at (0,0) 0-2 = -2, 0-3 = -3, it belongs to case 4. So we should have chosen a different point which could have given a good case 3 with this point Actually the solution is correct and maybe it requires some extra proof. That's what I am asking

• 5 hours ago, # ^ | ← Rev. 4 →   0 maximum 2 operations after all the 0s have been turned into 1s for example => the algorithm in general would be find maximum ai & -ai and two numbers that ai & -ai = max(ai & -ai) add 1 to one such number minus 1 from another one such number the minus 1 would become 11111110 the add one would become 10000001 since largest ai & -ai all other (ai & -ai) < max(ai & -ai) would be connected to 1111110 then 10000001 would connect to all ai & -ai == max(ai & -ai)

• 2 hours ago, # ^ | Well, that does not work. The optimal solution is not to allways choose the bigger of the two subtrees. Instead, we have to choose the one where we can stop the infection at the earliest step. That is, where the path to the first vertex with less than two childs is shortest.