Ccc2013
Author |
Message |
Halls McSmurfin
|
Posted: 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
|
|
|
ttm
|
Posted: Fri Mar 01, 2013 6:30 pm Post subject: Re: Ccc2013 |
|
|
Yeah. It was a 7 liner
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
|
Posted: 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
|
Posted: 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 |
|
|
|
|
|
bbqchps
|
Posted: 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
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) |
|
|
|
|
|
ishiney
|
Posted: 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 ).
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
|
Posted: 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" |
|
|
|
|
|
Panphobia
|
Posted: 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
|
|
|
nullptr
|
Posted: 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
|
Posted: 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
|
Posted: Fri Mar 01, 2013 9:44 pm Post subject: RE:Ccc2013 |
|
|
Well I couldve gotten 65 points..... |
|
|
|
|
|
linuxp
|
Posted: 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
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
|
Posted: 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
|
Posted: 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
|
Posted: 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
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. |
|
|
|
|
|
|
|