Am I the only one who got accepted without any fastmax and fastmin ? 25100623 My O(n ^ 3) solution passed comfortably in 2 seconds

well this might help 24408090 . In this code I have used ordered_set which can be used by including the headers in my code. It works like std::set but also supports order of an element and finding element by order. Nevertheless you must learn BIT and segment tree. this is just for your understanding.

suppose we choose a[j] as our middle element then number of ways = number of i such that i < j and a[i] > a[j] * number of k such that k > j and a[k] < a[j] . we can easily find this using BIT or segment tree

that's a really cool observation! can you provide more insight on solving the general query problem ? I'm unable to think of any solution other than the naive algorithm.

what's the answer in that case? isn't it 5?

I guess just one extra change has to be made if components = 1 and graph is not cycle then ans++

woah! I wonder why no one ever mentioned that although it was obvious, haha. Btw, we can deal with the situation you have mentioned if we agree to pretend that a[-1] = 0,a[-2] = a[0] , a[-3]=a[1] and so on.. and similarly a[n] = 0,a[n+1] = a[n-1], a[n+2] = a[n-2]

nah.. I meant 100, 0 , 100 people thought 1000100 ? my choice of 100 was lame :P

woah! was there anything wrong in what I said? or did I understand the question wrong?

correction for question 1: it can be alternating between any number and 0 not just 1.for example the sequence 100 0 100 also evolves to 0 0 0 in one step.

you need to minimize the denominator not maximize, i blindly coded ternary search without thinking and then regretted it. :/

I still dont get the n+2m argument. I get that in the worst case we create 2 extra intervals per query but what is n+2m? I solved the problem assuming it doesnt get TLE. can someone please elaborate on estimating the time complexity of the solution? EDIT: I believe it has something to do with amortized complexity. Each query appears to have O(N) complexity however intuitively I feel amortized complexity must be better but i cant prove it yet. :/

I see that many solutions with worst case O(N^2) complexity have passed. those solutions simply added all the k-th sons to a set and found the size of the set. ideally they shouldnt have passed :/. It would easily fail on a test where all nodes are attached to 1 and the query repeatedly asks about direct sons of 1.

man, seriously!! are you even thinking? (no offence) this is too trivial.

Hi, I had a similar problem before. I see that you are using both scanf and ios::sync_with_stdio(0). Use either scanf or cin when u use ios::sync_with_stdio(0), but not both. That's the reason for the problem you are experiencing :) EDIT: Also, your code has wrong logic so correct that too :).

That's a dumb question indeed :P . What you are saying is like this .. 19/3 can be greater than 15/5 + 4/4 . just because you are using all the money it doesn't provide you with more number of dissatisfaction units(because the cost is also high). Mathematically it goes like this.. a*x + (a-1) = Sigma(Bi*Yi). where each Bi is greater than 'a' implies Sigma(Yi) <= x. It's easy to prove :) . However my submission was giving wrong answer on test 75. can anyone please check ? what's special about testcase 75? here's my submission- [submission:21965336]

This is a classic dp problem. I would like to give hints so that you discover the solution by yourself. Denote dp[i][j] as the number of ways to get 'j' more brackets of the type '(' more than ')'. Note that j can be negative so add some constant to balance it out. Now you need to calculate dp[n-1][0] . Try to figure out the relation between dp[i][j] and dp[i+1][j+1],dp[i+1][j],dp[i+1][j-1]. Also don't forget to take the module at every step. This should lead you to the answer :) EDIT: I did not see that the parenthesis expressions have to be distinct and I can't delete this comment now :(

Unusual rounds.. unusual rounds everywhere

Hi, I'm not understanding why my submission is getting TLE for Div2 F. can anyone please check it? Here's my submission, 21830666 I have implemented it exactly as given in the tutorial.

Thanks a lot! I'm sorry for posting on the wrong blog. I should have found that post myself. But I'm new here :D

Thanks for the quick reply! I am aware of the worst case complexity of unordered map. However, usually most of the times unordered map is observed to be faster. Can you share any further insights on deciding between unordered map and map. And also what is making unordered map slower than map in the above case I presented? i,e.. what kinds of data is suitable to be represented by map and unordered_map exactly?

EDIT: I see that the test case on which unordered map gave TLE involves hashing a multiple of some fixed number. Has this got something to do with the TLE(I believe it must be the reason). Also, was the testcase specifically designed so that unordered_map fails on it, How do we make sure not to fall in such traps if so?

Hi can anyone explain, why map is more than 10 times faster in this case? I could not find any reason for this. any help on this matter would be highy appreciated. I also tried adding the 2 lines of code mentioned above to make unordered_map faster but with no luck. 21740384 and 21740655

Hi, I could not understand why you can't find the same argument intuitive . The same argument works because choosing the nodes in that way includes the edges which could have been included by choosing the vertices from same subtree along with a few more edges. So this solution is guaranteed to be correct. I hope you understand my argument. Indeed our solution for the previous case was also hinged on the same idea

Can anyone please explain why beard graph has to be a tree. 1->2->3->1 satisfies as a beard graph but is not a tree. Please correct me if I am wrong

the solution in editorial uses indexing from 0. so it is x+y :).