zco 2012 problem WORMHOLES

problem
zco
zio

#1

can anybody help me with the question of zcp 2012 wormhole

http://www.iarcs.org.in/inoi/2012/zco2012/zco2012-1b.php


#2

Sort all Wormhole starting times and wormhole ending times. Sort all tests by their starting times then for all contests calculate total time. Use vectors and sort if you are using c++.
Also, can you check out ZIO 2009’s first question. Tell me if you get a good solution to the problem …


#3

I’m getting Wrong Answer for 1 test case in Subtask 1 and 2 test cases in Subtask 2 in this WORMHOLES problem thus resulting in a total score of 0/100. I don’t think time limit is a problem as I used binary search so it should max take 2N(log N) iterations (sorry I am unsure of the proper notation, I suppose it is O(2NlogN)) which will be fine I guess. Still, suggestions are welcome.

My code’s here:https://www.dropbox.com/s/qzwfagv2q9yye51/WORMHOLES.docx?dl=0

Could someone please help me understand my error, or better, provide a test case for which this code doesn’t work?

P.S. If the link’s inconvenient, I am sorry, I tried using the tags to insert my code, but it was looking so ugly in the end.


#4

My code is basically the same as what Organic-Shilling has suggested above, and it works fine for all of the test cases I’ve thought up. On the server, it’s giving an incorrect answer on three problems in Subtask 1 and one in Subtask 2, and timing out on 4 problems in Subtask 2. I know I can use binary search instead of a linear one to reduce the time complexity, but I have no idea on how to fix the wrong answers.

It would be really helpful if someone could take a look at my code and tell me where I’m going wrong.

Here’s a link to my

code.


#5

Even I am having trouble with the problem. Here’s my code that works but exceeds time limit
http://pastebin.com/UUzJRtFP
Here’s my buggy code where time limit is taken care of but it gives wrong answer: http://pastebin.com/ytrq7xsc . I am also desperate for help.


#6

I cannot understand why @sany999 's code does not work. I have submitted my code, our logic looks the same,and I too am facing the same problem with score 0/100


#7

I’ve managed to get 100/100. Here’s my code.. No comments, I’m afraid.


#8

i am getting wrong answer for task 2,4,7,8,11,12,13
here is my code

#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>

using namespace std;
int cal(vector<pair<int, int> >, vector<int>, vector<int>,int);
int largest(vector<int>, int);
int smallest(vector<int>, int);
int main()
{
	vector<pair<int, int> > contest;vector<int>v;vector<int>w;
	int a1, a2;
	
	int a, v_a, w_a;
	cin >> a >> v_a >> w_a;

	
	
	for (int i = 0; i < a; i++)
	{
		cin >> a1>>a2;
		contest.push_back(make_pair(a1,a2));
		


	}
	sort(contest.begin(),contest.end());
	for (int i = 0; i < v_a; i++)
	{
		cin >> a1;
		v.push_back(a1);
	}
	for (int i = 0; i < w_a; i++)
	{
		cin >> a1;
		w.push_back(a1);
	}
	sort(v.begin(), v.end());
	sort(w.begin(), w.end());
	a = cal(contest, v, w, a);

	
	cout << a;
    return 0;
}
int cal(vector<pair<int, int> > contest, vector<int> v, vector<int> w,int a) {
	int x, y, z;int total,store=100000;
	for (int i = 0; i <a; i++) {
		x = contest*.first;
		
		y = smallest(v, x);
		
		x = contest*.second;
		z = largest(w, x);
		
		total = (z - y + 1);
		if (total < store) {
			store = total;
			
		}
		
	}
	return store;



}
int largest(vector<int>w_a, int number) {
	int a;
	for (int i = 0; i < (int)w_a.size(); i++)
	{
		
		if (number <= w_a*) {
			a = w_a*;
			break;

		}
		if (i < (int)w_a.size()) {
			a = w_a.back();
		}
	}
	return a;
}
int smallest(vector<int>v_a, int number) {
	int a;
	for (int i = 0; i < (int)v_a.size(); i++)
	{
		if(number < v_a* && i==0){
       	 a=v_a[0];
	   }
		if (number <= v_a*) {
			i--;
			a = v_a*;
			break;
		}
       
	}
	return a;


}

#9

guys, please upvote me. i am new here. nad not able to ask question


#10

I have solved it in java. I am getting subtask 1 right but getting a runtime error in subtask 2 task 8 , 12 , 13 , 14 , 15 and time limit exceeded in task 9. So my final score is 30/100.

Please help

My code is

https://www.codechef.com/viewsolution/15901611


#11

Could someone please at least provide a border test case for which the above code doesn’t work?


#12

Could you suggest some border cases which you think are probably missed out by most people?