- Prepare
- Algorithms
- Implementation
- Utopian Tree
- Discussions

# Utopian Tree

# Utopian Tree

+ 24 comments with only adds and bitwise:

return ~(~1<<(n>>1)) << n%2;

+ 3 comments Does anyone else feel slighty confused by the wording of this problem?

The Utopian Tree goes through 2 CYCLES of growth every YEAR. Each spring, it doubles in height. Each summer, its height increases by 1 meter.

Laura plants a Utopian Tree sapling with a height of 1 meter at the onset of spring. How tall will her tree be after N growth CYCLES?

I have been basing my solution around cycles. No where in the problem statement does it clarify that a year is a single growth cylce. If that is the case the last line should be written:

"How tall will her tree be after N growth YEARS?"

I am I the only one tripped up by this?

+ 11 comments Here's another O(1) approach. I searched for the sequence on the Online Encylopedia of Integer Sequences and found it at https://oeis.org/A075427

There was as closed-form solution on the page.

f(n) = 2 ^ ((n+3)/2) + ((-1)^n - 3) / 2

import java.io.*; import java.util.*; public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int numCases = in.nextInt(); for (int i = 0; i < numCases; i++) { int n = in.nextInt(); int answer = ((int) Math.pow(2, (n + 3) / 2)) + (((int) Math.pow(-1, n)) - 3) / 2; System.out.println(answer); } } }

+ 6 comments With python3

def utopianTree(n): if n < 3: return n + 1 if n % 2 == 0: return (utopianTree(n - 2) * 2) + 1 else: return (utopianTree(n - 2) + 1) * 2

+ 8 comments Did anyone try solving it this way? The output matches perfectly but the test cases tell me that the output is wrong...any suggestions?

Code in Python3:

n = int(input())

def growthCycle(x):

`if x == 0: h = 1 elif x % 2 == 0: h = 2 ** ((x/2) + 1) - 1 elif x % 2 == 1: h = 2 ** ((x + 3)/2) - 2 return h`

for l in (0, n):

`g = int(input()) res = int(growthCycle(g)) print(res)`

Sort 1623 Discussions, By:

Please Login in order to post a comment