Ccc2013
Author 
Message 
Panphobia

Posted: Sat Mar 02, 2013 5:45 pm Post subject: RE:Ccc2013 


S4 wasn't difficult, it was a simple graph search problem, gotta love breadth first search. S5 you could use recursion, but a dynamic solution would be better.






Sponsor Sponsor



coolgod

Posted: Sat Mar 02, 2013 9:13 pm Post subject: Re: Ccc2013 


bbi5291 @ Sat Mar 02, 2013 2:33 pm wrote: So what do you expect them to do? Give you a longer time limit for C++ than for C? That would be ridiculous, because then you could just use C input functions in C++, and then you'd have an unfair advantage over the C people.
Giving all programming languages equal execution time is the least evil of all choices.
Also, did any of you actually bother to test your programs on huge cases, to be sure they wouldn't time out? If you had, you would've known that cin wouldn't cut it.
How exactly did u bother to test your program on huge cases? Remember most of us were given no feedback.
Generate millions of numbers and write it in a text file?
Suppose our computer c++ with cin could run under 1 second, that doesn't mean online grader can. Did anyone get a 15/15 without using c style inputs?






ttm

Posted: Sat Mar 02, 2013 9:14 pm Post subject: Re: Ccc2013 


For 5 you could use DP but that's still pretty slow. I solved it like so:
code: 
#include <iostream>
int bestprime[] = { [huge list of precalculated values] };
int primes[] = { [huge list of precalculated values] };
int main() {
freopen("s5.in", "r", stdin);
int n, acc = 0; std::cin >> n;
for (int pn = 0; n != 1; ++pn) while (n % primes[pn] == 0) n /= primes[pn], acc += bestprime[pn];
std::cout << acc << std::endl;
}







Raknarg

Posted: Sat Mar 02, 2013 9:56 pm Post subject: RE:Ccc2013 


With s5 my friend did something interesting, that would work if he found an efficient method for finding factors. He basically created a map of finding to shortest path to separate numbers so he could reuse the data rather than straight bruteforcing it.
OF course it's still an n^2 algorithm if he has to search to find all the factors too.
I solved 4 with simple recursion. But i figured it out after the contest, so im kindof pissed .'






toofresh

Posted: Sat Mar 02, 2013 10:02 pm Post subject: Re: Ccc2013 


coolgod @ Sat Mar 02, 2013 9:13 pm wrote: Did anyone get a 15/15 without using c style inputs?
Easy.
code: 
#include <iostream>
#include <cstring>
using namespace std;
int N,M,cf,ct,p,q,pq,qp,target;
int hist[1000000];
int from[1000001];
int store[10000000];
int data[10000000][2];
char visited[1000000];
void dfs(int v) {
for(int i = from[v]; i < from[v+1] && !visited[target]; i++) {
if(visited[store[i]])
continue;
visited[store[i]] = 1;
dfs(store[i]);
}
}
int main() {
cin >> N >> M;
memset(hist,0,N*sizeof(int));
memset(from,0,N*sizeof(int));
for(int i = 0; i < M; i++) {
cin >> data[i][0] >> data[i][1];
data[i][0];
data[i][1];
hist[data[i][0]]++;
}
for(int i = 1; i < N; i++)
from[i] = from[i1]+hist[i1];
from[N] = M;
for(int i = 0; i < M; i++) {
cf = data[i][0];
store[from[cf]+(hist[cf])] = data[i][1];
}
cin >> p >> q;
p;
q;
memset(visited,0,N);
target = q;
dfs(p);
pq = visited[q];
memset(visited,0,N);
target = p;
dfs(q);
qp = visited[p];
if(pq && !qp)
cout << "yes" << endl;
else if(qp && !pq)
cout << "no" << endl;
else
cout << "unknown" << endl;
}

This runs in 0.85 seconds on their grader.






Panphobia

Posted: Sat Mar 02, 2013 10:09 pm Post subject: Re: RE:Ccc2013 


Raknarg @ Sat Mar 02, 2013 9:56 pm wrote: With s5 my friend did something interesting, that would work if he found an efficient method for finding factors. He basically created a map of finding to shortest path to separate numbers so he could reuse the data rather than straight bruteforcing it.
OF course it's still an n^2 algorithm if he has to search to find all the factors too.
I solved 4 with simple recursion. But i figured it out after the contest, so im kindof pissed .' I solved it with a breadth first search, no more than 20 lines of code






Raknarg

Posted: Sat Mar 02, 2013 10:15 pm Post subject: RE:Ccc2013 


blegh, at first I tried doing this weird linked list thing, which would have worked, it was just really messy and complicated. Turns out the answer was staring me right in the face, cause I was doing the easy search method in a really complex way cause I was just trying to save it... ugh






Panphobia

Posted: Sat Mar 02, 2013 10:25 pm Post subject: Re: RE:Ccc2013 


Raknarg @ Sat Mar 02, 2013 10:15 pm wrote: blegh, at first I tried doing this weird linked list thing, which would have worked, it was just really messy and complicated. Turns out the answer was staring me right in the face, cause I was doing the easy search method in a really complex way cause I was just trying to save it... ugh what school do you go to?






Raknarg

Posted: Sat Mar 02, 2013 10:49 pm Post subject: RE:Ccc2013 


Woodroffe High School, why?






Panphobia

Posted: Sat Mar 02, 2013 11:00 pm Post subject: RE:Ccc2013 


I don't know was just wondering.






linuxp

Posted: Sat Mar 02, 2013 11:14 pm Post subject: Re: RE:Ccc2013 


Panphobia @ Sat Mar 02, 2013 10:09 pm wrote: I solved it with a breadth first search, no more than 20 lines of code
Did you s5 code run in time(6s limit) for all cases?






toofresh

Posted: Sat Mar 02, 2013 11:22 pm Post subject: RE:Ccc2013 


Thought the time limit for s5 was 5 seconds...






Panphobia

Posted: Sat Mar 02, 2013 11:26 pm Post subject: RE:Ccc2013 


for s5 i only got a few test cases, but for s4 i got all but 5, the 5 i didnt timed out






Raknarg

Posted: Sat Mar 02, 2013 11:34 pm Post subject: RE:Ccc2013 


Im pretty sure the questions had a 1 minute limit






Panphobia

Posted: Sat Mar 02, 2013 11:51 pm Post subject: Re: Ccc2013 


this was for number 4 [/img]







