Problem Source Link

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);
        }

        BigInteger answer = realValue.subtract(subtract);
        answer = answer.mod(new BigInteger("1000000007"));
        System.out.println(answer.toString());
    }
}
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);
                
        BigInteger answer = three.subtract(seven);
        answer = answer.mod(new BigInteger("1000000007"));
        System.out.println(answer.toString());
    
    }
}
C324B.java - Correct