Thanks for the fast editorial!

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

any help will be appreciated.

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

Как автор задачи E, мне жаль, что E и F были не в том порядке.

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

What does the "transition" mean in D?

achha contest

Прощу прощения, можно ли найти где-то авторский код?

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?

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

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

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

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

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

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 .

Can someone please check out why my submission for Problem D is giving TLE?

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define nl '\n'
#define all(v) v.begin(), v.end()
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll const mod = 1000000007;
ll inf = 1000000000000000000;

int iter = 0;
ll binexp(ll a, ll b){
    ll ans = 1;
    while (b){
        iter++;
        if(b % 2){
            if(ans>inf/a) return inf+5;
            ans = (ans * a);
        }
        if(a>inf/a) 
            a = inf+5;
        else 
            a = (a*a); 
        b /= 2;
    }
    return ans;
}
ll LOG(ll x, ll p=2){
    if(p == 1) return 0;
    for(ll t=1, i=0;; t*=p, i++){
        iter++;
        if(t > x) return i-1;
        if(t > inf / p) return i;
    }
}
ll func(ll x){
    ll res = 0, L = 4, R, p, val;
    while(L <= x){
        iter++;
        p = LOG(L);
        val = LOG(L, p);
        R = min({(1ll<<(p+1))-1, binexp(p, val+1)-1, x});
        // cout << L << ' ' << R << nl;

        res += (val * ((R - L + 1) % mod)) % mod, res %= mod;
        L = R+1;
    }
    return res;
}
void Heisenberg(){
    ll q; cin >> q;
    while(q--){
        ll l, r; 
        cin >> l >> r;
        cout << (func(r) - func(l - 1) + mod) % mod << '\n';
        // cout << iter << '\n';
    }
}
signed main(){
    auto begin = std::chrono::high_resolution_clock::now();
    IOS
    Heisenberg();
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
}

Approach: Lets say $$$y = \log_{\log_2(x)}(x)$$$ then the value will remain same till $$$tempR = \min(R, 2^{\log_2(x)+1}-1, \log_2(x)^{y+1}-1)$$$. So I will keep updating answer as $$$ answer += y \cdot (tempR - x + 1)$$$ $$$x = R + 1$$$.

I think swap E and F is a good idea

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

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define nl '\n'
#define all(v) v.begin(), v.end()
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll const mod = 1000000007;
ll inf = 1000000000000000000;

int iter = 0;
ll binexp(ll a, ll b){
    ll ans = 1;
    while (b){
        if(b % 2){
            if(ans>inf/a) return inf+5;
            ans = (ans * a);
        }
        if(a>inf/a) 
            a = inf+5;
        else 
            a = (a*a); 
        b /= 2;
    }
    return ans;
}
ll LOG(ll x, ll p=2){
    if(p == 1) return 0;
    for(ll t=1, i=0;; t*=p, i++){
        if(t > x) return i-1;
        if(t > inf / p) return i;
    }
}
ll func(ll x){
    ll res = 0, L = 4, R, p, val;
    while(L <= x){
        p = LOG(L);
        val = LOG(L, p);
        R = min({(1ll<<(p+1))-1, binexp(p, val+1)-1, x});
        // cout << L << ' ' << R << nl;

        res += (val * ((R - L + 1) % mod)) % mod, res %= mod;
        L = R+1;
    }
    return res;
}
void Heisenberg(){
    ll q; cin >> q;
    while(q--){
        ll l, r; 
        cin >> l >> r;
        cout << (func(r) - func(l - 1) + mod) % mod << '\n';
    }
}
signed main(){
    auto begin = std::chrono::high_resolution_clock::now();
    IOS
    Heisenberg();
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
}

Mathforces

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

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);

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

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

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

#

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

Is there any online solution for F?

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?

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

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

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.

PROBLEM D

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

is there a way to solve problem c with binary search

Can F be solved online?

I think it is better with spoilers, and code.

Thank you, 127.0.0.1

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;

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

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!

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

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

Helpfull

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?

Solution to problem F- A Glowing Tree

Click here

If you like my solution please upvote me

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.