KM25P5C Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest
Author: Chandan Boruah

DIFFICULTY:

EASY

PREREQUISITES:

MATHS, DATA STRUCTURES.

PROBLEM:

Given the leaf nodes of a complete binary tree whose sum of siblings equals the parent node of those siblings, print the minimum change you need to make to make all siblings equal. You can increase or decrease the values.

QUICK EXPLANATION:

Since the sum of leaf nodes have a value and as the root node will have a value which will be reflected in the leaf node, thus there are only a few possibilities that the root will take, which would be the power of 2 cause all leaf nodes needs to be equal.

EXPLANATION:

Find the sum of all the values in the leaf node. For each level multiply the number of nodes to 2 and power the values to 2, so that the level total value is known. In the end the values of the nodes that matches the nodes in the given leaf nodes will be reached or will cross it. The minimum needs to be taken in each step, and then the value printed.

ADDITIONAL NOTES:

Since the total value was calculated and the individual values were not very important, the author that is me messed up in the test cases. I printed 2 values from upper rows in the test cases. Thus, the problem was messed up. Weak cases are used, so messed up in using values.
“I agree the problem needed testing by another coder. Sorry next time I hope to do better”.

Authors's Solution 
using System;
using System.Collections.Generic;
class some
{
	public static void Main()
	{
		int n=int.Parse(Console.ReadLine());
		string []ss=Console.ReadLine().Split();
		int[]vals=new int[ss.Length];
		int tot=0;
		for(int i=0;i<vals.Length;i++)
		{
			vals[i]=int.Parse(ss[i]);
			tot+=vals[i];
		}
		int levels=0;
		int now=1;
		int div=1;
		while(true)
		{
			if(now>=n)break;
			levels++;
			div*=2;
			now+=(int)Math.Pow(2,levels);
		}
		int min=int.MaxValue;
		int vv=(int)Math.Pow(2,levels);
		int tt=1;
		while(true)
		{
			int kk=vv*tt;
			tt++;
			min=Math.Min(min,Math.Abs(kk-tot));
			if(kk>=tot)break;
		}
		Console.WriteLine(min);
	}
}
1 Like