Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
ProjectEuler 411
Author Message
Panphobia

Posted: Wed Jan 23, 2013 11:42 pm   Post subject: ProjectEuler 411

As my exams get closer I am trying to keep away from project euler, but I cant resist trying the latest one, http://projecteuler.net/problem=411 , basically what the question is saying is if you are given n what is the maximum path from (0,0) to (n,n) when x,y cannot decrease, and (2^i mod n, 3^i mod n) are the x and y values 0 <= i <= 2n, so in their example they have 11 distinct points, when n is 22, how is this possible, is this because some of the x points are repeated throughout getting the x's and y's, if so is there a way to keep track of the values already calculated without looking through the whole list to check for duplicates, for efficiency, i am guessing it can be solved using a dfs, but that would take too long to run

d310

Posted: Thu Jan 24, 2013 8:57 pm   Post subject: Re: ProjectEuler 411

I actually got in the top 100 for this one!
A good place to start is looking at the maximum number of points; what is an acceptable O time for an algorithm given that many points?
If you want to keep track of all the unique points, you could use a TreeSet in Java.
Panphobia

Posted: Thu Jan 24, 2013 9:33 pm   Post subject: RE:ProjectEuler 411

I have the way to get distinct points, all I need is to get the maximum number of points, problem is finding an efficient algorithm that doesnt take days to run
d310

Posted: Thu Jan 24, 2013 9:55 pm   Post subject: Re: ProjectEuler 411

Try sorting your points, that's a good starting point.
Panphobia

Posted: Thu Jan 24, 2013 10:06 pm   Post subject: RE:ProjectEuler 411

Thats what I was thinking of but I dont know which value to sort them by, x or y?
d310

Posted: Thu Jan 24, 2013 10:13 pm   Post subject: Re: ProjectEuler 411

It doesn't really matter, as long as you sort by either the x or y coordinate, you will remove one dimension, and break down a two dimensional problem into a one dimensional problem (which is much easier to handle).
d310

Posted: Thu Jan 24, 2013 10:38 pm   Post subject: Re: ProjectEuler 411

For a path to be valid, the x and y coordinates have to be non-decreasing. If we sort by one coordinate we have one guaranteed coordinate that is non-decreasing, so all we have to do is...
Panphobia

Posted: Thu Jan 24, 2013 10:43 pm   Post subject: Re: ProjectEuler 411

The way I generate the distinct points, it takes forever, is there a much more efficient way than this?
 code: out:         for (int i = 0; i <= twon; ++i) {             long x = (long) Math.pow(2, i) % n;             long y = (long) Math.pow(3, i) % n;             for (int q = 0; q < node.size(); ++q) {                 if (node.get(q).x == x) {                     continue out;                 }             }             node.add(new Node(x, y));         }

d310

Posted: Thu Jan 24, 2013 10:48 pm   Post subject: Re: ProjectEuler 411

O(n^2) isn't going to cut it at 20 million points.
I already recommended a TreeSet which is O(n log n)
Panphobia

Posted: Thu Jan 24, 2013 11:13 pm   Post subject: Re: ProjectEuler 411

Ok I got the points generating quickly enough
 code: for (int i = 0; i <= twon; ++i) {             long x = (long) Math.pow(2, i) % n;             long y = (long) Math.pow(3, i) % n;             a=nodeX.size();             nodeX.add(x);             if(a!=nodeX.size())nodeY.add(y);         }
now on to the tricky part, finding an algorithm that actually runs at a decent speed
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 10 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: