FIRESC - Editorial

editorial
, , , ,
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
51

CodeChef: Practical coding for everyone getting wrong ansā€¦really pissed off :frowning: please find the errorā€¦thanx in advanceā€¦

52

Yes rightā€¦ after changing the logic to total = ((total % N)*(count % N) % N;ā€¦ my code also wordedā€¦ huhā€¦
http://www.codechef.com/viewsolution/1927944

53

Hey, am still getting WA. Can you give me any border test case?
http://www.codechef.com/viewsolution/1954203

54

I think all that the .begin() function does is accessing elements on well known positions that are known ahead of time and thus takes constant time, and that gives you no advantage, but maybe doing such modification on the .end() part might help, Im not sure if the gains would be significant though

55

y *= size[i];

Here the value of y can cross the limit of int and hence wrong answer. Make y long long int and you should be fine.

56

Thank you so much! :slight_smile:

57

I m getting SIGSEGV but i dont know why i am getting thisā€¦
intializing like this mark=vector(n,0) i am getting correct answerā€¦
but when i try to do vector mart(n,0) i am getting SIGSEGVā€¦
what is wrong with thisā€¦plz answer meā€¦
http://www.codechef.com/viewsolution/4372844

58

@gamabunta @tijoforyou
i donā€™t know what is the problem in my code and why i am getting a wrong submission
Pls help
#include
#include <bits/stdc++.h>
#include
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define M 1000000007
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while(t > 0)
{
long long n, m , a, b, i , count = 0, j = 0;
cin >> n >> m;
bool visit[n + 1] = {false};
long long freq[n + 1];
vector s;
//unordered_set
memset(freq, 0, sizeof(long long )(n + 1));
for(i = 0; i < m; i++)
{
cin >> a >> b;
if(visit[a - 1] == false && visit[b - 1] == false)
{
visit[a - 1] = true;
visit[b - 1] = true;
freq[a - 1] = i + 1;
freq[b - 1] = i + 1;
}
else if(visit[a - 1] == false)
{
visit[a - 1] = true;
freq[a - 1] = freq[b - 1];
}
else if(visit[b - 1] == false)
{
visit[b - 1] = true;
freq[b - 1] = freq[a - 1];
}
}
sort(freq,freq+n);
//sort(visit, visit+n);
long long flag = 0, f = 0 ;
for(i = 0; i < n; i++)
{
if(i == 0)
{
flag = freq[i ];
count++;
}
else if(flag == freq[i] && freq[i] != 0)
{
count++;
}
else if(flag == freq[i] && freq[i] == 0)
{
s.push_back(count);
count = 1;
}
else if(flag != freq[i])
{
//count++;
s.push_back(count);
flag = freq[i];
count = 1;
}
//cout << freq[i] <<" " << count << " ";
}
// cout << endl;
if(count != 0)
{
s.push_back(count);
}
long long cap = 1;
for(i = 0; i < s.size(); i++)
{
cap = (caps[i]) % M;
if(cap > M)
{
cap %= M;
}
}
//cout << endl;
cout << s.size() <<" " << cap << endl;
t -= 1;
}
}

59

I used Kosaraju algorithm for this question.
**My solution - **https://www.codechef.com/viewsolution/28336210

60

can you tell me for which test cases this code is failing
https://www.codechef.com/viewsolution/29105726