TLE in FOXLINGS SPOJ
up vote
0
down vote
favorite
Problem Statement: FOXLINGS
It’s Christmas time in the forest, and both the Fox and the Wolf
families are celebrating. The rather large Fox family consists of two
parents as well as $N$ ($1 leq N leq 10^9$) little Foxlings. The
parents have decided to give their children a special treat this year
– crackers! After all, it’s a well-known fact that Foxen love
crackers.
With such a big family, the parents can’t afford that many crackers.
As such, they wish to minimize how many they give out, but still
insure that each Foxling gets at least a bit. The parents can only
give out entire crackers, which can then be divided and passed around.
With this many children, not all of them know one another all that
well. The Foxlings have names, of course, but their parents are
computer scientists, so they have also conveniently numbered them from
$1$ to $N$. There are $M$ ($1 leq M leq 10^5$) unique two-way
friendships among the Foxlings, where relationship $i$ is described by
the distinct integers $A_i$ and $B_i$ ($1 leq A_i,B_i leq N$),
indicating that Foxling $A_i$ is friends with Foxling $B_i$, and vice
versa. When a Foxling is given a cracker, he can use his tail to
precisely split it into as many pieces as he wants (the tails of Foxen
have many fascinating uses). He can then pass these pieces around to
his friends, who can repeat this process themselves.
Input
Line 1: 2 integers, $N$ and $M$
Next $M$ lines: 2 integers, $A_i$ and $B_i$, for $i=1ldots M$
Output
A single integer – the minimum number crackers must be given out, such
that each Foxling ends up with at least a small part of a cracker.
From the question I attempted with disjoint sets. I applied union by size along with path compression. But the constraints are very high and I could not think how to optimize this further. Offcourse I am getting TLE with solution upon submitting. So can anyone tell me any trick or idea regarding optimization?
public static void main(String argh) throws Exception{
// BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Reader br= new Reader();
int n= br.nextInt();
int m= br.nextInt();
int dj= new int[n+1];
int size= new int[n+1];
for(int i=1; i<=n; i++){
dj[i]= i;
size[i]= 1;
}
HashMap<Integer, Integer> map= new HashMap<>();
int count=0;
for(int i=0; i<m; i++){
int n1= br.nextInt();
int n2= br.nextInt();
union(dj, size, n1, n2);
}
for(int i=1; i<=n; i++){
findParent(dj, i);
}
for(int i=1; i<=n; i++){
if(!map.containsKey(dj[i])){
count++;
map.put(dj[i], 1);
}
}
System.out.println(count);
}
private static int findParent(int arr, int pos){
if(arr[pos] == pos) return pos;
return arr[pos]= findParent(arr, arr[pos]);
}
private static void union(int arr, int size, int pos1, int pos2){
int posP1= findParent(arr, pos1);
int posP2= findParent(arr, pos2);
if(posP1 != posP2){
if(size[posP1] < size[posP2]){
int temp= posP1;
posP1= posP2;
posP2= temp;
}
arr[posP2]= posP1;
size[posP1] += size[posP2];
}
}
Note: Reader is just another fast inputting
java programming-challenge time-limit-exceeded
bumped to the homepage by Community♦ 16 hours ago
This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.
add a comment |
up vote
0
down vote
favorite
Problem Statement: FOXLINGS
It’s Christmas time in the forest, and both the Fox and the Wolf
families are celebrating. The rather large Fox family consists of two
parents as well as $N$ ($1 leq N leq 10^9$) little Foxlings. The
parents have decided to give their children a special treat this year
– crackers! After all, it’s a well-known fact that Foxen love
crackers.
With such a big family, the parents can’t afford that many crackers.
As such, they wish to minimize how many they give out, but still
insure that each Foxling gets at least a bit. The parents can only
give out entire crackers, which can then be divided and passed around.
With this many children, not all of them know one another all that
well. The Foxlings have names, of course, but their parents are
computer scientists, so they have also conveniently numbered them from
$1$ to $N$. There are $M$ ($1 leq M leq 10^5$) unique two-way
friendships among the Foxlings, where relationship $i$ is described by
the distinct integers $A_i$ and $B_i$ ($1 leq A_i,B_i leq N$),
indicating that Foxling $A_i$ is friends with Foxling $B_i$, and vice
versa. When a Foxling is given a cracker, he can use his tail to
precisely split it into as many pieces as he wants (the tails of Foxen
have many fascinating uses). He can then pass these pieces around to
his friends, who can repeat this process themselves.
Input
Line 1: 2 integers, $N$ and $M$
Next $M$ lines: 2 integers, $A_i$ and $B_i$, for $i=1ldots M$
Output
A single integer – the minimum number crackers must be given out, such
that each Foxling ends up with at least a small part of a cracker.
From the question I attempted with disjoint sets. I applied union by size along with path compression. But the constraints are very high and I could not think how to optimize this further. Offcourse I am getting TLE with solution upon submitting. So can anyone tell me any trick or idea regarding optimization?
public static void main(String argh) throws Exception{
// BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Reader br= new Reader();
int n= br.nextInt();
int m= br.nextInt();
int dj= new int[n+1];
int size= new int[n+1];
for(int i=1; i<=n; i++){
dj[i]= i;
size[i]= 1;
}
HashMap<Integer, Integer> map= new HashMap<>();
int count=0;
for(int i=0; i<m; i++){
int n1= br.nextInt();
int n2= br.nextInt();
union(dj, size, n1, n2);
}
for(int i=1; i<=n; i++){
findParent(dj, i);
}
for(int i=1; i<=n; i++){
if(!map.containsKey(dj[i])){
count++;
map.put(dj[i], 1);
}
}
System.out.println(count);
}
private static int findParent(int arr, int pos){
if(arr[pos] == pos) return pos;
return arr[pos]= findParent(arr, arr[pos]);
}
private static void union(int arr, int size, int pos1, int pos2){
int posP1= findParent(arr, pos1);
int posP2= findParent(arr, pos2);
if(posP1 != posP2){
if(size[posP1] < size[posP2]){
int temp= posP1;
posP1= posP2;
posP2= temp;
}
arr[posP2]= posP1;
size[posP1] += size[posP2];
}
}
Note: Reader is just another fast inputting
java programming-challenge time-limit-exceeded
bumped to the homepage by Community♦ 16 hours ago
This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.
One who negates . Pls do mention reason.
– Ladoo
Oct 12 at 11:01
Have you tested it? Are you aware there's a lot of looping going on?
– Mast
Oct 12 at 17:31
The code is correct for small N, for big N I learnt new technique dynamic DSU
– Ladoo
Oct 14 at 17:15
With the same code We cannot go for high N. So I was getting tle
– Ladoo
Oct 14 at 17:16
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Problem Statement: FOXLINGS
It’s Christmas time in the forest, and both the Fox and the Wolf
families are celebrating. The rather large Fox family consists of two
parents as well as $N$ ($1 leq N leq 10^9$) little Foxlings. The
parents have decided to give their children a special treat this year
– crackers! After all, it’s a well-known fact that Foxen love
crackers.
With such a big family, the parents can’t afford that many crackers.
As such, they wish to minimize how many they give out, but still
insure that each Foxling gets at least a bit. The parents can only
give out entire crackers, which can then be divided and passed around.
With this many children, not all of them know one another all that
well. The Foxlings have names, of course, but their parents are
computer scientists, so they have also conveniently numbered them from
$1$ to $N$. There are $M$ ($1 leq M leq 10^5$) unique two-way
friendships among the Foxlings, where relationship $i$ is described by
the distinct integers $A_i$ and $B_i$ ($1 leq A_i,B_i leq N$),
indicating that Foxling $A_i$ is friends with Foxling $B_i$, and vice
versa. When a Foxling is given a cracker, he can use his tail to
precisely split it into as many pieces as he wants (the tails of Foxen
have many fascinating uses). He can then pass these pieces around to
his friends, who can repeat this process themselves.
Input
Line 1: 2 integers, $N$ and $M$
Next $M$ lines: 2 integers, $A_i$ and $B_i$, for $i=1ldots M$
Output
A single integer – the minimum number crackers must be given out, such
that each Foxling ends up with at least a small part of a cracker.
From the question I attempted with disjoint sets. I applied union by size along with path compression. But the constraints are very high and I could not think how to optimize this further. Offcourse I am getting TLE with solution upon submitting. So can anyone tell me any trick or idea regarding optimization?
public static void main(String argh) throws Exception{
// BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Reader br= new Reader();
int n= br.nextInt();
int m= br.nextInt();
int dj= new int[n+1];
int size= new int[n+1];
for(int i=1; i<=n; i++){
dj[i]= i;
size[i]= 1;
}
HashMap<Integer, Integer> map= new HashMap<>();
int count=0;
for(int i=0; i<m; i++){
int n1= br.nextInt();
int n2= br.nextInt();
union(dj, size, n1, n2);
}
for(int i=1; i<=n; i++){
findParent(dj, i);
}
for(int i=1; i<=n; i++){
if(!map.containsKey(dj[i])){
count++;
map.put(dj[i], 1);
}
}
System.out.println(count);
}
private static int findParent(int arr, int pos){
if(arr[pos] == pos) return pos;
return arr[pos]= findParent(arr, arr[pos]);
}
private static void union(int arr, int size, int pos1, int pos2){
int posP1= findParent(arr, pos1);
int posP2= findParent(arr, pos2);
if(posP1 != posP2){
if(size[posP1] < size[posP2]){
int temp= posP1;
posP1= posP2;
posP2= temp;
}
arr[posP2]= posP1;
size[posP1] += size[posP2];
}
}
Note: Reader is just another fast inputting
java programming-challenge time-limit-exceeded
Problem Statement: FOXLINGS
It’s Christmas time in the forest, and both the Fox and the Wolf
families are celebrating. The rather large Fox family consists of two
parents as well as $N$ ($1 leq N leq 10^9$) little Foxlings. The
parents have decided to give their children a special treat this year
– crackers! After all, it’s a well-known fact that Foxen love
crackers.
With such a big family, the parents can’t afford that many crackers.
As such, they wish to minimize how many they give out, but still
insure that each Foxling gets at least a bit. The parents can only
give out entire crackers, which can then be divided and passed around.
With this many children, not all of them know one another all that
well. The Foxlings have names, of course, but their parents are
computer scientists, so they have also conveniently numbered them from
$1$ to $N$. There are $M$ ($1 leq M leq 10^5$) unique two-way
friendships among the Foxlings, where relationship $i$ is described by
the distinct integers $A_i$ and $B_i$ ($1 leq A_i,B_i leq N$),
indicating that Foxling $A_i$ is friends with Foxling $B_i$, and vice
versa. When a Foxling is given a cracker, he can use his tail to
precisely split it into as many pieces as he wants (the tails of Foxen
have many fascinating uses). He can then pass these pieces around to
his friends, who can repeat this process themselves.
Input
Line 1: 2 integers, $N$ and $M$
Next $M$ lines: 2 integers, $A_i$ and $B_i$, for $i=1ldots M$
Output
A single integer – the minimum number crackers must be given out, such
that each Foxling ends up with at least a small part of a cracker.
From the question I attempted with disjoint sets. I applied union by size along with path compression. But the constraints are very high and I could not think how to optimize this further. Offcourse I am getting TLE with solution upon submitting. So can anyone tell me any trick or idea regarding optimization?
public static void main(String argh) throws Exception{
// BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Reader br= new Reader();
int n= br.nextInt();
int m= br.nextInt();
int dj= new int[n+1];
int size= new int[n+1];
for(int i=1; i<=n; i++){
dj[i]= i;
size[i]= 1;
}
HashMap<Integer, Integer> map= new HashMap<>();
int count=0;
for(int i=0; i<m; i++){
int n1= br.nextInt();
int n2= br.nextInt();
union(dj, size, n1, n2);
}
for(int i=1; i<=n; i++){
findParent(dj, i);
}
for(int i=1; i<=n; i++){
if(!map.containsKey(dj[i])){
count++;
map.put(dj[i], 1);
}
}
System.out.println(count);
}
private static int findParent(int arr, int pos){
if(arr[pos] == pos) return pos;
return arr[pos]= findParent(arr, arr[pos]);
}
private static void union(int arr, int size, int pos1, int pos2){
int posP1= findParent(arr, pos1);
int posP2= findParent(arr, pos2);
if(posP1 != posP2){
if(size[posP1] < size[posP2]){
int temp= posP1;
posP1= posP2;
posP2= temp;
}
arr[posP2]= posP1;
size[posP1] += size[posP2];
}
}
Note: Reader is just another fast inputting
java programming-challenge time-limit-exceeded
java programming-challenge time-limit-exceeded
edited Oct 12 at 16:38
200_success
128k15149412
128k15149412
asked Oct 12 at 10:48
Ladoo
193
193
bumped to the homepage by Community♦ 16 hours ago
This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.
bumped to the homepage by Community♦ 16 hours ago
This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.
One who negates . Pls do mention reason.
– Ladoo
Oct 12 at 11:01
Have you tested it? Are you aware there's a lot of looping going on?
– Mast
Oct 12 at 17:31
The code is correct for small N, for big N I learnt new technique dynamic DSU
– Ladoo
Oct 14 at 17:15
With the same code We cannot go for high N. So I was getting tle
– Ladoo
Oct 14 at 17:16
add a comment |
One who negates . Pls do mention reason.
– Ladoo
Oct 12 at 11:01
Have you tested it? Are you aware there's a lot of looping going on?
– Mast
Oct 12 at 17:31
The code is correct for small N, for big N I learnt new technique dynamic DSU
– Ladoo
Oct 14 at 17:15
With the same code We cannot go for high N. So I was getting tle
– Ladoo
Oct 14 at 17:16
One who negates . Pls do mention reason.
– Ladoo
Oct 12 at 11:01
One who negates . Pls do mention reason.
– Ladoo
Oct 12 at 11:01
Have you tested it? Are you aware there's a lot of looping going on?
– Mast
Oct 12 at 17:31
Have you tested it? Are you aware there's a lot of looping going on?
– Mast
Oct 12 at 17:31
The code is correct for small N, for big N I learnt new technique dynamic DSU
– Ladoo
Oct 14 at 17:15
The code is correct for small N, for big N I learnt new technique dynamic DSU
– Ladoo
Oct 14 at 17:15
With the same code We cannot go for high N. So I was getting tle
– Ladoo
Oct 14 at 17:16
With the same code We cannot go for high N. So I was getting tle
– Ladoo
Oct 14 at 17:16
add a comment |
1 Answer
1
active
oldest
votes
up vote
1
down vote
for(int i=1; i<=n; i++){
findParent(dj, i);
}
for(int i=1; i<=n; i++){
if(!map.containsKey(dj[i])){
count++;
map.put(dj[i], 1);
}
}
This part is slow and unnecessary - you can count how many times you did union instead.
int dj= new int[n+1];
With 10^9 limit for N, only that line requires 4GB of RAM, when limit for task is 1.5GB. Use HashMap instead and store only unioned ids - there will be at most 2*M of those.
Yes I found that was consuming lot of space and is not suitable for high N
– Ladoo
Oct 14 at 17:17
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
for(int i=1; i<=n; i++){
findParent(dj, i);
}
for(int i=1; i<=n; i++){
if(!map.containsKey(dj[i])){
count++;
map.put(dj[i], 1);
}
}
This part is slow and unnecessary - you can count how many times you did union instead.
int dj= new int[n+1];
With 10^9 limit for N, only that line requires 4GB of RAM, when limit for task is 1.5GB. Use HashMap instead and store only unioned ids - there will be at most 2*M of those.
Yes I found that was consuming lot of space and is not suitable for high N
– Ladoo
Oct 14 at 17:17
add a comment |
up vote
1
down vote
for(int i=1; i<=n; i++){
findParent(dj, i);
}
for(int i=1; i<=n; i++){
if(!map.containsKey(dj[i])){
count++;
map.put(dj[i], 1);
}
}
This part is slow and unnecessary - you can count how many times you did union instead.
int dj= new int[n+1];
With 10^9 limit for N, only that line requires 4GB of RAM, when limit for task is 1.5GB. Use HashMap instead and store only unioned ids - there will be at most 2*M of those.
Yes I found that was consuming lot of space and is not suitable for high N
– Ladoo
Oct 14 at 17:17
add a comment |
up vote
1
down vote
up vote
1
down vote
for(int i=1; i<=n; i++){
findParent(dj, i);
}
for(int i=1; i<=n; i++){
if(!map.containsKey(dj[i])){
count++;
map.put(dj[i], 1);
}
}
This part is slow and unnecessary - you can count how many times you did union instead.
int dj= new int[n+1];
With 10^9 limit for N, only that line requires 4GB of RAM, when limit for task is 1.5GB. Use HashMap instead and store only unioned ids - there will be at most 2*M of those.
for(int i=1; i<=n; i++){
findParent(dj, i);
}
for(int i=1; i<=n; i++){
if(!map.containsKey(dj[i])){
count++;
map.put(dj[i], 1);
}
}
This part is slow and unnecessary - you can count how many times you did union instead.
int dj= new int[n+1];
With 10^9 limit for N, only that line requires 4GB of RAM, when limit for task is 1.5GB. Use HashMap instead and store only unioned ids - there will be at most 2*M of those.
answered Oct 12 at 15:45
user158037
54637
54637
Yes I found that was consuming lot of space and is not suitable for high N
– Ladoo
Oct 14 at 17:17
add a comment |
Yes I found that was consuming lot of space and is not suitable for high N
– Ladoo
Oct 14 at 17:17
Yes I found that was consuming lot of space and is not suitable for high N
– Ladoo
Oct 14 at 17:17
Yes I found that was consuming lot of space and is not suitable for high N
– Ladoo
Oct 14 at 17:17
add a comment |
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f205446%2ftle-in-foxlings-spoj%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
One who negates . Pls do mention reason.
– Ladoo
Oct 12 at 11:01
Have you tested it? Are you aware there's a lot of looping going on?
– Mast
Oct 12 at 17:31
The code is correct for small N, for big N I learnt new technique dynamic DSU
– Ladoo
Oct 14 at 17:15
With the same code We cannot go for high N. So I was getting tle
– Ladoo
Oct 14 at 17:16