C++

Forum

 
Reposting the error in my code ...

Maggi Iggam (123)
I am reposting my question as i am not getting any answers or corrections in my code . Please help me its eating me up !
Here is the question:-
Problem 2: The Leaf Eaters, (Tanmoy Chakraborty, CMI)
As we all know caterpillars love to eat leaves. Usually, a caterpillar sits on leaf, eats as much of it as it can (or wants), then stretches out to its full length to reach a new leaf with its front end, and finally "hops" to it by contracting its back end to that leaf.
We have with us a very long, straight branch of a tree with leaves distributed uniformly along its length, and a set of caterpillars sitting on the first leaf. (Well, our leaves are big enough to accommodate upto 20 caterpillars!). As time progresses our caterpillars eat and hop repeatedly, thereby damaging many leaves. Not all caterpillars are of the same length, so different caterpillars may eat different sets of leaves. We would like to find out the number of leaves that will be undamaged at the end of this eating spree. We assume that adjacent leaves are a unit distance apart and the length of the caterpillars is also given in the same unit.
For example suppose our branch had 20 leaves (placed 1 unit apart) and 3 caterpillars of length 3, 2 and 5 units respectively. Then, first caterpillar would first eat leaf 1, then hop to leaf 4 and eat it and then hop to leaf 7 and eat it and so on. So the first caterpillar would end up eating the leaves at positions 1,4,7,10,13,16 and 19. The second caterpillar would eat the leaves at positions 1,3,5,7,9,11,13,15,17 and 19. The third caterpillar would eat the leaves at positions 1,6,11 and 16. Thus we would have undamaged leaves at positions 2,8,12,14,18 and 20. So the answer to this example is 6.
Input format
The first line of the input contains two integers N and K, where N is the number of leaves and K is the number of caterpillars. Lines 2,3,...,K+1 describe the lengths of the K caterpillars. Line i+1 (1 ≤ i ≤ K) contains a single integer representing the length of the ith caterpillar.
You may assume that 1 ≤ N ≤ 1000000000 and 1 ≤ K≤ 20. The length of the caterpillars lie between 1 and N.
Output format
A line containing a single integer, which is the number of leaves left on the branch after all the caterpillars have finished their eating spree.
Test Data:
The range of input values over which your pragram is to be tested is described above. In addition, 50% of the test-cases will also satisfy 1 ≤ N≤ 10000000 and K ≤ 16.
Example:
We now illustrate the input and output formats using the example described above.
Sample Input:
20 3
3
2
5
Sample Output:
6
Hint:
You may use 64-bit integers (long long int in C/C++) to avoid errors while multiplying large integers. The maximum value you can store in a 32-bit integer is 2^31-1, which is approximately 2 * 10^9. 64-bit integers can store values greater than 10^18.


And here is my solution code :-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
#include <iostream>
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    int leafs[(n+5)],cp[k],i,o,s=0;
    for (i=0;i<(n+5);i++) leafs[i]=5;
    for (i=0;i<k;i++) {
        cin>>cp[i];
        for (o=1;o<n;o=o+cp[i]) {
            if (!(leafs[o]==1)) {leafs[o]=1;s++;}
        }
    }
    cout<<(n-s);
}


Its running well in my computer but when i submit the code , it gives an message saying segmentation fault . Can anybody Please Help . And thanks to developer of this fantastic site , its my favourite !
Gaminic (1621)
int leafs[(n+5)],cp[k];
That won't work in C++. In fact, it shouldn't even compile.

You can either use static allocation of arrays, in which case 'n' and 'k' have to be constants, or dynamic allocation of arrays, using the "new" operator to allocate (and "delete" to deallocate) memory.

Alternatively, use std::vector or std::valarray to use the above without the hassle of memory management.
Maggi Iggam (123)
Actually that works perfectly well not only in this but also in my other programs !
And i can't understand much of what you have said , can you please edit & show ???
Gaminic (1621)
Can you show one of those programs where that works? Because it most definitely shouldn't.

This is wat MSVC++ shows:
error C2057: expected constant expression
error C2466: cannot allocate an array of constant size 0
error C2133: 'leafs' : unknown size

Dynamic allocation would look like this:
1
2
3
4
5
 
int *leafs = new int[(n+5)], *cp = new int[k], i,o,s=0;
// ...
cout<<(n-s);
delete[] leafs, cp;
return 0;
Maggi Iggam (123)
Hey Gaminic !!! That worked !!!
But when it was giving ABORTED (got SIGABRT) , so i tried to add long before int in line 6 after replacing it with line 1 of your suggested code .
But then it is giving this compilation error :-
"/aux/home/opc/backend/data/uploads/3/553: In function ‘int main()’:
/aux/home/opc/backend/data/uploads/3/553:6: error: invalid conversion from ‘int*’ to ‘long int*’
/aux/home/opc/backend/data/uploads/3/553:6: error: invalid conversion from ‘int*’ to ‘long int*’
/aux/home/opc/backend/data/uploads/3/553:15: warning: right-hand operand of comma has no effect"
Please help me once again & thanks for your help !!! You got me some peace !
aquaz (170)
I guess you didn't add long before new int. line 1 should look like:
 
 
long int *leafs = new long int[(n+5)], *cp = new long int[k], i,o,s=0;

And be careful with line 15, you should write it as:
1
2
 
delete[] leafs;
delete[] cp;

The standard form of delete discard arguments after the comma.

For the fact that int leafs[(n+5)] compile it is because i guess you are using gcc which support C99, in which you can declare variable size stack array and it crash because k is too high. MSVC doesn't support fully C99, that's why Gaminic can't compile your exemple.
Maggi Iggam (123)
Oh thankyou , it works !
But can you help me in getting out from another error of this program .
This works absolutly fine in first 5 test cases , but then from 5th to 9th it gives runtime error abrt ?

"Test Case #5 for 10 points
Runtime Error: ABRT
Description: Aborted (got SIGABRT)
Runtime: 0.01"

Why is it occuring and how can it be removed ???
aquaz (170)
Your problem says that N can be over 10 000 000 for 50% of the test. I'm not sure your system will let you allocate 1 GB of contiguous memeory so i's not surprising if last 5 tests fail.

Maybe you should think of another way of computing the number of remaining leaf, without array of int.
Perhaps a bitset will work as it uses far less memory but again not sure if it can hold so much data (link: http://www.cplusplus.com/reference/stl/bitset/ ).
Last edited on
Maggi Iggam (123)
Umm... well is there no other way , to handle 10 000 00 input ? (other than changing whole of my program) ???

And also aquaz , your link is dead .
aquaz (170)
Sorry, i changed the link.

I tested with bitset, it works but it is awfully slow for big caterpillars so i think the solution is with some arithmetics, no arrays. So if yoy really want to pass the 5 last tests I guess you have to change the whole of your programm, I doubt you can pass with a solution which take 2 minutes to execute.

I don't know very much arithmetics but your problem advise you to use long int to do multiplications so it is clear your solution is not the expected one
sockless (5)
Just skimming over the problem, it looks like you're solving it wrong.

Using arrays is not the right way to go about this problem, the first thing that comes into my head on how to solve it is to use a for loop from 0 to n, and inside it checks if the number is divisible by any of the caterpillar leaves, if it isn't, increment a count.

Something like this (assume you have an array or a vector with the lengths of the caterpillars in it called caterpillars):

1
2
3
4
5
6
7
8
9
10
11
12
 
for (int i = 1; i < n; i++)
{
    count++;
    for (int j = 0; j < caterpillars.size(); j++)
    {
        if (i % j == 0)
        {
            count--;
            break;
        }
    }
}



Hope that makes sense to you, ask away if it doesn't.
Maggi Iggam (123)
Well , i got a fair idea of what you are saying 'sockless' , but i couldn't get exactly what you said .
Here's my code that doesn't handles values above 1000000000 :-

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
#include <iostream>
using namespace std;
int main(){
    long long int n,k;      //Here n is number of leaves & k is number of caterpillars present
    cin>>n>>k;
    int *leafs = new int[(n+5)], *cp = new int[k], i,o,s=0; //i & o are counter variables for my loop & s is the count of leaves eaten
    for (i=0;i<(n+5);i++) leafs[i]=5;  //storing any constant in all leaves position(in order to avoid error)
    for (i=0;i<k;i++) {
        cin>>cp[i]; //storing lengths of caterpillars in array cp
        for (o=1;o<n;o=o+cp[i]) {
            if (!(leafs[o]==1)) {leafs[o]=1;s++;}
        }
    }
    cout<<(n-s); //printing (total number of leaves-leaves eaten) , ie leaves left unharmed
}


Can you please now make merge your code snippet here ?
Thankyou 'sockless' for helping me .
sockless (5)
Try this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
#include <iostream>
#include <vector>
using namespace std;
int main(){
    long long int n,k;      //Here n is number of leaves & k is number of caterpillars present
    int count;
	cin>>n>>k;
	
	vector<int> caterpillars;
	for (int i = 0; i < k; i++)
	{
		int foo;
		cin>>foo;
		caterpillars.push_back(foo);
	}
	
	for (int i = 1; i <= n; i++)
	{
		count++;
		for (int j = 0; j < caterpillars.size(); j++)
		{
			if (i % j == 0)
			{
				count--; //if we find that the leaf has been eaten by a 'pillar, we don't need to check the rest of them
				break;
			}
		}
	}
		
    cout<<(count);
    return 0;
}


I'm not sure that that exactly would work, but something like that.

Also, just some other comments on your code, you can initialise variables in for loops e.g. for (int i = 0; i < 10; i++)

It's only in C that you can't do that.

I personally prefer to have each declaration of an array on a new line, just because it improves readability. I also try to out each statement on a new line, space is one of the things you don't have to worry about, so try to expand your code to make it as readable as possible.

Try to space out your code across the page too, so adding spaces between operators, I find it helps avoid impenetrable blocks of code.

Another handy tip is the += operator, i += 4 is equivalent to i = i + 4. Also, instead of using ints for your array of leaves, you could use bools, instead, since you are only storing 1 value.

With your if statement, you can also do !=, which is "not equal", equivalent to !(a == b), but easier to read.

I've modified your original code to show how I would have written it:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
#include <iostream>
using namespace std;
int main(){
    long long int n,k;//Here n is number of leaves & k is number of caterpillars present
    cin>>n>>k;
    int *leafs = new int[(n+5)], 
	int *cp = new int[k],
	int s = 0; //i & o are counter variables for my loop & s is the count of leaves eaten
	
    for (int i = 0; i < (n + 5); i++) 
	{
		leafs[i] = 1;  //storing any constant in all leaves position(in order to avoid error)
	}
	
    for (int i= 0; i < k; i++) 
	{
        cin>>cp[i]; //storing lengths of caterpillars in array cp
        for (int o = 1; o < n; o += cp[i]) 
		{
            if (leafs[o] != 0) 
			{
				leafs[o]=0;
				s++;
			}
        }
    }
    cout<<(n-s); //printing (total number of leaves-leaves eaten) , ie leaves left unharmed
    return 0;
}


A lot of programmers don't put opening curly braces ({) on a new line, but I find it helps me.

Oh, and make sure you put return 0; at the end of your code, some marking machines (ie the one I'm using), don't like it when you omit it.

I'm not trying to be harsh, but I'm trying to make sure you learn good habits before you get stuck with bad ones.
Maggi Iggam (123)
Yeah thanks for advice , but dude i am still getting stuck upto test case 5 !!! And the same error !!!
"Test Case #6 for 10 points
Runtime Error: ABRT
Description: Aborted (got SIGABRT)
Runtime: 0.01"

Anyway thanks for trying to help me .
Gaminic (1621)
Did you actually change anything since the last advice posts? If you haven't actually gotten rid of n-sized arrays, chances are you'll never get it working.
sockless (5)
Did you try a straight copy+paste of the top section of code that I gave you? (the one with #include<vector>)
sockless (5)
Also, could you link me to the problem site?
<edit> I found a solution for you if you're really stuck and want a look: http://www.iarcs.org.in/inoi/contests/sep2004/Advanced-2-solution.php

It doesn't cover code, just how it's done.
Last edited on
Maggi Iggam (123)
Oh thanks 'sockless' , that link was GREAT !!!!
Now you have made my job a lot easier ! Thankyou man .
yes , the problem site is "http://opc.iarcs.org.in" officially for indians but foriegners are also allowed .
Last edited on
Topic archived. No new replies allowed.