For LONELY CYLCES I constructed a spanning tree of graph such that any edge which is not included in it connects u and v such that (lca(u, v) != u and lca(u, v) != v).
Then I marked all the edges which are part of cycles as blocked and which are not in spanning tree as red.
Then I just ran dfs to calculate the number of possible vertices I can reach from a given verices using dpdown - when I go down, dpup -> dp up taking care that I never visit more than 1 blocked edge.
Then calculated the answers for each type of edge, normal , red, blocked accordingly
I tried a lot of test cases and on each I was getting the right answer still got WA. If anybody can point out what I am missingā¦
In the princess and dragons problems can the values of the dragon strengths be negative?? I tried to solve the problem for the first 3 subtasks but got WA on the 2nd and 3rd but the first one passed. I am having this confusion because although it says the main constraint is 1ā¤Siā¤105 but in the constraints of the subtask 3 which i got WA on says Siā¤2,000 , nothing mentioned about the lower limit . Thank you .
I solved GCDMOD with a greedy approach, still cant prove that is right but i got AC
A = gcd( a^n+b^n, |a-b| ) = gcd( a^n + b ^n , |a-b|, a^n - b ^n) : assume: a>b, if(a=b) its simple
=> A= gcd( 2a^n, 2 b^n, |a-b|) = gcd ( 2*gcd(a,b)^n, |a-b|) so now its simple
LOL. I used your approach one except for my search function (which selected rows to search) involved statistics and interval heuristics. I thought it was dumb of me to get AC that way but now Iām feeling good :3
I donāt think this was the intended solution, but in the GCDMOD problem, we get the same answer whenever n > 1. If n >= 2, set n = 2 and print the answer directly. Only special case is a == b, in which the answer is 2 \times a^n. Hereās my AC Submission.
Can anyone prove why this works?
Can the interactive matrix problem be solved by the following approach.
First 2*n queries to determine the nature of the rows and columns(increasing or decreasing)
Now,
Select a mid=(l+r)/2;
now in the column mid apply a binary search to find the range in which possible value of key can lie
now in the row mid apply a binary search to find the range in which possible value of key can lie
Select only those cells which are part of both row and column range and make a new matrix of only these cells.
Continue the process till only 1 element exists.
For lonely cycle, I am not able to find a test case where my logic goes wrongā¦ My submission is-submission
My logic goes as suchā¦ For each node x, I find in and out which are pairsā¦ 1st index stores without cycle 2nd stores with cycleā¦in[x] means within the subtree of node x and also considering xā¦ for this I merge its childrenās āinā values and also some node in its subtree from which there is back-edge to x.
Out[x] position means same as aboveā¦It means the nodes we can visit in the tree except its subtree but including the node itselfā¦for this I merge its parentās out and also itās siblings inā¦Also in case of back-edge from x to some node higher in the dfs traversal tree, I merge its outā¦
For answer, consider for edge (a-b)
case (i):(a is dfs_par[b] or vice versaā¦ and not part of same cycle) answer is (in[b])*(merge(out[a], sibling[b]))
case (ii):(neither is parent of other but are part of cycle connected by back-edge)answer is (in[b])*(out[a]) (consider a comes before b in dfs traversal)
Seems promising but how will you exactly carry out this step-
now in the column mid apply a binary search to find the range in which possible value of key can lie now in the row mid apply a binary search to find the range in which possible value of key can lie
