FIRESC - Editorial

editorial
, , , ,
31

Whats wrong with this CodeChef: Practical coding for everyone

32

Please star my projects and contribute if you are interested.

  1. GitHub - armgabrielyan/DiceRoller: Dice Rolling Simulator
  2. https://github.com/ArmenGabrielyan16/SuperLibrary
33

Can someone please point out the mistake in this code?

Code-(CodeChef: Practical coding for everyone)

Thanks :slight_smile:

34

such a nice problem, thank you codechef.

1 Like
35

Used union find but kept getting TLE. Code:gDZvZc - Online C++0x Compiler & Debugging Tool - Ideone.com
Would be really helpful if someone could point out the mistake in this.

36

very good question …

37

You have loop for(int j=i; j<n; j++) after each call to dfs. In the case of no edges in the graph you will have O(N^2) solution. Obviously it should get TLE :slight_smile:

38

@anton_lunyov >> So, if I consider the case of graph consisting of no edges separately, will it run within TL?

39

Replace c[p[i]]++ by c[find(i)]++
p[i] is not always the actual root of the disjoint set containing i.
Namely, after link operation.

1 Like
40

http://www.codechef.com/viewplaintext/1916644

41

No. The graph could have many components, say 90000, and you still will get TLE. Also why you are creating the array visited at each dfs run? This is the worst thing to do. It should be created only once and filled by false before global dfs loop

42

and that is why my code was 270M :frowning:

43

@anton_lunyov >> can you give some large test files, like you did for CHEFHACK?

44

Use ret = ((long long)ret * c) % 1000000007;

45

I used weighted quick union for this, which can be improved further using path compression.
My solution : http://www.codechef.com/viewplaintext/1869801

46

@ anton : Thanks a lot…

47

This might help, https://class.coursera.org/algs4partI-002/lecture/8

48

They both have the same mistake. You do not handle possible overflow in this statement

total = ((total % N)*(count % N) % N;

As you can see, because N is 1000000007, the result of the product might exceed the range of 32-bit integers. You must cast total as long long in C to solve the issue. Cast total to long in JAVA to get AC.

49

Checkout the fixes here.

I could point out two bugs

  • You have to find uniques in the id array. You are simply parsing over it and inserting ‘i’ instead of find(i) in the HashSet.
  • Multiplying everything and storing in a long will potentially overflow. It is fixed by storing the result modulo 1000000007 along the way.
50

Try this test case

1
4 3
1 2
1 3
4 3

You print

2 4

The answer should be

1 4

Can you see how?

2 Likes