You are not logged in. Please login at www.codechef.com to post your questions!

×

zco 2012 problem WORMHOLES

can anybody help me with the question of zcp 2012 wormhole

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

asked 28 Nov '14, 20:21

praked's gravatar image

2★praked
275
accept rate: 0%

edited 30 Nov '14, 15:48


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 ..

link

answered 28 Nov '14, 22:04

Organic-Shilling's gravatar image

0★Organic-Shilling
9318
accept rate: 11%

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

link

answered 05 Dec '14, 22:16

achintya75's gravatar image

1★achintya75
5115
accept rate: 12%

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

(05 Dec '14, 22:30) sandy9993★

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.

link

answered 01 Dec '14, 16:24

sandy999's gravatar image

3★sandy999
38111235
accept rate: 10%

edited 02 Dec '14, 16:11

1

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

(03 Dec '14, 15:36) sandy9993★

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.

link

answered 03 Dec '14, 17:32

achintya75's gravatar image

1★achintya75
5115
accept rate: 12%

edited 03 Dec '14, 17:32

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.

link

answered 04 Dec '14, 02:17

Organic-Shilling's gravatar image

0★Organic-Shilling
9318
accept rate: 11%

edited 04 Dec '14, 02:18

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

link

answered 05 Dec '14, 00:08

swagatochatt's gravatar image

0★swagatochatt
1536
accept rate: 0%

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[i].first;

        y = smallest(v, x);

        x = contest[i].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[i]) {
            a = w_a[i];
            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] && i==0){
         a=v_a[0];
       }
        if (number <= v_a[i]) {
            i--;
            a = v_a[i];
            break;
        }

    }
    return a;


}
link

answered 21 Apr, 01:14

subho0ace's gravatar image

0★subho0ace
1
accept rate: 0%

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

link

answered 21 Apr, 03:05

thinkinfinit's gravatar image

1★thinkinfinit
672
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×448
×169
×50

question asked: 28 Nov '14, 20:21

question was seen: 3,379 times

last updated: 21 Apr, 03:05