And I am unable to solve these 15 problems even after trying very much and I thought that I shouldn’t drag ZIO for really long time so I am asking you guys for help
Here are the 15 problems which I couldnt solve :
Pls help me!
I can answer the last one i.e, ZIO 2004, P3:
So it goes like this,
The things we need to understand from the problem:
It is asked to convert some particular roads connecting cities, to a highway, such that all the cities are connected. It doesn’t matter how large the distance becomes to travel one city to another.
Given in the question, that the total cost of constructing the highways must be as low as possible.
From statement 2 which implies : length of the road is directly proportional to the cost of constructing highway i.e, more the length of the road more is the cost to construct it.
In the solution image, the highways connecting the cities are of the least length. Thus, retaining the statement 2.
Another way to think about it is that you need to find a non cyclic path such that all cities are connected with the least road lengths (for least total cost).
Please let me know if you find the solution for, ZIO 2007 , 1st question and ZIO 2006, 3rd question. I understood the question completely but I am not able to come up with a correct solution. So please share with me when you find it and I will do the same.
Can you explain which facts you don’t understand at Problem ZIO 2007 P1 and ZIO 2006 P3. The link with a solution is very clear and helpful. If you tell me what you don’t understand then I will try to explain it further.
I managed to solve the (a) sub-question by watching the increasing frequency of Valleys (V) and I came up with the solution for it that is 2 to the power n-1 where n is the number of folds as I could see that after 1 fold I get 2 to the power 1-1 i.e, 2 to the power 0 which is one and for 2 fold is 2 to the power 1 which is 2 and so on. So for 10 folds it will be 2 to the power 10-1 which is 512 Vs.
But I could not answer the patterns asked in the other two sub-questions.
Don’t tell the direct answer just give a hint I want to figure it out myself.
The pattern which appeared in the previous fold reappears in the next fold in the front, as you can see the pattern formed by 3 folds is repeated as it is in front of the 4 fold’s pattern. You can even see the 2 fold’s pattern reappeared in front of 3 fold’s pattern.
But still I can’t observe any repeating patterns for (c) part, the last 10 ending patterns.
Yes! I get it!
The pattern in the second half is just reversed and inverted pattern of the first half (ignoring the middle element).
Thank You @denjell it was fun to solve with you.
Let’s get move on to the next one the 2006, P3:
The question is really straight forward you are given two tiles of dimension 2x1 and 3x1 and you are asked to find the number of ways you can arrange the tile in a given area.
This problem can be solved by writing an algorithm using DP , but how could you solve it without programming and by just using pen and paper. I have no Idea about it.
Ya, I know it I can easily implement an algorithm for that but how could we solve it using pen and paper. @sudheerays123 Tell me if you ever gave a ZIO exam, are we allowed to write code for the problem or can we only use pen and paper?
If we are allowed to solve problem by using code then we can just write a DP algorithm for it and if we can’t code then I have no idea how to solve it.
Just use the given formulas with the appropiate starting values (base cases you can analyse easily).
f(n) = f(n-1) + f(n-2) + 2g(n-2)
g(n) = f(n-1) + g(n-1)
f(0) = 1
f(1) = 1
g(0) = 0 (cannot tile a single square),
g(1) = 1 (use exactly one L-shaped tile)
And then calculate the remaining values by hand up to f(12). No need for a computer program. The whole problem here is to come up with the 2 formulas. Values up to small values of n can be done by hand. Would be another story if you were needed to tile a rectangle of size 2*10000.
As you can see we can easily calculate every function value because they depend only on values we have calculated before. There is no cross connection between functions values with same n.
Take the values with caution, I calculated them in my head
Okay I understood, you started with the base cases what I did was I started with the f(8) to the base cases forming a tree graph which made it difficult to evaluate.
Thanks I can do the rest of them it’s easy.
That is also a relevant observation. If you implement the formulas by using recursion there will be several values that are evaluated many times. Therefore you can precalculate all values up to a specific value (bottom-up strategy) like we did here or you can remember all values that were already calculated (memoization). Both are relevant topics for dynamic programming.
