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:
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: