Hi , your explanation was really clear. I came up with a solution inspired from yours, I used your idea to calculate b1[] and b2[] where b1[i] is the maximum impact while using i operations of cost 1 (and cost 2 for b2[i] ).But instead of dp , I binary searched for the number of operations , which is < nlog(nWmax) as you said , for a fixed number of operations , say x , there is x+1 ways to construct a solution : take i + (x-1)mod 2 from cost 1 and (x-i) / 2 from cost 2 with 0 <= i <= x . For each of these possibilities , we can calculate the maximum impact which is y = b1[i + (x-1)mod2] + b2[(x-i) / 2] , if Sum_impact — y <= s for any i then x is valid. It works in O(nlog(nWmax)*log(nlog(nWmax))) Hope i explained it well .

How to solve E2 ?

Auto comment: topic has been updated by youssefbou62 (previous revision, new revision, compare).

for all i <= n we have a_i <= n so you don't need to save sums > n.

thanks.

"Finding node u, v could be done with dfs and stack for each milk_type." Could you elaborate ?

How to solve gold milkvisits ( the one about trees ).

https://leetcode.com/problems/sum-of-distances-in-tree/solution/

Got it , thanks a lot !

In coin combination my solution is O(x*n) but I implemented it bottom and bookshop is classic knapsack in O(x*n) too and you don't need to save O(x*n) state but only previous state.have you implemented your solution in top down or bottom up dp ?

https://cses.fi/problemset/list/ Dp section has some classic dp problems

and why does it work ? if I understood well d1,d2 save the distances from two leaves of the diameter to every node?

Auto comment: topic has been updated by youssefbou62 (previous revision, new revision, compare).

I still don't understand the solution for this problem even after watching Errichto's video.Any help ?

This is not what rudy said in his comment.

I was searching a solution for a problem on google.

We can solve this problem Offline. First, sort the queries in increasing order and the values of the array as {value,index}. For each query ,using a data structure which can do sums and update operations (eg segment tree or bit), set to one the all the indices which have value < K of the current query and >= K of the previous query .As you have done this for previous queries the sum query will take into account all values < K.the answer of i'th query is sum(l,r) after performing updates. Here's my submission for a similar problem.

https://www.spoj.com/problems/KQUERY/

Stop saying no sense please!

I get it Thank you.

More details please.

How to solve problem D ?

Hi could you please upload the articles you write on your github for people who understand french ? It's often hard to find clear explanations for OI problems.

How to solve D2 ?

amiratou is my favorite coder !

Send $5500 and I'll help!

Thanks a lot for the explanation !

Could explain in more details the solution to problem D ?

any link to your submission ?

Please, what are the math/algorithm prerequisites to understand the problem's E solution?

please refer to this

I misread the statement , sorry .

"you can just simulate the process, performing actions from third to first."__

why in that order ?

that's wrong !

let's take n = 10 and order /2 , 4/5 ,2/3 then n is 10 , 5 , 4 this outputs -1 so order does matter if u do it this type of operations but i think you to wanted to get its factors so you do /2 , ans ++ , /5 , ans+= 3 , /3 ,ans+= 2 ,

for problem A why do you choose this order of operation 4*n/5 , 2*n/3 , n / 2 ?

check answers above before commenting.

understood ! thank you very much.

How to solve problem E ?

https://www.youtube.com/watch?v=FAQxdm0bTaw

Could anyone offer more explanation for problem F ? I don't understand this " If you fix some k and C, the route would be uniquely decided. Let f(k, C) be the score for the route. Then it holds that " and its implementation even after looking at AC submissions.

Thank you.

Could anyone provide a clear explanation for problem D pls ?

Some troller put my name in the list . Could you please remove it ?

How to solve D ?

Are there any problems similar to problem D for practice ?

What's the approach for Div2D(Div1A) please ?

Worst case is when you start at position (0,0) and destination is(1e9,1e9) then manhattan distance is 2*1e9 , also in worst case scenario wind would be against you and it is at max 1e5 so if you can reach destination you should be able to move by 1 every wind cycle therefore 2*1e9*1e5 = 2e14

Yes if someone can further explain it it would be really nice.

Could you please further explain what your check function does ?

Why does my submission for C fail in tc1 using g++ 11/17 48256069&& gets AC with clang 48258190 ?

Edit : I figured it out i wrote the fast io thing after doing the first cin

Could you provide the link of your youtube channel ? I really want to watch today's stream's replay .

Thank you that helped me a lot !

Can anyone explain to me why my solution for problem C get's WA In testcase 13 ? 42740594