127.0.0.1's blog

Codeforces Round 907 (Div. 2) Editorial
By 127.0.0.1, history, 12 months ago, translation, In English

Thank you for participating!

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +116
  • Vote: I do not like it

Comments Comments (90)
| Write comment?
»
12 months ago, # |
  Vote: I like it +34 Vote: I do not like it

Thanks for the fast editorial!

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

    I am having a little problem in D. Its working on nearly all the test cases and logic is to point. But I think there is some problem with modulus and its giving wrong answer on one test case-v 179 1000000000000000000 Can any body help I cant seem to figure it our. This is my code where maxi is modulus ll l,r; cin>>l>>r;

    ll te=l; ll ans=0; while(te<=r) { ll p=log2(te); ll up; // if(p==63) // up=r; // else up=min((ll)(pow(2,p+1)-1LL),r); //cout<<up<<endl; ll ct=0; ll x=1;

    while(x*p<=te) { x*=p; ++ct; } // cout<<te<<" "<<x<<endl; while(true) { ll nx; //cout<<x*p<<e ndl; x*=p;nx=min(x,up+1); ll nxm=nx%maxi; ll tem=te%maxi; ans=(ans+(ct*((nx-te)%maxi))%maxi)%maxi; if(nx>up) break; ct=(ct+1)%maxi; te=nx; } if(up==r) break; te=up+1;

    } cout<<ans<<endl;

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

      I had kinda similar problems, try using unsigned long long instead if you're not using that

      → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why the approach for F with euler tour+Lazy prop is giving tle on tc 21? here is the code-https://codeforces.me/contest/1891/submission/230589277

any help will be appreciated.

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

    I think the problem is that you are passing the adj vector to dfs not by reference

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

      vector*adj means we are passing vector adj[n] by reference.

      Thanks for responding but i got AC by using unordered_map instead of map.

      → Reply
»
12 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I came up with the author's solution F, but I didn't have enough time to debug((

→ Reply
»
12 months ago, # |
  Vote: I like it +16 Vote: I do not like it

F can be solved without reversing the queries. It is offline though.

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    It would be online if the final tree was known beforehand. Otherwise — yes, the online solution would be quite nasty with maybe some link-cut trees or treaps.

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

    What do you mean by reversing the queries? I just run on the queries and update to 0 when adding a node

    → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What does the "transition" mean in D?

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

achha contest

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In C problem I did as proposed in editorial, but in one test case answers differ. Here is sequence of 14 hits from my implementation:

[1, 1, 2, 5, 6, 6]
=1h small stack=1 0/6
=2h small stack=1 1/6
=4h small stack=2 2/6
=6h big stack=5 4/6
crushing 6/6
=7h -> [3, 6] combo=0
[3, 6]
=10h small stack=3 0/6
crushing 3/6
=11h -> [3] combo=0
1 stack with 3 left. hit by 1
[3]=14h

Can someone provide a sequence to win with just 13 hits?

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

    On the final stack of 6 use the combo at the end (2 small attacks (4) -> combo(-1)) instead of doing combo(3) -> 3 small attacks(0).

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Thanks. Premature use of combo is the root of evil

      → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to avoid tle for C https://codeforces.me/contest/1891/submission/230581501

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

    If you want to stick to this approach, try using std::deque, erase() from the beginning of vector is expensive operation. Or take a look how beautifully contest leaders solved it.

    → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is an alternative solution for F, using Fenwick Tree.

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

    Same, I think this is more direct.

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

    What's the logic?

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

      I believe that my solution 230576374 is the same as in this comment, so I'll describe it.
      Let's build our tree and for each vertex save its creation time and updates with current time and value.
      What is answer for some vertex? It's sum of all requests which were made on this vertex or any of parents LATER than creation time of current vertex. So let's create BIT for sum of requests by time and dfs our tree. We perform updates before getting ans and rollback them before dfs exit thus for each vertex only relevant updates remain:

      dfs(u, p):
    for (time, value) in updates[u]:
        bit.update(time, value)
    ans[u] = bit.get(createdAt[u], n)
    for (int v: g[u]): if v != p:
        dfs(v, u)
    for (time, value) in updates[u]:
        bit.update(time, -value)

      Each update is made exactly twice, so it's $$$O((n + q) \log(n))$$$

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

        Thanks for the explanation! Very creative solution. I like that you no longer need range updates, only point updates and range queries.

        → Reply
»
12 months ago, # |
  Vote: I like it +108 Vote: I do not like it

What was the reasoning for putting problem F at that position?

→ Reply
»
12 months ago, # |
  Vote: I like it +21 Vote: I do not like it

This is probably the easiest F I've ever seen :(

→ Reply
»
12 months ago, # |
← Rev. 5   Vote: I like it +5 Vote: I do not like it

C can be implemented not using two pointers. But during the contest i forgot to check if n == 1 and a[i] == 1 :\

void solve() {
    scanf("%lld", &n);
    int s = 0;
    for (int i = 1; i <= n; i ++) {
        scanf("%lld", &a[i]);
        s += a[i];
    }
    if (n == 1 && a[1] == 1) {
        puts("1");
        return;
    }
    int sp = s / 2;
    sort(a + 1, a + 1 + n);
    int ss = 0, cnt = 0;
    for (int i = n; i >= 1; i --) {
        ss += a[i];
        cnt ++;
        if (ss >= sp){
            break;
        }
    }
    printf("%lld\n", cnt + s - s / 2);
}
→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a problem on C . In 230619057 the code id accepted , but in 230619275 , the code is wrong . The only difference between them is merely in "lower_bound(pres,prew+n+1)" or "lower_bound(pres+1,pres+n+1)" . But the pres is the prefix sum of a which indicates that the sum divided by 2 (floor,except for n = 1) must be positive . So "+1" should not make a difference to my solution . I am quite confused . Please help we .

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

    I reverse the order , sorry . The former one is wrong , while the latter one is correct .

    → Reply
»
12 months ago, # |
  Vote: I like it +36 Vote: I do not like it

I think swap E and F is a good idea

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please tell me why is my submission for Problem D giving TLE?

Code
→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You recalculate intervals every time you run "func" function. Doing it once and storing it somewhere could help. My solution working as I said: 230684869

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

      Yeah, I got that later. Even this solution is correct if I directly calculate from L to R rather 1 to R and 1 to L.

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

Mathforces

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Nope

    Spoiler
    → Reply
»
12 months ago, # |
  Vote: I like it +13 Vote: I do not like it

why is E is much difficult than F. Or why is F much easier than E.

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe the simplest implementation for C:

sort(a+1,a+1+n);
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
int tmp=(sum[n]+1)/2;
int c=0;
for(int i=1;i<=n;i++) if(sum[i]>tmp) c++;
printf("%lld\n",tmp+c);
→ Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

can anyone explain why the greedy solution works in C? also for the case when i==j and the last number is an odd number and x=0, then there is no way we can use the 2nd method on this horde

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

    It's possible to use 2nd method when there is only 1 horde left with odd size and x = 0.

    For example left horde size = 7 and x = 0 Use 3 attacks of first type. After that horde size = 4 and x = 3. Use second type (ultimate) attack. After that horde size = 1 and x = 0. Use 1 attack of first type. After that horde size = 0.

    So it takes 5 attacks to destroy horde size including second attack. Without second attack it would take 7 attacks.

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

      thanks, and it was my bad, I took the 2nd method as it can be used only when there are exactly x monsters left in a horde :-(

      it's also clear now why the greedy solution works

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

I came up with using offline query in problem F. My idea is first save the query and build the completed tree which is presented in the end. Then, I just need to loop from q to 1 and update normally using Euler's tour when type 2 is meet otherwise if type 1 is the current query, output it's node value. But unfortunately, I got WA immediately at 2nd test case although this idea is kind of nature (or maybe it's wrong in some case), anyone suggests me why am i wrong here?

My submissions: 230648660

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone help in f...getting wa on 2..230657380

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

    are u wrong answer in 4927th or 799th

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

      4927

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

        It is wrong in answer of node. Node in tree is different from node in euler tour (my english is bad sry about it)

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

          sorry for being such stupid....replaced a[i] with a[tin[i]] and accepted....thanks

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

#

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone give a simple idea about F? Also may I know what are the prerequisites to learn to solve problem F?

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it
    1. Queries are offline, you already know how your tree will look like
    2. Can you solve this problem if first queries are always making the tree and other queries are adding (I mean, try solve this: you have a tree and $$$q$$$ queries add some $$$value$$$ on subtree, how solve this?)
    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I guess there are multiple ways of doing the 2. one you have mentioned. Can you suggest which method is good to opt.

      → Reply
      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        You can do $$$dfs$$$ and go down from root to leafes.

        If in node $$$x$$$ you get some sum from above, you also get same sum into all nodes in $$$x$$$ subtree.

        → Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Prerequisites: "offline" approach, DFS pre-order, fenwick tree (range add/point get interpretation)

    → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any online solution for F?

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D

and on each segment there are at most O(logn) transitions

shouldnt there be like at most 2 transitions per segment because if we make 3 transitions that would mean jump to next segment?

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My logic is similar to one in editorial but I am having issues with MOD. What changes should be done in my code ?

https://codeforces.me/contest/1891/submission/230655160

Also what are some good sources for topics like modular arithmetic and other topics that will help me remain stable expert. Thanks

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Out of curiosity following problem F , how will this problem be solved? Initially i have only one vertex which is numbered 1.There are 1e5 qeuries where in one type of query i can add a vertex to the tree with number sz+1 (sz is the no of nodes in the tree currently).Can i answer other type of query where i need to tell the size of subtree rooted at a given vertex in logn time or what will be the most optimized algorithm for this.

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

    Euler Tour Technique

    Note that you don't need to answer the queries online. So you can create the whole tree and process queries later.

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

      can you explain a bit more . Like when a node is added i need to change the size of subtree of all the ancestors of the node . How will i do that?

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

        From the page:

        Notice that after running dfs, each range [start[i], end[i]] contains all ranges [start[j], end[j]] for each j in the subtree of i.

        So, to add something to the subtree of i, you just update the values from start[i] to end[i]. This can be done with any range update technique.

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

      what does online means here? I saw it in other comments also but don't know it's meaning

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

        u dont know the queries in advance

        → Reply
»
12 months ago, # |
← Rev. 5   Vote: I like it -7 Vote: I do not like it

PROBLEM D

→ Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Here is the implementation of sqrt decomposition for F. It is giving TLE as warned by author. Any optimisation in provided code is welcomed.

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

is there a way to solve problem c with binary search

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

Can F be solved online?

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think it is better with spoilers, and code.

→ Reply
»
12 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Thank you, 127.0.0.1

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

127.0.0.1 I am having a little problem in D. Its working on nearly all the test cases and logic is to point. But I think there is some problem with modulus and its giving wrong answer on one test case-v 179 1000000000000000000 Can any body help I cant seem to figure it our. This is my code where maxi is modulus ll l,r; cin>>l>>r;

ll te=l;
 ll ans=0;
 while(te<=r)
 {
    ll p=log2(te);
    ll up;
    // if(p==63)
    // up=r;
    // else
    up=min((ll)(pow(2,p+1)-1LL),r);
    //cout<<up<<endl;
    ll ct=0;
    ll x=1;

   while(x*p<=te)
   {
      x*=p;
      ++ct;
   }
  // cout<<te<<" "<<x<<endl;
   while(true)
   {
    ll nx;
    //cout<<x*p<<e ndl;
    x*=p;nx=min(x,up+1);
    ll nxm=nx%maxi;
    ll  tem=te%maxi;
     ans=(ans+(ct*((nx-te)%maxi))%maxi)%maxi;
     if(nx>up)
     break;
     ct=(ct+1)%maxi;
      te=nx;
   }
   if(up==r)
   break;
   te=up+1;



 }
 cout<<ans<<endl;
→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone help me,i am getting WA on test 2 of F https://codeforces.me/contest/1891/submission/232563023

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone try (probably the dumbest) solution to F by reversing queries and doing segtree with range updates on the euler tour of the final tree? That's the first thing that comes to mind

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a problem in D. I got a wrong anwer on test 8, and I have trouble finding where I went wrong. My submission is Your text to link here... . Can someone help me figure out what the problem is? Thanks a lot if you can help!

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

    I am having the same issue, failed on the same test case. Did you manage to figure it out? if so, what was the issue?

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

      I filed on test case 8 because I used the function std::log2(), which led to a accuracy issue. I switched to using binary search to avoid the accuracy issue.

      → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please tell me if the error is in the steps of modular operations or in the map in the following solution. It would be a big help. My submission for Problem D

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am quite stuck on the 1891D task. I have checked the solution explanation, and I can't figure out one key element. The explanation says, that on each part with f(i)==f(i+1) we will have at max O(logn) transitions, such that g(i)!=g(i+1).
My question: how can g(i)!=g(i+1) be on the segment where f(i)==f(i+1), when f(x)=log2(x), while g(x) = logf(x)x, which means that it's base is bigger than 2, and that it should change its values significantly more rare that log2(x).

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem C, can someone explain why we are taking the attack iteratively rather than the subarray smaller to the largest horde (in this case the current j pointer)? Why not distributing attacks (of type I) on the remaining hordes beneficial since we can keep the largest hordes larger? and also, why are we minimizing the attacks of type II, wouldn't they be more effective if use them when the combo is higher than 1?

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

Solution to problem F- A Glowing Tree

Click here

If you like my solution please upvote me

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

2nd ques. can be done in less than O(30.N) if we maintain another array for counting the what should be added to the array element if it is divisible by some power of 2.

class Codechef {
public static void main(String[] args) throws IOException {
        Scanner ab = new Scanner(System.in);
        int t = ab.nextInt();
        while(t-- > 0) {
           int N = ab.nextInt();
            int Q = ab.nextInt();
            long[] a = new long[N];
            for(int i=0; i<N; i++) a[i] = ab.nextInt();

           boolean[] flag = new boolean[31];
           int mini = 31;
           for(int i=0; i<Q; i++) {
               int pow = ab.nextInt();
               if(pow < mini) {
                   mini = pow;
                   flag[pow] = true;
               }
           }

           long[] adder = new long[31];
           for(int i=1; i<=30; i++) {
               adder[i] = adder[i-1];
               if(flag[i]) adder[i] += (1<<(i-1));
           }
           for(int i=0; i<N; i++) {
               int pow = log(a[i]);
               a[i] += adder[pow];
           }
           for(int i=0; i<N; i++) System.out.print(a[i] + " ");
           System.out.println();
        }
    }
    static int log(long a) {
        int count = 0;
        while(a % 2 == 0) {
            ++count;
            a = a / 2;
        }
        return count;
    }
}

The time complexity comes out to be O(Q + NlogM), M = 30 at max.

→ Reply