What about using a persistent segment tree for F? We let version=depth and it should run in .

how to solve 3rd question rumor

in E — in O(1) (by precalcing factorials and inverse factorials)

https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind

in order to solve the problem you had to calculate s(n,k). How can you calculate this with O(1)?

Can someone please explain Div 2 F ? I am not able to understand it from the editorial ?

Problem C can be solved using disjoint set too!

Can someone elaborate on solving Problem C. I understand that if we find the minimum of each group, it will give us the minimum gold in order to spread the rumor. However, how can we turn the list of pairings we are given as inputs into groups?

Can someone explain me please why C(y+cnti-1 ; cnti) is the corect formula? I can.t undertand from where we have this relation

Good Contest

Can someone explain me "Segment Tree structure" solution for "F" ?

Can someone explain to me why my solution for D is wrong? https://paste.ubuntu.com/26042298/

For each ai = 0 I supppose that I deposited the maximum amount of money that I am allowed to deposit. Then, if my money at bank is greater than d, I substract only the necessary from the last deposit; if after this update, my last deposit cant make my money at bank non-negative, print -1.

Can someone provide a proof for editorial for E?

893F can be transformed into a 2D RMQ without assignments where there's only one element in each row, so I think 1D Sparse Table + 1D persistent segment tree/balanced tree can be used, which could also run in O(n log^2 n + m log n)... (Note: let dat[i][j] be the segment tree for elements from the i-th row to the (i+2^j-1)-th row, then the difference between dat[i][j] and dat[i+1][j] is only about two elements) Yet I'm not certain whether this solution will get Memory limit Exceeded. [sorry for my poor English]

Can someone explain the example input of F, why the output is "2 5"? I think I misunderstood the problem somehow...

In Problem C — Rumor, the editorial and comments mention describe a solution where one takes the sum of minimum gold for all connected components. In my solution 32587668, I sorted the characters by the amount of gold they need to spread the rumor. Then it is sufficient to process each character in order and run a DFS if not visited and sum up the gold required. There's no need to take the minimum anymore.

In problem E for every prime divisor i of n , we are calculating the number of ways of putting 'cnti' objects into 'y' boxes.

Or in other word the number of non-negative integral solution of equation x1+x2+x3+....+xY = cnti.

And this should be equal to (cnti+y-1)C(y-1) .

What is wrong in this logic? And if it is correct then how that formula came which you wrote over there?

For f we can also use fractional cascading wich gives us a solution with (n+q)log

I have a solution for F that involves a 2D data structure (It's a Segment Tree with Treaps in each node). It runs in O((N+M)*Log^2(N)). Here's the submission: 32671104

Hello codeforces community .. can someone tell me that the rumor problem can be solved without using the dfs / bfs i am just trying to maintain the neighbours of each vertex in an vector of vectors but get stuck any help will be appreciated

Can someone post their approach for the problem D (Credit Card) in Div 2?

Actually, tests in F are really weak. I got AC with O(n) for minimum query (with default athor solution which is supposed to use sparse tables to process a query with O(log(n)) by going down from x with 2^k steps and taking minimum on segment of precalculated values each time).

In E, can someone explain this ? And why do we multiply answer every time when we encounter new prime?

Can someone tell me why my submission gets MLE in problem F . I think it uses Nlogn memory which is within the limits. What am I missing here ?
PS. I made a typo in binary search in the get() function as typing (a<<step) instead of (1<<step) but i have no idea why did that cause MLE.

In Problem E: My code works till 7th test case and then shows long long int overflow in diagonistics --

"signed integer overflow: 58062342303970488 * 835 " says the error message,

but in my code it must not happen because

pdt=((pdt%MOD)*(NCR(val+y-1,y-1)%MOD))%MOD;

I have already taken mod before multiplication!

My submission : 32953649

Problem E can be solved using pure Segment Tree with complexity O((m+n)log(n)). First, run Eulerian ordering (using DFS) on this root tree. After that we got an array 2n elements where 2 adjacent elements have depth difference <= 1. We'll build segment tree base on this array. Each node [l, r] we store array of length r-l+1. Each i-th element of this array is minimum value which has depth <= i. Sorry for poor explanation. Sound like crazy but I got accepted submission. Pls check it out if you curious. 74651014

can pls anyone tell me whats wrong with my code for rumors?

Your code here...
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define f(i,a,b) for(i=a;i<b;i++)
int main()
{
    ll i,m,n,ans=0,ele1,ele2;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    vector<ll> gold(n+1);
    f(i,1,n+1)
    cin>>gold[i];
    vector<ll> a(n+1,0);
    for(i=0;i<m;i++)
    {
        cin>>ele1>>ele2;
        if(a[ele1]==0&&a[ele2]==0)
        {
            ans+=min(gold[ele1],gold[ele2]);
            a[ele1]=a[ele2]=1;
        }
        if(a[ele1])
        a[ele2]=1;
        if(a[ele2])
        a[ele1]=1;
        }
    f(i,1,n+1)
    if(a[i]==0)
    ans+=gold[i];
    cout<<ans<<"\n";
 
}

Alternate solution for F : Build a merge sort tree on the euler tour of the given rooted tree, with list sorted by height, giving prefix minimum of assigned id's. To speed up query in merge sort tree from Log^2(N) to Log(N), use fractional cascading. Solution works easily in less than 2 seconds.

In problem E, how is the formula for calculating the answer derived if there are no negative numbers?