This problem frustrated me and I caused my rating to go down again.  But I will talk about thin my review.

This problem took me a while to figure out.   Something that instantly hit me is that the number of points is 3n.  n was the number given to us.   Also, each node could have 3 different values.   So all the possible combinations would be 3^(3n).   If n=1, there would be 27.   However, the answer was 20.   A difference of 7.

I then tried different things.  I really didn’t get the pattern until I put in 3^6 and got 729.  The sample output was 680.  I didn’t think of it until about ten minutes later, but the difference between them is 49.   When I saw the 49, it clicked in my mind.

The formula for the is (3^3n – 7^n)%1000000007.   Easy.  So I write this up:

``````import java.math.BigInteger;
import java.util.Scanner;
/*
Kyle S. Dencker
CodeForces #324 - Problem B
October 6, 2015
*/
public class C324B {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
long n = scan.nextLong();
long gnomes = n*3;

BigInteger subtract = BigInteger.ONE;
BigInteger seven = new BigInteger("7");
BigInteger three = new BigInteger("3");

for (long i=0; i<n; i++) {
subtract = subtract.multiply(seven);
}

BigInteger realValue = BigInteger.ONE;
for (long i=0; i<gnomes; i++) {
realValue= realValue.multiply(three);
}

}
}``````
C324B.java - Time Limit

I get time limit!  Grr!  I thought I had it right.   So I spend a few more moments researching faster way to take the power of something and when I do, I start getting the wrong answers.   I tried a few different ways of rewriting the power function, decided that 3^(3n) is the same as 27^n and used that.  None of this gave me the correct answer.

I was about to give up and then I thought, I wonder if BitInteger has a power function.   I found it, used and submitted.  It was correct.  It is faster, but I don't know why.   However, I did finish two this round and I was excited about that.

This is my final code:

``````import java.math.BigInteger;
import java.util.Scanner;
/*
Kyle S. Dencker
CodeForces 324 - Problem B
October 6, 2015
*/
public class C324B {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();

BigInteger seven = new BigInteger("7");
BigInteger three = new BigInteger("27");

seven = seven.pow(n);
three = three.pow(n);