EVEDG problem help

my soln
problem -EVEDG
I am getting TLE in task#6 of subtask 1
But all cases in subtask 2 are passing .

I don’t understand how TLE is occurring when the constraint is [2,10] only .Please help.

2 Likes

My guess: it’s the cost of initialising an array of 100001 vectors, 3000 times.

Try replacing:

     vector<int> *ptr;
     ptr=new vector<int> [100001]();
     cin>>n>>m;

with

     cin>>n>>m;
     vector<int> *ptr;
     ptr=new vector<int> [n + 1]();
2 Likes

@ssjgz I wanted to test it on my machine to see how long it really takes.

Here's the code
	#include <iostream>
	#include <vector>
	#include <chrono>
	using namespace std::chrono;
	using namespace std;

	int main (void) {
		auto start = high_resolution_clock::now();
		vector<int>* V;
		for (int i = 0; i < 1'00'000; ++i) {
			V = new std::vector<int>(1'00'000);
		}
		auto stop = high_resolution_clock::now();
		auto duration = duration_cast<microseconds>(stop - start);
		cout << "Time taken by function: " << duration.count() << " microseconds" << endl;
	}

My machine literally froze for like 10 whole minutes! How do I test such code safely? Thank you. :slightly_smiling_face:

1 Like

Keep your fingers hovering over CTRL+C :wink:

Not sure, really - the best approach is not to write such code in the first place - the major problem here is that V is never deleted, which would not be the case if we used a vector<vector<int>> instead of directly using new. Edit: Actually, in the code you wrote, I mean that V should just be a vector<int>, declared inside the inner loop - doh.

Probably under UNIX there’s some way of restricting the maximum RAM usage of a process we’re about to launch(?), but I’ve not looked into it :slight_smile:

Edit:

This looks interesting - might give it a try in mo :slight_smile:

Edit2:

That seems to work quite nicely :slight_smile:

2 Likes

I don’t have any idea what’s wrong with my system, but it really it took me 10 minutes of ctrl + C-ing and alt + ctrl + delete-ing (Task Manager) to stop the process XD.

Thank you for the explanation. :slightly_smiling_face:

I guess the time has come for me to say Bye Bye to my Windows. RIP.

1 Like

Do you have a HDD or an SSD? If my laptop had had an HDD, I’d probably still being try to kill the rogue process even now, whether on Linux or Windows :slight_smile:

1 Like

I’m afraid it’s an HDD. I feel lucky, now that it’s dead. Welcome back Windows! XD

1 Like

Here’s a concrete testcase that illustrates the problem: don’t run it unless you want to bring your machine to a standstill!

WARNING - DO NOT RUN - WARNING - DO NOT RUN

Don’t run this testcase XD

1 Like

Thank you so much .You’re right

1 Like

Hey ,same problem as shreyas_that. Can you please have a look at my friend’s code as well. It could get only 70pts in it.
https://www.codechef.com/viewsolution/27343541

1 Like

What exactly is the problem over here?

Leaks memory (so takes up a huge amount of RAM), but even if you cleaned up the memory leaks, initialising 100’001 vectors 3000 times takes up much more than 1 second.

1 Like

Can you look in the code which i mentioned above. There is no repeated initialization yet it gives WA. Everything is global. Any idea what the issue maybe?

Not yet - I haven’t gotten it to fail on my randomised testcases, but they only check for whether you have correctly answered the question of how many subgraphs are needed - it doesn’t check whether the subgraph decomposition the program outputs is correct.

Edit:

Just triggered a wrong answer - haven’t quite been able to isolate why yet, though.

1 Like

Oh!
Please let me know if when you figure out on which test case and why it fails if possible.
Thanks!

1 Like

Linux use timeout command

1 Like

That was strange. Ok, here’s a testcase which seems to fail: it needs only two subgraphs.

1
9 7
1 6
1 4
4 5
7 9
7 8
8 9
4 6

Edit:

Not going to attempt to debug why - I’ll leave that up to you guys XD

2 Likes

Thankyou i will debug it now.

1 Like