Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Ccc2013
Index -> Contests
Goto page Previous  1, 2, 3, 4, 5, 6, 7, 8  Next
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
Halls McSmurfin




PostPosted: Fri Mar 01, 2013 5:53 pm   Post subject: Re: Ccc2013

ttm @ Fri Mar 01, 2013 5:20 pm wrote:
I didn't use the online grader but my solution to S5 ran in <3 seconds for all cases...


Wow.. that's very impressive. Did you also get perfect?
Sponsor
Sponsor
Sponsor
sponsor
ttm




PostPosted: Fri Mar 01, 2013 6:30 pm   Post subject: Re: Ccc2013

Yeah. It was a 7 liner Smile

crossley7 wrote:

The number of operations performed in 1 second is enormous.


Um.. yeah but have you seen the size of the test cases for S4? Some of my classmates' solutions (in Ruby) cut it close at > 40 seconds for the larger cases. I'd have no idea how to solve 4 if I was using Turing (but I suppose that counts as a language with ridiculous amounts of overhead).[/quote]
nullptr




PostPosted: Fri Mar 01, 2013 6:44 pm   Post subject: Re: Ccc2013

What's this about a postcontest? Can I test my solutions there? (I don't have any login info)
ishiney




PostPosted: Fri Mar 01, 2013 6:55 pm   Post subject: RE:Ccc2013

For those complaining about the 1/6s - 1 min judge time, here's the reply I got from Mr. Troy Vasiga, the person in charge of CCC (according to the CEMC website):

Quote:
"1 minute" of real time (i.e., user time) is roughly the same as "5 seconds" of CPU time. So, it should actually be roughly equal.


So there you go Smile
bbqchps




PostPosted: Fri Mar 01, 2013 7:38 pm   Post subject: Re: RE:Ccc2013

ishiney @ Fri Mar 01, 2013 6:55 pm wrote:
For those complaining about the 1/6s - 1 min judge time, here's the reply I got from Mr. Troy Vasiga, the person in charge of CCC (according to the CEMC website):

Quote:
"1 minute" of real time (i.e., user time) is roughly the same as "5 seconds" of CPU time. So, it should actually be roughly equal.


So there you go Smile


Thanks for asking! I have still have a question though... Only the last problem was given 5s to run, but wasn't the one minute time limit in place for each of the problems (based on the instruction booklet at least)Question
ishiney




PostPosted: Fri Mar 01, 2013 8:21 pm   Post subject: RE:Ccc2013

I agree that the official answer regarding the time limits isn't perfect. For example, after slightly modifying my algorithm to calculate the answers for all N <= 5 million (for S5), it ran under 30s (though my 2.5 GHz laptop is slightly higher than the specified specification), but TLE'd on the judge computer. There's not much we can really do about it at this point, though, besides send hate mail (just kidding Smile ).

However, I do believe that even a slightly optimized algorithm (i.e. that's not completely brute-force) should pass most of the test cases for S5 under the 5s time limit....
bbqchps




PostPosted: Fri Mar 01, 2013 8:40 pm   Post subject: Re: RE:Ccc2013

Haha, I'm actually referring to Q4 which I made a bit of a careless mistake so it TLE'd, but I'm pretty sure that it was at least fast enough to run under 1 minute.

Q5 is really just a 10 line "solution" Razz
Panphobia




PostPosted: Fri Mar 01, 2013 9:02 pm   Post subject: Re: Ccc2013

Could anyone point out what I did wrong in question number 3, I got the sample output correct on both cases, but I seemed to have failed the testing
Java:
import java.util.*;

public class Main {

    static int teamWin = 0;

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        while (s.hasNext()) {
            int team = Integer.parseInt(s.nextLine());
            int n = Integer.parseInt(s.nextLine());
            ArrayList<String> nums = new ArrayList<String>();
            nums.add("1 2");
            nums.add("1 3");
            nums.add("1 4");
            nums.add("2 3");
            nums.add("2 4");
            nums.add("3 4");
            ArrayList<String[]> text = new ArrayList<String[]>();
            int[] scores = {0, 0, 0, 0};
            for (int i = 0; i < n; ++i) {
                text.add(s.nextLine().split(" "));
                if (Integer.parseInt(text.get(i)[2]) > Integer.parseInt(text.get(i)[3])) {
                    scores[Integer.parseInt(text.get(i)[0]) - 1] += 3;
                } else if (Integer.parseInt(text.get(i)[2]) < Integer.parseInt(text.get(i)[3])) {
                    scores[Integer.parseInt(text.get(i)[1]) - 1] += 3;
                } else {
                    scores[Integer.parseInt(text.get(i)[1]) - 1]++;
                    scores[Integer.parseInt(text.get(i)[0]) - 1]++;
                }
            }
            for (int i = 0; i < n; ++i) {
                nums.remove(nums.indexOf(text.get(i)[0] + " " + text.get(i)[1]));
            }

            ArrayList<int[]> points = new ArrayList<int[]>();
            for (int i = 0; i < nums.size(); ++i) {
                int[] num = {nums.get(i).charAt(0) - '0', nums.get(i).charAt(2) - '0'};
                points.add(num);
            }
            recurse(points, scores, team);
            System.out.println(teamWin);
        }

    }

    public static void recurse(ArrayList<int[]> points, int[] score, int team) {
        if (points.isEmpty()) {
            for (int i = 0; i < 4; ++i) {
                if (i != team - 1) {
                    if (score[team - 1] < score[i]) {
                        return;
                    }
                }
            }
            teamWin++;
        } else {
            int[] lol = points.get(0);
            score[lol[0] - 1] += 3;
            ArrayList<int[]> a = new ArrayList<int[]>();
            for (int i = 0; i < points.size(); ++i) {
                if (i != points.indexOf(lol)) {
                    a.add(points.get(i));
                }
            }
            recurse(a, score, team);
            score[lol[0] - 1] -= 3;
            score[lol[1] - 1] += 3;
            a.clear();
            for (int i = 0; i < points.size(); ++i) {
                if (i != points.indexOf(lol)) {
                    a.add(points.get(i));
                }
            }
            recurse(a, score, team);
            score[lol[1] - 1] -= 3;
            score[lol[0] - 1]++;
            score[lol[1] - 1]++;
            a.clear();
            for (int i = 0; i < points.size(); ++i) {
                if (i != points.indexOf(lol)) {
                    a.add(points.get(i));
                }
            }
            recurse(a, score, team);
            score[lol[0] - 1]--;
            score[lol[1] - 1]--;
        }
    }
}
Sponsor
Sponsor
Sponsor
sponsor
nullptr




PostPosted: Fri Mar 01, 2013 9:36 pm   Post subject: Re: Ccc2013

Panphobia @ Fri Mar 01, 2013 9:02 pm wrote:
Could anyone point out what I did wrong in question number 3, I got the sample output correct on both cases, but I seemed to have failed the testing
Java:
import java.util.*;

public class Main {
    ...
}


It looks like your program counts ties as wins... they really should have included a test case for that.
Panphobia




PostPosted: Fri Mar 01, 2013 9:43 pm   Post subject: RE:Ccc2013

yea I just changed from < to <= and I got perfect in all cases lol
Panphobia




PostPosted: Fri Mar 01, 2013 9:44 pm   Post subject: RE:Ccc2013

Well I couldve gotten 65 points.....
linuxp




PostPosted: Fri Mar 01, 2013 10:09 pm   Post subject: Re: RE:Ccc2013

ishiney @ Fri Mar 01, 2013 6:55 pm wrote:
For those complaining about the 1/6s - 1 min judge time, here's the reply I got from Mr. Troy Vasiga, the person in charge of CCC (according to the CEMC website):

Quote:
"1 minute" of real time (i.e., user time) is roughly the same as "5 seconds" of CPU time. So, it should actually be roughly equal.


So there you go Smile



I have to tell you something really sad

For S4, if i use cin as input result is tle
but if i change cin to scanf, result is prefect.
Can you say my algorithm is bad? it's not even close to roughly equal.
coolgod




PostPosted: Fri Mar 01, 2013 10:46 pm   Post subject: Re: Ccc2013

Guide to getting high scores on CCC.
learn c and use c inputs instead of C++. This is the only contest I've seen where a c++ solution does not run in time but a c one does.
bbi5291




PostPosted: Fri Mar 01, 2013 11:18 pm   Post subject: Re: Ccc2013

coolgod @ Fri Mar 01, 2013 10:46 pm wrote:
Guide to getting high scores on CCC.
learn c and use c inputs instead of C++. This is the only contest I've seen where a c++ solution does not run in time but a c one does.

Then you haven't seen a lot of contests.
crossley7




PostPosted: Fri Mar 01, 2013 11:21 pm   Post subject: Re: Ccc2013

ttm @ Fri Mar 01, 2013 6:30 pm wrote:
Yeah. It was a 7 liner Smile

crossley7 wrote:

The number of operations performed in 1 second is enormous.


Um.. yeah but have you seen the size of the test cases for S4? Some of my classmates' solutions (in Ruby) cut it close at > 40 seconds for the larger cases. I'd have no idea how to solve 4 if I was using Turing (but I suppose that counts as a language with ridiculous amounts of overhead).


Yes, Turing has a ridiculous amount of overhead. Haskell/C/C++/Java are the ones I was mainly considering. I don't know anything about ruby, but even python which is popular is much slower than the other ones I mentioned. Turing should not be used for the senior contest by anyone imo since a) it doesn't get used outside of a high school classroom and even then it's rarely used there, b) it is about a bazillion times slower than any decent language, and c) if the goal is to move to the next round you need to use something else that is drastically different anyways so you may as well qualify and practice with the allowed language.

I won't say Turing doesn't have uses, the thing is that none of those uses apply to contests.

Also, I have not seen test cases for any question nor have I seen the actual questions (I've got enough University schoolwork keeping me busy enough as is... though practice would be smart) I know what it is like for the time limit and my solution for S4 last year timed out on 3 of 5 cases given a minute (though not on the grader) but the other 2 were done in under 5 seconds.
Display posts from previous:   
   Index -> Contests
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 4 of 8  [ 118 Posts ]
Goto page Previous  1, 2, 3, 4, 5, 6, 7, 8  Next
Jump to:   


Style:  
Search: