It should be f(n-2) not f(n-3) right ?
If so , it is the same old formula
It should be f(n-2) not f(n-3) right ?
If so , it is the same old formula
No it should be n-3 because we add =| and continue with a rectangular space that is 3 columns less wide.
Checked the formulas in Excel and they give correct output:
f(n) = f(n-1) + f(n-3) + 2g(n-2) + 2g(n-4)
g(n) = f(n-1)+g(n-1)
Oh ok
Thanks a lot ! , The excel is cool
Will try to understand the recurrence
Thanks a lot @denjell
Alright, I will write couple of steps i followed for solving the c part, I hope you will be able to get some hint from it.
11th - Final Stage
8 22 47 75
11 33 86
12 95
28
40
1 3 6 7
2 4 8
5 11
9
10
Now observing that 95
was inserted in 3rd row when 11th
item was added. The only way for 95
to be inserted in 3rd
row would be by pushing it down from 2nd
row. Which means 95
would originally be in 2nd
row, meaning it would be in place of 86
.
So, third row before inserting 11th
element would be 11 33 95
, what about 86
then?
For 86
to be in 2nd
row, it must have been pushed by 75
. Meaning 75 was the last element to be inserted.
Note:- Somethings will only make sense when u take notebook entry into consideration, think why was only 75
able to push 86
down, when 47
could have easily done that?
10th Stage
8 22 47 86
11 33 95
12
28
40
8 was 10th
9th Stage
11 22 47 86
12 33 95
28
40
11 was 9th
8th Stage
12 22 47 86
28 33 95
40
86 was 8th
7th Stage
12 22 47 95
28 33
40
95 was 7th
and so on…
If u need help, feel free to ask.
Btw, were you able to solve 2014 Q3 and Q4?
@sudheerays123
For ZIO 2007 Q3
I’ve updated my answer and removed the phrase 'weighted average. I used it to indicate that you were looking in the right direction. But looks like it led to some confusion. My apologies for that. (a more accurate phrase for what I did would be 'median with conditions; but actually its not even median for the z axis. I don’t know what it is called )
You wanted to know that how I came up with the formula. What It’s doing that its dividing the data in four parts and selecting 3 (or 1) part from it. Hence the (3+1) in denominator. I’ve explained everything below. Also know that my solution is not a ‘general’ solution. It’s an exploitation of the fact that the testcases are given to us, and I just did the most logical process at each step. You may scroll down in this post to read the flaws I’ve mentioned.
The procedure I’ve come up with isn’t something I would call intuitive or anything that would strike you while reading the question. I came up with that solution by looking at the given coordinates for each of the three parts.
I’ll detail it out here
I was very inclined towards taking an average but obviously that meant that the answer may come out in decimal, which cannot be possible. Now, there could’ve been some method to handle decimal coordinates, but I wanted to explore all options that would straight away give me an integer answer , before I tried to think what to do with decimals.
Then I thought of taking median. This would give me an integer answer in all three cases. As there are odd number of people in each part, the median would be one of the given coordinates, i.e. an integer.
Next step was some practical thinking. Let’s say you want to meet a friend at one of the many restaurants which lie on the road connecting his home to yours. Your car uses 1 litre of fuel for every 10 km, while your friend’s car uses 1 litre of fuel for every 15 km. You want to minimize the total amount of fuel used. For the same amount of petrol, your friend covers larger distance than you. So the restaurant you choose to meet should be more closer to your home. I hope you understand this part.
I applied the same logic to the z-axis. Going up takes 3 units of fuel; down takes 1 unit. So more people should go down than up in the optimal situation.
Finally I had to come up with a number which will be my answer. I divided my coordinates into (3+1) parts = 4 equal parts. 3 groups of these people will go down, 1 group will move up. Now you’d realize that the number of people in all cases in odd. Hence dividing by 4 will give decimal answer, which i wanted to avoid from the very beginning. However, I observed that in all cases if you subtract 1 from the number of people, you get a multiple of four.
Even in x and y axis, The cost is 2 and 2 for either direction. So I need to divide data into 2+2= 4 groups. And (n-1)
is divisible by 4.
Now, everyone except one person has to move either up or down. What happens to this one person who is left out? Well, he is already on the optimal coordinate for the specific axis. And that coordinate is the answer.
For the x and y axis, median works, because even if you’re using my procedure, you’d be indirectly calculating the median.
Some flaws to prove my solution wrong
n
can be represented as 4k + 1
. Otherwise you get a decimal answer. And not getting a decimal answer was the first motivation to think in whatever direction I did.Yet I posted my solution here, because it gave correct answer for all three parts. It may inspire someone else to reach at a solution which is actually correct.
Or maybe, my solution is totally different from what you’re actually supposed to do :-p
Now i understood this solution , yes the advantage in ZIO is that you have the testcases to exploit
Thanks a lot for such a detailed solution @anon22682649 !!!
I was able to solve ZIO 2014 , Q3
Can you give me some hints on how I could solve it? Also did my solution for 2012 Q4. makes any sense?
doing it…
Hint : The number of passwords starting with 2 and having length k is equal to the number of passwords starting with 6 and having length k is equal to the number of passwords starting with 4 and having length k is equal to the number of passwords starting with 8 and having length k
The number of passwords starting with 1 and having length k is equal to the number of passwords starting with 3 and having length k and is equal to the number of passwords starting with 7 and having length k is equal to the number of passwords starting with 9 and having length k
Now having this , continue to get the answer
Hello @anon11129538 ,
I understood the solution , I knew that we should find the order from the last but i was not writing the shelf entry again , making it complicated
I learnt how to solve these problems and learnt new
Thanks for such a detailed solution !!
For ZIO 2002 question 3,
This question is based on logarithms. So only if you have a basic understanding of it, I would recommend this problem to you.
The easiest way you see is having weights of 1g, 2g, 3g, 4g … upto 4000g
Now, in the question it is written that the number of weights should be < 11 (2^11 = 2048).
Explanation:
The numbers in the question (1, 2, 4…) can be expressed in log x base 2, where x is any number between 1 and 4000.
Now, we can’t just replace any integer with an integer in the set.
Replacing a number will break the whole sequence of the set. Suppose to reach 3800, it needed 128 4 times, and you have replaced it by some other number. Then the whole sequence has gone haywire. There are some numbers which are totally dependent on that number to get to the destination.
Eg: The number to weigh is 3 and we have removed 1 and put 7.
Now there is no way to weigh 3, try any combination.
Thus, we need to bring up a defined set.Let me remind you that a defined set is one which has some logic behind its making.
In the question, the given set is made of powers with base 2, and exponents ranging from 1 to 11
Also, the defined set has to increase the difference between two consecutive numbers as we are traversing it in ascending order else we cannot reach our target.
So, when we are given the set with powers of 2, what can be the next set. We have shortened it to only one thing applicable.
Powers. Powers is a defined set with increasing gap between the numbers as we traverse it in ascending order. As we want the number of weights use to weigh a single thing to be the smallest, but also the numbers in the set to be smaller, the answer is powers of 3.
So the set is {1, 3, 9, 27, 81, 243, 729, 2187}.
What is the answer to part b?
As these exponential forms of powers of 3 can be written as logs of base 3, the answer is n - (1 + 3 + … log_3(n)).
I hope that this was of help. .
For ZIO 2017 P3,
So the answer goes like this,
First, we initialize maxi to the max of all h[i]. That is the minimum answer.
Then for each i from 1 to n, we increase seek by maxi - h[i].
Here seek is the maximum number of games a child is ready to seek.
Here two case arise:
answer is n
We will be initializing i to maxi. Now, we increment i by 1 and increment seek by n.
Now, if seek >= i, , The answer is i. Else keep on incrementing.
Why i instead of maxi?
As we are increasing the number of rounds, the number of seekers have to match the new number of rounds, which is being stored in i.
Hope this helps .
Thanks for detailed solution
But unfortunately i dont know logarithms and this is the only problem where logarithm was used i guess so what should i do ? @aryan12
Will do this problem once i am bit familiar with logarithms
Thanks for taking your time out
Sorry
As this was a pretty old problem, I suggest leave it coz these years I dont think logarithms are in the syllabus for ZIO
Is this n or maxi as it is not working for subtask a
Even here
Thanks a lot !
Didnt understand this , Can you pls elaborate ?
and why this method works ?
Thanks a lot @aryan12 !
Oh ya sorry, its maxi. I made a mistake while typing it.
Thanks for pointing it out.
We will be initializing i to maxi. Now, we increment i by 1 and increment seek by n.
The lowest number of rounds can be maxi, and then we keep on incrementing so that we find the lowest number of rounds required only.
Whenever we encounter the following condition, we stop, else it keeps going on:
if(seek >= i)
As we need only a single person to become a seeker in one round. So when this statement is true, it means a single child can always be the seeker if we look at the optimal solution.
If not, then we increment i, and then each child can become a seeker once more when i is increased. As there are n childs, there the seek variable will increase by n.
Hope you understood this explanation.