Блог пользователя awoo

Автор awoo, история, 5 месяцев назад, По-русски

1976A - Проверка пароля

Идея: BledDest

Разбор
Решение (awoo)

1976B - Увеличение/уменьшение/копирование

Идея: BledDest

Разбор
Решение (Neon)

1976C - Собеседование на работу

Идея: BledDest

Разбор
Решение (BledDest)

1976D - Инвертируемые скобочные последовательности

Идея: BledDest

Разбор
Решение (Neon)

1976E - Разделяемые перестановки

Идея: BledDest

Разбор
Решение (BledDest)

1976F - Удаление мостов

Идея: BledDest

Разбор
Решение (awoo)
  • Проголосовать: нравится
  • +97
  • Проголосовать: не нравится

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

W contest, W editorial!

»
5 месяцев назад, # |
  Проголосовать: нравится 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 ?)

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 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

    • »
      »
      »
      5 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        5 месяцев назад, # ^ |
          Проголосовать: нравится 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.

        • »
          »
          »
          »
          »
          5 месяцев назад, # ^ |
            Проголосовать: нравится 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 did
          • »
            »
            »
            »
            »
            »
            5 месяцев назад, # ^ |
            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.

        • »
          »
          »
          »
          »
          5 месяцев назад, # ^ |
          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.

          • »
            »
            »
            »
            »
            »
            5 месяцев назад, # ^ |
            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 :(

            • »
              »
              »
              »
              »
              »
              »
              5 месяцев назад, # ^ |
                Проголосовать: нравится 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.

            • »
              »
              »
              »
              »
              »
              »
              5 месяцев назад, # ^ |
                Проголосовать: нравится +1 Проголосовать: не нравится

              https://codeforces.me/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.

    • »
      »
      »
      5 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      O(n) solution -> 263543487

  • »
    »
    5 месяцев назад, # ^ |
    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 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.

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Problem C is much simpler when using DP
    https://codeforces.me/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

  • »
    »
    5 месяцев назад, # ^ |
    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.

    • »
      »
      »
      5 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        5 месяцев назад, # ^ |
        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.

»
5 месяцев назад, # |
  Проголосовать: нравится +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

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Loved C

»
5 месяцев назад, # |
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 convolution

Submission

»
5 месяцев назад, # |
  Проголосовать: нравится 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?

»
5 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Nice contest ! Thanks for this nice editorial

»
5 месяцев назад, # |
  Проголосовать: нравится +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.

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 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.

»
5 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

263511839

»
5 месяцев назад, # |
Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится
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.

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    bro explain

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Same I thinked that but unable to come up how to count it ??

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Hii, can you please explain significance of this if(potential & 1ll) bucket[potential/2] = 0;

    • »
      »
      »
      5 месяцев назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      The "potential" is $$$bal_i$$$ in the official editorial. Consider the $$$bal_i$$$-$$$i$$$ graph. When we flip a segment of parentheses ending with index $$$i$$$, we find a previous index $$$k$$$ with $$$bal_i$$$ and flip the graph between them across $$$y = bal_i$$$. The flipped $$$bal$$$ should be no smaller than zero, so if $$$\exists j, k<j<i$$$ s.t. $$$bal_j > 2bal_i$$$, it flips down below zero and all the $$$k$$$s before $$$j$$$ don't count, and the bucket will be reset.

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem F, how to prove greedy is correct?

  • »
    »
    5 месяцев назад, # ^ |
    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 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      What if LCA is the root?

      In before, the root does not only have 1 son, because you prove the induction hypothesis not just for that tree, but for any tree with n nodes.

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

263649473

»
5 месяцев назад, # |
  Проголосовать: нравится 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)

»
5 месяцев назад, # |
  Проголосовать: нравится 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<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)."

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Amazing E problem, thank you BledDest !

»
5 месяцев назад, # |
  Проголосовать: нравится 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

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

best content

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think in the editorial of B, in the first point we should increase a[i] to b[n+1] instead of a[n+1] to b[n+1] because a's size is n only.

»
6 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone point out my mistake in this solution for C, I am not able to figure out where am i going wrong. I has implement in exactly same way as given in the editorial.

Submission Link: https://codeforces.me/contest/1976/submission/283706262

»
6 недель назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

can someone tell me why is this wrong?

~~~~~~~~~~

void solve(){

ll n,m;cin>>n>>m;

vll ps(n+m+1);ai(ps,n+m+1);

vll ts(n+m+1);ai(ts,n+m+1);

sll prog,test;

ll ans=0;
vll vecans;

for(int i=1;i<n+m+1;i++){
    if(ps[i]>ts[i]){
        if(prog.size()==n){
            test.insert(i);
            ans+=ts[i];
        }else{
            prog.insert(i);
            ans+=ps[i];
        }
    }else{
        if(test.size()==m){
            prog.insert(i);
            ans+=ps[i];
        }else{
            test.insert(i);
            ans+=ts[i];
        }
    }
}
vecans.pb(ans);
// cout<<ans<<"\n";

for(int i=1;i<n+m+1;i++){
    if(prog.find(i)!=prog.end()){
        ans-=ps[i];
        prog.erase(i);
    }else{
        ans-=ts[i];
        test.erase(i);
    }

    if(ps[i-1]>ts[i-1]){
        prog.insert(i-1);
        ans+=ps[i-1];
    }else{
        test.insert(i-1);
        ans+=ts[i-1];
    }

    if(prog.size()==n){
        vecans.pb(ans);
    }else{
        if(prog.size()>n){
            auto it=*prog.rbegin();
            ans-=ps[it];
            ans+=ts[it];
            prog.erase(it);
            test.insert(it);
        }else {
            auto it=*test.rbegin();
            ans-=ts[it];
            ans+=ps[it];
            test.erase(it);
            prog.insert(it);
        }
        vecans.pb(ans);
    }
}

printvec(vecans);

}

~~~~~~~~~~~~