Ccc2013

[Panphobia]

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.

[coolgod]

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]

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]

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]

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.

[Panphobia]

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]

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]

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]

Woodroffe High School, why?

[Panphobia]

I don't know was just wondering.

[linuxp]

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]

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

[Panphobia]

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

[Raknarg]

Im pretty sure the questions had a 1 minute limit

[Panphobia]

this was for number 4 [/img]