GALACTIK - Editorial

I was going through a few submissions of this problem. Interestingly, @mugurelionut’s solution seems way too clear than the editorial itself!!

4 Likes

Hello all,
I’m applying this approach…

  1. Use DFS to count number of components and minimum tax of each component.

  2. If any component has all planets having negative taxes, then answer is -1

  3. Otherwise find global min tax value.

  4. Compute result = sum of minimum value of all components + (components-2)*global_min

Is my algo right ??

Using this approach,I’m able to get right answers in all test cases I can think of…still getting WA…

6 Likes

DFS is much easier to handle :slight_smile:

Can anyone please provide a test case where my solution is wrong?? I used DFS…but getting WA…

Someone please help me to figure out why my solution gives a WA.
Link: oM1MVe - Online C++0x Compiler & Debugging Tool - Ideone.com

nice editorial but code was a little messy, dfs is easier though!

Hi please help me out.I am getting WA.Here is my commented


[1]


  [1]: https://ideone.com/Wl3WYn

please have a look at my code ia m using the same logic along with bfs but getting wa

i have solved the question using disjoint set data structure . I have heavily commented my code if anybody wants to solve by using disjoint set and finding difficulty here is my code.

Happy Coding :slight_smile:

5 Likes

can anyone tell me why we did (components-2)*global_min .

2 Likes

can anyone tell me why we did (components-2)*global_min .

could u plz look at CodeChef: Practical coding for everyone its giving wa

I am giving you a test case. Try to figure it out on your own.
7 4
1 2
2 3
1 3
5 6
3
-1
-1
2
6
8
4

1 Like

@tijoforyou Your code does not handle the case for multiple paths with the same vertex, or is it so?
When (1->3); then (3->2); and then (2->1) is given as the paths, your code would store it as 1(->2), 2(->1) and 3(->2) as the final list for DFS.
Could you clarify how this does not change the correctness of the solution?

@programme I am using adjacency list representation. When (1->3); then (3->2); and then (2->1) is given as the paths, my code would store it as 1(->2->3), 2(->1->3), 3(->2->1). (For each edge <u, v>, I add u at the front of the adjacency list of v, and v at the front of the adjacency list of u.

@tijoforyou I really appreciate your help, I finally figured it out. Thanks again!

@programme We are all here to learn and help each other. Happy to help! :smiley:

“If any component has all planets having negative taxes, then answer is -1”

What if this is true, but there is only one component? Then, surely, the answer is 0 and not -1.

Have you checked this case?

6 Likes

Apart from this, the steps you said are right.

thanks bro, for your help…now it got accepted.