Hi,

Problem
My solution

I made a segment tree with a slight modification to the merge function from merge sort. The recurrence should come to:

Which should be O(n lg n), for the initial building part. For each query it would take O(lg n) right? Why is this timing out? I made a huge test case and it kept running for like a minute. I tried fast i/o, tried to store results and output later, and converted the vector to list but nothing worked.

Is my analysis wrong? How do I make it faster? Please help.

Problem: Cman and Candies

So when I saw the constraint that C[i] is a positive integer below 1e5, I immediately thought of a segment tree solution. My segment tree nodes store the number of "active" elements in the range that it represents and the sum of all those elements.

So we see an element we sum up all of the elements that are lesser than it, and let's call it lsum. As we know how many numbers were added to get lsum, we can easily calculate one part of the answer. Let's do a similar thing for the numbers greater than the current one, that we have already seen and call it rsum.

The answer must be: (Number of things less than current element)*(current element) — lsum + rsum — (number of elements more than this element)*(current element)

CODE

It gives me a WA. Please tell me what is wrong with my approach/implementation and if there is a simpler method to approach this problem.

Thanks and happy new year :)

Problem: RANKFRAUD

The problem can be framed as a graph problem, to find hamiltonian path in the graph. As the graph is a tournament graph, the path can be found in polynomial time.

My Solution

My solution uses the algorithm described here, but it gives me a WA for four cases. I am not able to figure out why my implementation is wrong.

When I inserted the asserts I got a SIGABRT, meaning the portion with the got variable is failing somehow. Shouldn't there always be a vertex j such that path[j]->i and i->path[j+1]?

Let's assume there is not such a vertex and that path[path.size()-1] does not connect to i and i does not connect to path[0]. If it does the other two ifs should handle that in the code. Then we have a case where path[0] defeats i and i defeats path[path.size()-1]. If we assumed that no element j in path exists such that path[j] defeats i and i defeats path[j+1], then for all j the case must be either that path[j] and path[j+1] both are defeated by i OR path[j] and path[j+1] both defeat i. In the first cases, all indices 1..path.size()-1 must get defeated by i, but we know that path[0] defeats i so we have found a place to insert i. A similar argument goes the other way for the last element in path.

What is wrong with my reasoning?

Hi,

I tried to solve this question: Problem using a DFS procedure with an extra variable recording the number of consecutive cats we have seen till now.

Code

This code returned Wrong answer on test case 9. I cannot find test cases for which this solution returns wrong answer. I also tried converting variables to long long in case int was overflowing, but no luck. After some thought I realized there could be a scenario in the problem where visiting a node "cleanses" us of all cats seen. Then we could go back through the parent to the other leaves, with a reduced m.

I implemented it this way: Code

I basically record the best cats_seen that has been obtained till now and if we can beat that we visit the node again. However this too returns WA on test case 9.

Please help me debug this.

Also, general question, till what constraint (of n) is recursive DFS feasible? Meaning it won't cause a stack overflow? I'm not sure where to find help debugging my solutions, so I'm posting it on my blog. Please do give me a link if there's a dedicated place for this, because it would be really nice to have one.