Keeping me entertained
I thought the Crop Triangles Code Jam problem will be gone in no time. It looked simple the morning I started with it and I was expecting to have it all done by lunch time.
The basic idea is that you have an integer coordinate system (or grid) and in certain points of the grid there are some trees located. If you use those trees as vertices to make triangles ... how many different triangles can be created?
Well, the answer to that is actually quite simple using combinatoric numbers, but they added a restriction: the center of a valid triangle has to be located on a grid coordinate, if not do not count that triangle. A triangle with vertices (x1,y1) (x2,y2) and (x3,y3) has a center at coordinate ((x1+x2+x3)/3,(y1+y2+y3)/3)
My first solution was to simulate the system. Given all the available trees, I will go though all the different combinations and after checking each one a counter will give me the valid answer.
That idea worked nicely for the small dataset (once I realized that Case #9 really required to use 64-bit integers), but it was just unfeasible for the large dataset (as computing time will huge for 100000 trees). A new approach has to be found somehow.
The key observation was that for a triangle to be valid the sum of x and y coordinates of vertices has to lead to a number multiple of 3. If we add three different numbers, the result will be a multiple of 3 if: a) all of them are multiples of 3 or b) one of them is a multiple and the others add up to a multiple too c) none of them are but the three numbers lead to a remainder of 1 when divided by three.
So then, why don't we count the number of trees with each coordinate x and y being either 0, 1 or 2 when we perform the modulo 3 operation. This way we will have a 3x3 matrix totaling the count of each type of coordinate of all our trees.
Next observation is that for a triangle to be created we will use three trees, each one belonging to each one of these nine (3x3) bins. But not all the combinations are possible. For example, if I choose three trees from bin 0,0 then these are trees which coordinates (both x and y) are multiples of 3. So when we add them we are going to have a triangle whose center will be on the grid. But if we choose a triangle from 0,0 bin and two from 1,1 bin then the resulting tree won't be a valid one.
I've used the following 'bc' code to print the valid combinations:
c=0; for(i=0;i<9;i++)for(j=0;j<9;j++)for(k=0;k<9;k++) if((i%3+j%3+k%3)%3==0 && (i/3+j/3+k/3)%3==0) {print c++," ",i," ",j," ",k,"\n";}
A careful observation of the combinations will show you that only rows, columns and diagonals are the combinations that render a valid tree. These and, whenever possible, to choose the three trees from the same bin (i.e. 1,1)
So what is left is to read the trees coordinates, count them appropriately and to sum the different combinations. There are only two cases: 1) you take the three trees from the same bin, then this subtotal is (x)*(x-1)*(x-2)/6 or 2) each bin comes from a different bin, and then the subtotal is x*y*z (x,y,z are the values of each bin, for example x is the count of bin 0,0 y the count of 1,1 and z the count of 2,2).
Of course, pondering all that took longer than lunch time :-)
I did have a lot of fun too with the Number Sets problem, but I will write about it another day.
Update: I've just noticed that Code Jam site has added a nice entry named "Contest analysis" where a comment on each problem's solution is provided (so you can skip my comments and go straight to the real thing :-) Highly recommended!!
The basic idea is that you have an integer coordinate system (or grid) and in certain points of the grid there are some trees located. If you use those trees as vertices to make triangles ... how many different triangles can be created?
Well, the answer to that is actually quite simple using combinatoric numbers, but they added a restriction: the center of a valid triangle has to be located on a grid coordinate, if not do not count that triangle. A triangle with vertices (x1,y1) (x2,y2) and (x3,y3) has a center at coordinate ((x1+x2+x3)/3,(y1+y2+y3)/3)
My first solution was to simulate the system. Given all the available trees, I will go though all the different combinations and after checking each one a counter will give me the valid answer.
That idea worked nicely for the small dataset (once I realized that Case #9 really required to use 64-bit integers), but it was just unfeasible for the large dataset (as computing time will huge for 100000 trees). A new approach has to be found somehow.
The key observation was that for a triangle to be valid the sum of x and y coordinates of vertices has to lead to a number multiple of 3. If we add three different numbers, the result will be a multiple of 3 if: a) all of them are multiples of 3 or b) one of them is a multiple and the others add up to a multiple too c) none of them are but the three numbers lead to a remainder of 1 when divided by three.
So then, why don't we count the number of trees with each coordinate x and y being either 0, 1 or 2 when we perform the modulo 3 operation. This way we will have a 3x3 matrix totaling the count of each type of coordinate of all our trees.
Next observation is that for a triangle to be created we will use three trees, each one belonging to each one of these nine (3x3) bins. But not all the combinations are possible. For example, if I choose three trees from bin 0,0 then these are trees which coordinates (both x and y) are multiples of 3. So when we add them we are going to have a triangle whose center will be on the grid. But if we choose a triangle from 0,0 bin and two from 1,1 bin then the resulting tree won't be a valid one.
I've used the following 'bc' code to print the valid combinations:
c=0; for(i=0;i<9;i++)for(j=0;j<9;j++)for(k=0;k<9;k++) if((i%3+j%3+k%3)%3==0 && (i/3+j/3+k/3)%3==0) {print c++," ",i," ",j," ",k,"\n";}
A careful observation of the combinations will show you that only rows, columns and diagonals are the combinations that render a valid tree. These and, whenever possible, to choose the three trees from the same bin (i.e. 1,1)
So what is left is to read the trees coordinates, count them appropriately and to sum the different combinations. There are only two cases: 1) you take the three trees from the same bin, then this subtotal is (x)*(x-1)*(x-2)/6 or 2) each bin comes from a different bin, and then the subtotal is x*y*z (x,y,z are the values of each bin, for example x is the count of bin 0,0 y the count of 1,1 and z the count of 2,2).
Of course, pondering all that took longer than lunch time :-)
I did have a lot of fun too with the Number Sets problem, but I will write about it another day.
Update: I've just noticed that Code Jam site has added a nice entry named "Contest analysis" where a comment on each problem's solution is provided (so you can skip my comments and go straight to the real thing :-) Highly recommended!!
Comments