I think E has same idea as this

Problem C video Editorial : YOUTUBE VIDEO LINK Audio : English

E can be solved linearly.

edit : I lost some rating but I think the problems were very nice :)

Wow, I just see a solution of E which takes $$$O(n)$$$ time. It just uses 1 DFS to calculate the result synchronously just by how we will do to find out the result of one color.

I solved E with centroid decomposition (which is $$$O(n log n)$$$) but got TLE.247977712

But the Editorial says authors were expecting $$$O(n log^2 n)$$$ solutions. I'm confused.

Hello Codeforces! Please explain what virtual trees are (they are used in the second solution of the problem E).

Need Help.

Why does this solution give tle while the one given in editorial passes for the problem 1923E - Count Paths.

248160733

Can someone please tell on which case this is failing?

ll n,q;

cin>>n>>q;
ll arr[n];
for(ll i=0;i<n;i++){
    cin>>arr[i];
}
ll pre[n];pre[0]=arr[0];
for(ll i=1;i<n;i++){
    pre[i]=pre[i-1]+arr[i];
}
while(q--)
{
    ll l,r;
    cin>>l>>r;
    ll sum = pre[r-1];
    if(l>1){
        sum -= pre[l-2];
    }
    if(l==r){
        cout<<"NO\n";
    }
    else{
        ll length = (r-l+1);
        ll atleast = sum/length;
        if(atleast>1){
            cout<<"YES\n";
        }
        else if(sum==3 && length==2){
            cout<<"YES\n";
        }
        else{
            ll total_ones = length - (sum%length);
            if(total_ones>(length/2)){
                cout<<"NO\n";
            }
            else{
                cout<<"YES\n";
            }
        }
    } 
}

I had an idea that works in O(n):

Check this code:

https://mirror.codeforces.com/contest/1923/submission/247999826

i have solved E linearly. Here is the solution

here ans[c] means how many visited nodes of color c are available to be the first vertex .

when we are going forward we can only add 1 node of that color with new node. And when we go backward we are getting 1 extra node to add with new nodes.

In problem B, why is it always optimal to hit the nearest monster? There can be a possibility that there was another monster far away with much much greater health, and if certain bullets were not provided to them within the starting seconds, they would definitely hit the origin.

I would love to know if someone can tell me why my solution to problem C is so slow (2308 ms)

The third case in Tutorial-C: If this sum is greater than ...

Change 'greater' to 'smaller'.

You can use divide and conquer on tree to solve problem E easily in $$$O(n \log n)$$$ too. It is easy to think.

If someone want to consult a centroid decomposition + set solution can see my submission: 248033502. My idea: I can count the number of way cross the centroid node for all node and use set to manage the first node in DFS way has color C.

I am unable to understand why the solution to problem E has time complexity O(n log^2 n ). For every node, we are iteration through all the children, and then for every child we are iterating through every color it has. Can someone explain it to me?

I think there are some mistakes in tutorial for problem 1923C — Find B

To answer query l , r at first let's try to find the array b with the minimum value of ∑bi . For this, for indexes i , where ci=1 we have to set bi=2 , and for indexes i , where ci>i we have to set bi=1 . Thus, the sum of all elements in array b equal to cnt1⋅2+(r−l+1)−cnt1 or (r−l+1)+cnt1

. Now we have three cases:

If this sum is greater than ∑ri=lci then the answer is NO

If this sum is equal to ∑ri=lci then the answer is YES

If this sum is greater than ∑ri=lci then we can add this excess to the maximal element in array b In this case, the answer is YES

instead of ci>i, shouldn't it be ci>1 ?

In third case, shouldn't it be smaller instead of greater?

My solution for C got hacked. It seems somes python solutions are just taking more time. Can somebody explain ?

def f(c,l,r):
  if l == r:
    return False
  return c[r]-c[l-1] >= 0

def solve():
  n,q = list(map(int,input().split()))
  a = list(map(int,input().split()))
  b = [ -1 if x == 1 else x - 1 for x in a]  
  
  c = [0] 
  for i in range(n):
    c.append(c[-1]+b[i])

  for i in range(q): 
    l,r = map(int,input().split())
    if f(c, l, r): 
      print('yes')
    else:
      print('no')

   
t = int(input())
for _ in range(t):
  solve()

About F's fact 4, two binary strings should have same number of '1'. Is it true?

I solved E using stack for each color.

Here is my solution: 248216745

Can someone tell me why my solution for B is not working.

My Submission

Approach — stored the sorted vector (distance,hp) in vector p. Then,iterated through vector p and for each monster, calculated the time it would need to be killed by the forumla hp/k. also calculated bullets left in extra. at the start of each iteration , subtracted extra bullets

D was a realy good question. Great Contest

Explaining Tourist's Solution to D Problem

Objective: For each slime, find min no of operations to eat that slime. One Operation is eating of one slime by an adjacent bigger slime.

Some observations:

• For each slime, if there is a bigger slime to immediate left/right, then ans for this slime = 1.

Now in other cases

• If there is a consecutive set of equal-sized slimes, they can't do any operation on each other.

• Any merging operation to make a bigger slime are made either to the LEFT or RIGHT, not including the index of the slime.

• Looking at one side (left or right), there must be at least 2 different-sized slimes on this side.

• Since eventually the adjacent slime needs to get bigger than the current slime, we need to look for the min slimes to include on one side, which has its prefix sum > current slime size, and no of distinct slimes > 1.

• Since the prefix sum is monotonous for a contiguous range, we can perform binary search on both side to find the min number of slimes to include to satisfy the condition.

• Explanation of setting limits for binary search: LEFT keep the lo limit at 0, and hi limit at the largest index where slime size is not equal to that of the slime to the immediate left of current slime. Because need to ensure at least 2 different-sized slimes be included in the range.

Pre-processing:

• l(n) and r(n) : Store the begin and end index of the contiguous equal-sized slime windows.
• p(n+1) : prefix sum array : its monotonicity property helps use binary search.

Overall Time Complexity: O(nlogn)

• O(n) time for preprocessing

• O(nlogn) time for the core implementation: logn time to binary search to LEFT and RIGHT of the current index.

I lost rating, but I enjoyed the challenging problems.

248285844 Problem D Whats wrong with my code please someone help. I just don't get why am i getting wrong answer.

For Problem E, I came up with this simple solution.

void dfs(int s, int p, vector<int> *adj, map<int,int> &m, ll &ans, vector<int> &a){
    ans += m[a[s]];
    int t = m[a[s]];
    for(int u:adj[s]){
        if(u==p)
            continue;
        m[a[s]]=1;
        dfs(u,s,adj,m,ans,a);
    }
    m[a[s]]=t+1;
}
// not pasting template here, scan -> cin, print -> cout
void solve()
{
    int n;
    scan(n);
    vector<int> a(n);
    vscan(a);
    vector<int> adj[n];
    for(int i=0; i<n-1; i++){
        int x,y;
        cin>>x>>y;
        adj[x-1].push_back(y-1);
        adj[y-1].push_back(x-1);
    }
    map<int,int> m;
    ll ans = 0;
    dfs(0,-1,adj,m,ans,a);
    print(ans);
    return;
}

can we solve C using sparse table ?

can we solve C using sparse table ?

Can anybody tell , for problem 2 why this code is giving error on test case 2 , https://mirror.codeforces.com/contest/1923/submission/248233287

For problem D : Can anyone tell why is this code giving wrong answer??248345962

Can someone explain why jiangly's solution to problem E works in O(Nlog^2N). I know it utilizes small to large merging, but why does merging by the size of color sets yield that complexity? When we merge some node's children, set size won't necessarily go up 2x. For example combining sets (1,2,3) and (1,2,3) will give us (1,2,3) again, so the regular proof does not apply here.

Edit: Nvm, I neglected the fact that number of colors is always less or equal than the number of nodes in a subtree. The proof is trivial.

How does one come up with solutions like that of problem C? :/

I do not understand why does my submission not pass the second test case and what am I doing wrong here. Can someone please explain? 248388078

I made video editorial for E discussing the DP idea (excluding the small to large trick).

I also made a contest with easy version of problem E and some followup problems. Access it here

Thanks

Problem F's "Fact 4",You should specify that s'1 and s'2 have the same number of 1s , otherwise your statement is wrong.

s1=1000011 s2=1000100 k-1=2 s'1=1001111 s'2=1000111 s1 < s2 and s'1 > s'2

For E with Virtual Trees — I think you can do just an modified Euler walk of the tree first, and then walk on only the nodes of the same color in the order of the Euler walk: it will be eqv. to doing DFS on the Virtual Tree. So should be easy to do DP in each node for all its top-level children with/without being a direct descendent of the parent.

The final complexity should be just O(n), better than the O(n log n) of the tutorial.

The modification of the walk is that you put the node each time you visit it, not only first & last time.

can someone give me the testcase where this solution (https://mirror.codeforces.com/contest/1923/submission/248724413)

In problem D,my code got a "Wrong Answer" on test 2. Can anyone give me a hack? Many thanks.

https://mirror.codeforces.com/contest/1923/submission/248850524

Problem C : what's the mistake in this code? Please help. https://mirror.codeforces.com/contest/1923/submission/249311392

Is there a typo for the editorial for problem C? Should it be, "and for indexes $$$i$$$, where $$$c_i > 1$$$" instead of $$$c_i > i$$$? That makes more sense to me.

How Can We Do Problem B using Dynamic Programming?

How can we do B using DP?