AUG18 - Problem Discussion

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ā€¦

My submission

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 .

pseudo orange

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

Codechef wont let me become orange this easily :frowning:

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

1 Like

Check out this type of case- [4,4,4,3,4,4,4]. For K>0 the sequence B should be of form [2,2,2,1,2,2,2] instead of [1,1,2,1,2,2,2].

No, the main constraint said they will be greater than 1.

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.

Total queries =2n+1+lognlogn

Can someone please discuss their approach for princess and dragon problem? Thank you

1 Like

According to my calculations, itā€™s (25/8)*N queries on average.

You can have a look here, https://drive.google.com/open?id=1UqZF6zDOYlLcEtrPkMWjpJuUbeQXfWut

1 Like

@avijit_agarwal after solving INMAT: link

1 Like

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)

For all those wondering why their solution fails for lonely cycle.

Try this input:

1
14 14
1 2
2 3
3 4
4 1
4 5
5 6
6 7
7 5
6 8
6 9
8 10
10 11
11 12
12 13

Output should be:
1
1
2
2
11
14
7
2
25
9
24
21
16
9

2 Likes

Iā€™m not able to access LONCYC and KCOMPRES Editorials. @admin please help.

My long long int passed fortunately xD

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

Try tomorrow.

Iā€™m talking of worst caseā€¦