awoo's blog

Educational Codeforces Round 166 Editorial
By awoo, history, 3 weeks ago, translation, In English

1976A - Verify Password

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

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

W contest, W editorial!

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

Is there any way to determine the difficulty rating of recently asked contest problems? Any guidance on this would be greatly appreciated.(Any extension ?)

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

whats the motivation behind problem-C, i was blank after reading the problem. Any tips for such problem.

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

    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

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

      Can you briefly explain what exactly are you running the binary search on?

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

        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.

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

          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 did
          → Reply
          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            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.

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

          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.

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

            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 :(

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

              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.

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

              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.

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

      O(n) solution -> 263543487

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

    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 set2

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

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

    Problem C is much simpler when using DP
    https://codeforces.com/contest/1976/submission/263321988
    We 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_tester
    Then 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

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

    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.

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

      By caching , doesn't it exceed time complexity? Because we need to cache (n+m+1 * n * m) states. Thanks

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

        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.

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

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

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

Loved C

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

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 convolution

Submission

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

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?

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

Nice contest ! Thanks for this nice editorial

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

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.

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

    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.

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

Can anyone tell me why does my O(n) solution fail for problem C

263511839

→ Reply
»
2 weeks ago, # |
← Rev. 3   Vote: I like it +11 Vote: I do not like it
O(n) problem D in only 24 lines

UPD: I compressed my code further and I'm surprised to find that I now have the shortest correct solution for the problem.

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

In problem F, how to prove greedy is correct?

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

    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.

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

Why does this code gives TLE? As far as I know it is clearly O(nlogn).

263649473

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

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)

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

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<balr−x , we can remove all its occurrences from the map (i. e. remove the key x from the map). This fix works because the current position lies between the left border (which we store in the map) and the potential right border, and the current balance is too high (which violates the first condition)."

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

Amazing E problem, thank you BledDest !

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

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

→ Reply