print 7 - a + 7 - b + 7 - c because the sum of the numbers on opposite faces is 7.
Reverse the string & replace 6 with 9 and 9 with 6.
For all b[i], find how many values are there in C with value i. Then for every a[i], just add those values you have computed before.
I solved this in python to avoid any overflow issues. The idea is for each index starting from 0 to len(a + b) - 1, you try to see if it's possible to put b here. How to check that? You need to find how many ways are there if we put a at current index which will be choose(a + b - 1, a - 1) and if this value exceeds k then we put b(also subtract this value from k) else put a.
In this we are given a tree and for given queries, we are required to find how many nodes are under subtree u with distance d from root.
First we will need euler tour to define which nodes are under any subtree. While doing euler tour, keep track of at what depth we have which nodes(their start time). Then for each query you need to find how many values are there in range start_time[u] to end_time[u] with value d. So we can use binary search in depth vector above at given depth d to find how many values it has from start_time[u] to end_time[u].
To avoid overflow in D you could use the formula $$$\binom{n}{r}= \binom{n-1}{r} + \binom{n-1}{r-1}$$$
The other trick to avoid overflow is to go horizontally across 1 row of Pascal's triangle.
Can you explain why we do
k--at the start? Thank you in advance!I'm not sure which implementation you're referring to, but probably because you want the number to be 0-indexed, but the input format is 1-indexed.
Sorry for the vague question, I was referring to your submission. Thank you nonetheless. Love your streams btw, hope you do more in the future.
Ah, okay, then yes, it's because of the indexing thing I mentioned. I generally prefer zero-indexing, so I almost always translate things while performing the input to avoid issues later.
As for why it works in this problem, I think you should just trace through exactly how the code/logic works, and then you'll basically see that you reach the wrong answer if you don't do
k--(but I think you would get the right answer if you didn't dok--and you replacedcount_if_a <= kwith<). So basically it's "because it gets the right answer", haha.(My submission for reference/convenience to anyone else reading this.)
Auto comment: topic has been updated by dush1729 (previous revision, new revision, compare).
BRUUH, how didn't I think of binarysearching for the number of occurences. :(
For problem E,
"So we can use binary search in depth vector above at given depth d to find how many values it has from start_time[u] to end_time[u]."
How this will work?
Because we are adding start time of every node in the depth vector, it help us find count of how many values are there from
start_time[u] to end_time[u]at depthd.Don't know if this will help, but here's a what I made during contest.