Styjun

Should you avoid redundant information after dialogue?

Do native speakers use ZVE or CPU?

Crab Nebula short story from 1960s or '70s

Will it hurt my career to work as a graphic designer in a startup for beauty and skin care?

Won 50K! Now what should I do with it

As a DM, how to avoid unconscious metagaming when dealing with a high AC character?

Doing research in academia and not liking competition

How are "soeben" and "eben" different from one another?

Construct a pentagon avoiding compass use

What is the German equivalent of 干物女 (dried fish woman)?

How can an advanced civilization forget how to manufacture its technology?

What does a red v with a dot above mean in the Misal rico de Cisneros (Spain, 1518)?

Would letting a multiclass character rebuild their character to be single-classed be game-breaking?

What's the difference between soft PWM and PWM

Possible isometry groups of open manifolds

Why does Hellboy file down his horns?

Is killing off one of my queer characters homophobic?

Are L-functions uniquely determined by their values at negative integers?

Is a public company able to check out who owns its shares in very detailed format?

Equivalent definitions of total angular momentum

Integral clarification

Redox reactions redefined

What are some symbols representing peasants/oppressed persons fighting back?

Project Euler, problem # 9, Pythagorean triplet

Is there a way to mathematically locate the correct node?

What is an efficient way to implement a singleton pattern in Java?Fastest way to determine if an integer's square root is an integerWhat's the simplest way to print a Java array?How do I write a correct micro-benchmark in Java?Correct way to add external jars (lib/*.jar) to an IntelliJ IDEA projectEfficient way to find Frequency of a character in a String in java : O(n)Return value in atoi functionHow to directly initialize a HashMap (in a literal way)?Missing Return Statement Error w/ For Loop - JAVAIs there a way to have a single for loop return different values for different user inputs?

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;

0

1

Question from: https://open.kattis.com/problems/numbertree, sourceed from KTH Challenge 2014

This is how the number tree looks like

I used a for loop to iterate through the input string consisting of 'L' and 'R', and curr to store the current variable being evaluated and previous to store the one before this iteration.

if (i == 0) //first 'L' or 'R'
 if (curr == 'L') count++; 
 if (curr == 'R') count +=2 ; 
 

Here, if the current character is the same as the previous one, I increase count by 2 to the power of loops passed, and subtract one from that if the current character is not the same as the previous one.

else if (curr == prev) count += (int) Math.pow(2, h); 
else if (curr != prev) { count += (int) Math.pow(2, h)-1;

At the end of every loop, I'll equate prev to curr and increment h.

This logic worked for the 3 given inputs, 3 LR, 3 RRL, and 2, which returns 11, 2, and 7 respectively.

However it did not pass the hidden test cases. One input I've tried is 3 LLL
which should return 8, but my algorithm returned 3. 3 LRR should return 5, but I got 3.

Is there a solution which uses a data structure to obtain the solution, since the problem quotes "perfect binary trees". Appreciate any help in sorting out the kinks in my logic, as well as other solutions. Thank you!

java

share|improve this question

edited Mar 26 at 7:10

Teo Jun Xiong

asked Mar 26 at 6:28

Teo Jun XiongTeo Jun Xiong

844 bronze badges

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Please make the code into a MCVE (see help section), and provide example input, and expected and actual outputs.
  
  – hyde
  Mar 26 at 6:32
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Also, at least to me it is unclear what you mean either by "solve it mathematically" or by "is data structure required". But generally speaking, you don't handle text (your input string) "mathematically", at least...
  
  – hyde
  Mar 26 at 6:33
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Thanks for your suggestion! Sorry, first post here on stackoverflow :-)
  
  – Teo Jun Xiong
  Mar 26 at 7:11
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Why would 2 return 7?
  
  – Mark
  Mar 26 at 8:32
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  When there's no path. it returns the root, 7
  
  – Teo Jun Xiong
  Mar 26 at 8:35
  

  
  
  
  

 | 
show 2 more comments

0

1

Question from: https://open.kattis.com/problems/numbertree, sourceed from KTH Challenge 2014

This is how the number tree looks like

I used a for loop to iterate through the input string consisting of 'L' and 'R', and curr to store the current variable being evaluated and previous to store the one before this iteration.

if (i == 0) //first 'L' or 'R'
 if (curr == 'L') count++; 
 if (curr == 'R') count +=2 ; 
 

Here, if the current character is the same as the previous one, I increase count by 2 to the power of loops passed, and subtract one from that if the current character is not the same as the previous one.

else if (curr == prev) count += (int) Math.pow(2, h); 
else if (curr != prev) { count += (int) Math.pow(2, h)-1;

At the end of every loop, I'll equate prev to curr and increment h.

This logic worked for the 3 given inputs, 3 LR, 3 RRL, and 2, which returns 11, 2, and 7 respectively.

However it did not pass the hidden test cases. One input I've tried is 3 LLL
which should return 8, but my algorithm returned 3. 3 LRR should return 5, but I got 3.

Is there a solution which uses a data structure to obtain the solution, since the problem quotes "perfect binary trees". Appreciate any help in sorting out the kinks in my logic, as well as other solutions. Thank you!

java

share|improve this question

edited Mar 26 at 7:10

Teo Jun Xiong

asked Mar 26 at 6:28

Teo Jun XiongTeo Jun Xiong

844 bronze badges

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Please make the code into a MCVE (see help section), and provide example input, and expected and actual outputs.
  
  – hyde
  Mar 26 at 6:32
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Also, at least to me it is unclear what you mean either by "solve it mathematically" or by "is data structure required". But generally speaking, you don't handle text (your input string) "mathematically", at least...
  
  – hyde
  Mar 26 at 6:33
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Thanks for your suggestion! Sorry, first post here on stackoverflow :-)
  
  – Teo Jun Xiong
  Mar 26 at 7:11
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Why would 2 return 7?
  
  – Mark
  Mar 26 at 8:32
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  When there's no path. it returns the root, 7
  
  – Teo Jun Xiong
  Mar 26 at 8:35
  

  
  
  
  

 | 
show 2 more comments

Question from: https://open.kattis.com/problems/numbertree, sourceed from KTH Challenge 2014

This is how the number tree looks like

I used a for loop to iterate through the input string consisting of 'L' and 'R', and curr to store the current variable being evaluated and previous to store the one before this iteration.

if (i == 0) //first 'L' or 'R'
 if (curr == 'L') count++; 
 if (curr == 'R') count +=2 ; 
 

Here, if the current character is the same as the previous one, I increase count by 2 to the power of loops passed, and subtract one from that if the current character is not the same as the previous one.

else if (curr == prev) count += (int) Math.pow(2, h); 
else if (curr != prev) { count += (int) Math.pow(2, h)-1;

At the end of every loop, I'll equate prev to curr and increment h.

This logic worked for the 3 given inputs, 3 LR, 3 RRL, and 2, which returns 11, 2, and 7 respectively.

However it did not pass the hidden test cases. One input I've tried is 3 LLL
which should return 8, but my algorithm returned 3. 3 LRR should return 5, but I got 3.

Is there a solution which uses a data structure to obtain the solution, since the problem quotes "perfect binary trees". Appreciate any help in sorting out the kinks in my logic, as well as other solutions. Thank you!

java

share|improve this question

edited Mar 26 at 7:10

Teo Jun Xiong

asked Mar 26 at 6:28

Teo Jun XiongTeo Jun Xiong

844 bronze badges

if (i == 0) //first 'L' or 'R'
 if (curr == 'L') count++; 
 if (curr == 'R') count +=2 ; 
 

else if (curr == prev) count += (int) Math.pow(2, h); 
else if (curr != prev) { count += (int) Math.pow(2, h)-1;

share|improve this question

edited Mar 26 at 7:10

Teo Jun Xiong

asked Mar 26 at 6:28

Teo Jun XiongTeo Jun Xiong

844 bronze badges

share|improve this question

edited Mar 26 at 7:10

Teo Jun Xiong

asked Mar 26 at 6:28

Teo Jun XiongTeo Jun Xiong

844 bronze badges

asked Mar 26 at 6:28

Teo Jun XiongTeo Jun Xiong

844 bronze badges

asked Mar 26 at 6:28

Teo Jun XiongTeo Jun Xiong

844 bronze badges

1 Answer
1

active

oldest

votes

0

Being a perfect binary tree, the lowest node at a level x is greater then the sum of 2^k, where k here is the number of nodes from the level x+1 to H. A path 5 RL tells you that you have a node in level 2 on a 5-levels tree, so that node is greater than 2^3 + 2^4 + 2^5 = 56. Now that we have reduced the tree to H = h(x), we can observe that the path to the node is nothing more than a binary code where L = 0, R =1. We convert this binary code to integer, sum it to the number obtained before and we have the label of the node. A path RL is 10 = 2, and then 5 RL has label 58.

Now, converting this algorithm is very simple as you just have to split the array in two parts, convert the R-L path in binary code and do the math.

share|improve this answer

answered Mar 26 at 6:58

Davide VitaliDavide Vitali

70033 silver badges1616 bronze badges

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55351011%2fis-there-a-way-to-mathematically-locate-the-correct-node%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

0

Being a perfect binary tree, the lowest node at a level x is greater then the sum of 2^k, where k here is the number of nodes from the level x+1 to H. A path 5 RL tells you that you have a node in level 2 on a 5-levels tree, so that node is greater than 2^3 + 2^4 + 2^5 = 56. Now that we have reduced the tree to H = h(x), we can observe that the path to the node is nothing more than a binary code where L = 0, R =1. We convert this binary code to integer, sum it to the number obtained before and we have the label of the node. A path RL is 10 = 2, and then 5 RL has label 58.

Now, converting this algorithm is very simple as you just have to split the array in two parts, convert the R-L path in binary code and do the math.

share|improve this answer

answered Mar 26 at 6:58

Davide VitaliDavide Vitali

70033 silver badges1616 bronze badges

add a comment | 

0

Being a perfect binary tree, the lowest node at a level x is greater then the sum of 2^k, where k here is the number of nodes from the level x+1 to H. A path 5 RL tells you that you have a node in level 2 on a 5-levels tree, so that node is greater than 2^3 + 2^4 + 2^5 = 56. Now that we have reduced the tree to H = h(x), we can observe that the path to the node is nothing more than a binary code where L = 0, R =1. We convert this binary code to integer, sum it to the number obtained before and we have the label of the node. A path RL is 10 = 2, and then 5 RL has label 58.

Now, converting this algorithm is very simple as you just have to split the array in two parts, convert the R-L path in binary code and do the math.

share|improve this answer

answered Mar 26 at 6:58

Davide VitaliDavide Vitali

70033 silver badges1616 bronze badges

add a comment | 

Being a perfect binary tree, the lowest node at a level x is greater then the sum of 2^k, where k here is the number of nodes from the level x+1 to H. A path 5 RL tells you that you have a node in level 2 on a 5-levels tree, so that node is greater than 2^3 + 2^4 + 2^5 = 56. Now that we have reduced the tree to H = h(x), we can observe that the path to the node is nothing more than a binary code where L = 0, R =1. We convert this binary code to integer, sum it to the number obtained before and we have the label of the node. A path RL is 10 = 2, and then 5 RL has label 58.

Now, converting this algorithm is very simple as you just have to split the array in two parts, convert the R-L path in binary code and do the math.

share|improve this answer

answered Mar 26 at 6:58

Davide VitaliDavide Vitali

70033 silver badges1616 bronze badges

share|improve this answer

answered Mar 26 at 6:58

Davide VitaliDavide Vitali

70033 silver badges1616 bronze badges

answered Mar 26 at 6:58

Davide VitaliDavide Vitali

70033 silver badges1616 bronze badges

answered Mar 26 at 6:58

Davide VitaliDavide Vitali

70033 silver badges1616 bronze badges