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 





Sponsor Sponsor



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 nondecreasing. If we sort by one coordinate we have one guaranteed coordinate that is nondecreasing, 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));
} 






Sponsor Sponsor



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 






