### awoo's blog

By awoo, history, 2 weeks ago, translation,

Idea: BledDest

Tutorial
Solution (awoo)

1976B - Increase/Decrease/Copy

Idea: BledDest

Tutorial
Solution (Neon)

1976C - Job Interview

Idea: BledDest

Tutorial
Solution (BledDest)

1976D - Invertible Bracket Sequences

Idea: BledDest

Tutorial
Solution (Neon)

1976E - Splittable Permutations

Idea: BledDest

Tutorial
Solution (BledDest)

1976F - Remove Bridges

Idea: BledDest

Tutorial
Solution (awoo)
• +97

 » 2 weeks ago, # |   0 W contest, W editorial!
 » 2 weeks ago, # |   0 Is there any way to determine the difficulty rating of recently asked contest problems? Any guidance on this would be greatly appreciated.(Any extension ?)
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   +7
•  » » » 2 weeks ago, # ^ |   +3 add : after https in the hyper link.
 » 2 weeks ago, # |   0 whats the motivation behind problem-C, i was blank after reading the problem. Any tips for such problem.
•  » » 2 weeks ago, # ^ |   0 The O(n) solution is very teidous to implement, but applying prefix sums and binary search makes it easy. So sacrifice runtime for coding time, I guess. Here's my submission for reference: 263515621
•  » » » 2 weeks ago, # ^ |   0 Can you briefly explain what exactly are you running the binary search on?
•  » » » » 2 weeks ago, # ^ |   0 Sure, I'm binary searching the last point up until it stands that there are less good programmers than N and also less good testers than M before. Here, good programmers mean candidates whose programming skill is better, and good testers mean candidates whose testing skill is better. Both of them are non-decreasing functions (the ones that tell you how many are before a point), thus binary search can be applied.
•  » » » » » 2 weeks ago, # ^ |   0 Yeah got it, but now I want to know your full solution, could you explain that as well? I still don't see how binary search can be used. I just understood some of the top submissions and implemented similarly. What I didThe main observation of their solution is that one group is always finished selecting first. Lets say programmers quota is finished first. Then what we will do is send remaining workers to test. In this configuration we calculate the net sum (note that we have employed one extra tester). We can calculate the answer for all i's when it is a tester being removed by simply subtracting b[I] from the net sum. As for removing the programmers, we would have to find a different configuration by employing n + 1 programmers this time. Then calculate net sum. Then from the initial i's when programmers were recruited, we subtract a[i] from the net sum of the second configuration.
•  » » » » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 I think it's pretty clear from the code, but I'll explain it anyways. So make 3 prefix sums, let's call them x, y and z. Let $x_{i}=x_{i-1}+max(a_{i},b_{i})$. Let $y_{i}=y_{i-1}+a_{i}$. Let $z_{i}=z_{i-1}+b_{i}$. Now take the sum until the index we searched before in $x$, because up until this point, we can decide to which team we want to assign the candidate. From this point, either everyone will get hired as a programmer or as a tester. Use $y$ and $z$ for that. Also you have to adjust your answer a bit, based on whether the candidate who didn't come is before or after the searched point. It's very similar to the solution you explained above.
•  » » » » » » » 2 weeks ago, # ^ |   +1 thanks
•  » » » » » 2 weeks ago, # ^ | ← Rev. 6 →   0 Can you tell me how can i fix my code, I feel my idea is similar. 263342854 Failing testcase is 1 0 1 1 2 2 Basically I am not able to find that point correctly through bs, where i get all programmer or tester.
•  » » » » » » 2 weeks ago, # ^ | ← Rev. 3 →   0 Hi. The problem with your code is, that you're searching for the last good point, inclusive. And the lowest possible you can get is 0. But sometimes, taking the better of the 2 skills even only at 0 will produce a bad result.Edit: Forget the last sentence I wrote in Rev. 1, I'm tired :(
•  » » » » » » » 2 weeks ago, # ^ |   0 Ok,Np auto calc_gpc = [&](ll mid) -> ll { return cum_good_p[mid + 1] - (i <= mid && A[i] > B[i]); }; ll lo = -1; ll hi = N + M + 1; while(lo + 1 < hi) { ll mid = (lo + hi) / 2; ll gpc = calc_gpc(mid); ll gtc = cum_good_t[mid + 1] - (i <= mid && A[i] < B[i]); if(gpc <= N && gtc <= M) lo = mid; else hi = mid; } bool no_more_p = calc_gpc(lo) == N; Can you just explain this part of your code. I feel I just have to calc no_more_p correctly.
•  » » » » » » » 2 weeks ago, # ^ |   +1 https://codeforces.com/contest/1976/submission/263582707 Thanks for you soln, my code worked , I have not handled corner case, for the case i am not able to get lower_bound of tester or programmer.
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 O(n) solution -> 263543487
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   0 i have a approach.instead of hiring n+m employees.hire (n+1 programmers & m testers) = set1 or hire(n programmers and m+1 testers) = set2.now compare both these new arrays you'll always notice only one index will have a change in their role, the others indexes will not have a change because it's just off by one.do prefix of both set1 and set2and iterate over each and if he's from set1 and a programmer remove him from the set1 where you hired n+1 programmers and you would have hired n+m employees or if he's a tester remove him from set2 where you hired m+1 testers and you would have hired n+m employees.
•  » » 2 weeks ago, # ^ |   +5 Problem C is much simpler when using DPhttps://codeforces.com/contest/1976/submission/263321988We use DP to calculate (i, num_programmer, num_tester): the skill of the team starting from i if we already have num_programmer and num_testerThen for each i, we calculate current_skill + dp(i+1, num_programmer, num_tester), then assign the role to candidate i and update current_skill, num_programmer, num_tester
•  » » » 2 weeks ago, # ^ |   0 What about time complexity?
•  » » » » 2 weeks ago, # ^ |   0 Time complexity is O(n)
•  » » » 2 weeks ago, # ^ |   0 nguyenquocthao00 That is very cool! But, I thought it would give, Memory limit exceeded because the n+m+1 range is up to 2*1e5 as you are having three states in dp?
•  » » » » 2 weeks ago, # ^ |   0 For this problem I use map to cache state, not array
•  » » » 8 days ago, # ^ |   0 This is great. So much cleaner than the binary-search + prefix/suffix solution I implemented.https://codeforces.com/contest/1976/submission/264856786
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   0 For problem C, I wrote a brute-force solution 263363415, but it worked magically.Let's divide what we need into two parts, if i is fixed, the left part [0, i-1], which can be calculated by simulation directly. the right part [i+1, n-1], which can also be calculated if the selected programmer pc and testers tc are known. During this progress, we cache results by tuple (i+1, pc, tc). So the solution is very simple: if the right part is cached, just use it; if not, then calculate and save in cache. I don't know why, but seems that only 2 times of brute-force is needed.
•  » » » 2 weeks ago, # ^ |   0 By caching , doesn't it exceed time complexity? Because we need to cache (n+m+1 * n * m) states. Thanks
•  » » » » 13 days ago, # ^ | ← Rev. 2 →   0 Since it's already decided which person will go where and there isn't really a choice, there wont be many values of 'n' and 'm' provided to 'i'. My logic is as follows:Compare these 2 sequences. seq_1: P T x P T i ... seq_2: P T T x T i ... where 'x' is the index excluded,'i' is the index we are currently in in the recursive process. 'n1' and 'n2' is the number of more programmers it need to take. Similarly, 'm1' and 'm2' means more testers it needs to take. Note that index 2 changed from x->T and index 3 changed from P->x. So m2 = m1-1 and n2 = n1+1, meaning in second sequence it needs to take one less tester as a previously excluded guy was appointed as a tester and also it needs to take one more programmer as a previous programmer is being excluded. For all scenarios it can be calculated. x1->T and P->x2 : n2 = n1+1, m2 = m1-1 x1->P and P->x2 : n2 = n1, m2 = m1 x1->T and T->x2 : n2 = n1, m2 = m1 x1->P and T->x2 : n2 = n1-1, m2 = m1+1 So, n2 and m2 don't seem to vary much. My submission.
 » 2 weeks ago, # |   +1 I created a blog discussing an alternate $O(n \cdot log(n))$ solution for D: Invertible Bracket Sequence. If you want to test your understanding of this conept, I also created some practice problems
 » 2 weeks ago, # |   0 Loved C
 » 2 weeks ago, # | ← Rev. 2 →   +22 Alternative DP solution to F:The problem choose the largest connected set of edges that has exactly $k$ leaves and contains the root can be solved with DP. Let $\mathrm{dp}_{i, j}$ be the answer for the subtree rooted at $i$, when taking exactly $j$ leaves. The transitions are straightforward — same as in knapsack. This gives us a $\mathcal{O}(n^2)$ solution.Notice that the sequence $(\mathrm{dp}_{i, 0}, \mathrm{dp}_{i, 1}, \dots)$ is always concave for a fixed $i$. This can be easily proven with induction — the sequence in leaves is concave, and the max-plus convolution of two concave sequences is also concave. This gives us a faster solution. Instead of storing the DP directly, store the adjacent differences (they will always be sorted in non-increasing order). Then, we can use small-to-large merging, which gives us $\mathcal{O}(n \log^2 n)$ complexity.More about max-plus convolutionSubmission
 » 2 weeks ago, # |   0 I couldn't figure out how to implement the range condition of balance[i] <= 2 * balance[l — 1] bit, later figured some people used data structures to check if the max of the range is lesser than 2 * balance[l — 1]. But I must say that the simple map implementation is the best I have seen in two days, how did you even come up with that?
 » 2 weeks ago, # | ← Rev. 2 →   0 Nice contest ! Thanks for this nice editorial
 » 2 weeks ago, # |   +1 Can someone explain why the time complexity of the solution for problem D is O(nlogn). Like how the while loop is taking logn time only. I can visualize it somehow but I can't prove it.
•  » » 2 weeks ago, # ^ |   0 The while loop isnt taking log(n) time. More like the most number of items that will be removed using the while loop is at max n summed over all of i, log(n) comes from sorting the bal[i] values because it's a map and we want to remove the smallest few "blocked" matches of potential r's.
 » 2 weeks ago, # | ← Rev. 2 →   0 Can anyone tell me why does my O(n) solution fail for problem C263511839
 » 2 weeks ago, # | ← Rev. 3 →   +11 O(n) problem D in only 24 lines#include #include using namespace std; typedef long long ll; ll bucket[200100]; int main() { int z; cin >> z; while(z--){ string s; cin >> s; ll n = s.size(), ans = 0, potential = 0; memset(bucket, 0, sizeof(ll) * (n/2 + 5)); for(ll i=0; i
•  » » 2 weeks ago, # ^ |   +1 bro explain
•  » » 2 weeks ago, # ^ |   0 Same I thinked that but unable to come up how to count it ??
 » 2 weeks ago, # |   0 In problem F, how to prove greedy is correct?
•  » » 2 weeks ago, # ^ | ← Rev. 4 →   +16 I will use the power of induction, going over the number of vertices in the tree.The base is immediately obvious for n = 1 or n = 2.Consider a vertex v != root. If we choose some set of leaf nodes L = {l1, l2, ..., lk} in its subtree, how many bridges do we remove? This number equals to the size of the union of edges of all paths from li to v, plus some number C, which does not depend on leaves in L. Actually, C depends only on other leaf nodes we chosen — the ones not in L. It can be shown that C equals to the number of remaining bridges on the path from v to root after we choose all leaves do not belong L.This means we can choose some leaf nodes outside of v's subtree, and then optimize leaves in Lindependently from others, if |L| = const(if their number remains constant). By inductive hypothesis for v's subtree, greedy is the optimal way.Suppose we have some solution which is not greedy. Let's show that there is a vertex v, which subtree solved non-greedy (and we can make it better). Just take 2 leaves: l1, which will be taken in greedy solution, and l2, which was taken instead of l1. Choose v = LCA(l1, l2).P.S. May be there is some inaccuracy in my proof, such as deg(root) = 1 condition in the problem, but induction does not use it. We need this condition only to find out that we should connect root with 2k-1 leaves, so there is no problem.
 » 2 weeks ago, # |   0 Why does this code gives TLE? As far as I know it is clearly O(nlogn). 263649473
•  » » 2 weeks ago, # ^ |   0 nvm found it
 » 2 weeks ago, # |   0 For Problem F, instead of the implementation idea mentioned in the editorial, if we simply brute force (i.e. when we take the longest path, simply update the distances of all leaves whose edge numbers decrease), what would be the complexity? I am struggling to find a construction that makes the number of updates worse than O(N^1.5)
 » 2 weeks ago, # |   0 In D tutorial can someone explain these lines? I couldnt get it:"Luckily, it is easy to fix, if the current balance balr and there is balance x in the map such that x
 » 2 weeks ago, # |   0 Amazing E problem, thank you BledDest !
 » 13 days ago, # |   0 Just got this e-mail that plague has been detected in my code and I am genuinely so confused. My solution for D problem is only slightly similar to one random guy's solution!? This contest was a huge rating boost for me. Please review this 263359271 This is my submission and the following is the other guy's submission: 263354669 MikeMirzayanov