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
Panphobia




PostPosted: 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
Sponsor
sponsor
coolgod




PostPosted: 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




PostPosted: 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 pre-calculated values] };
int primes[] = { [huge list of pre-calculated 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




PostPosted: 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




PostPosted: 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[i-1]+hist[i-1];
        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. Shocked
Panphobia




PostPosted: 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 Smile
Raknarg




PostPosted: 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




PostPosted: 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?
Sponsor
Sponsor
Sponsor
sponsor
Raknarg




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

Woodroffe High School, why?
Panphobia




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

I don't know was just wondering.
linuxp




PostPosted: 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 Smile


Did you s5 code run in time(6s limit) for all cases?
toofresh




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

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




PostPosted: 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




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

Im pretty sure the questions had a 1 minute limit
Panphobia




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

this was for number 4 Posted Image, might have been reduced in size. Click Image to view fullscreen.[/img]
Display posts from previous:   
   Index -> Contests
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

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


Style:  
Search: