ZIO problems

Hello guys !!!

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!

ZIO 2006 , P3 :
link : https://www.iarcs.org.in/inoi/2006/zio2006/zio2006-qpaper.pdf :white_check_mark:
Saw a solution but didnt understand
link of the solution : https://www.iarcs.org.in/inoi/online-study-material/topics/dp-tiling.php
Better explanation : https://journeywithdp.blogspot.com/2018/07/way-to-solve-tiling-problems.html
Credit : @denjell

ZIO 2009 , P1:
link : https://www.iarcs.org.in/inoi/2009/zio2009/zio2009-qpaper.pdf :white_check_mark:
very similar to the last problem
Credit : @denjell

ZIO 2011 , P4 :
link : https://www.iarcs.org.in/inoi/2011/zio2011/zio2011-qpaper.pdf :white_check_mark:
Solution : https://en.wikipedia.org/wiki/Burrows–Wheeler_transform

ZIO 2002 , P3 :
link:https://www.iarcs.org.in/inoi/2002/zio2002/part-a-qpaper.pdf :white_check_mark:
solution which I didnt understand : https://www.iarcs.org.in/inoi/2002/zio2002/part-a-solutions.txt
Credit : @aryan12

ZIO 2012 , P4 :
link : https://www.iarcs.org.in/inoi/2012/zio2012/zio2012-qpaper.pdf :white_check_mark:
Credit : @bharat8i

ZIO 2014 , P4 :
link : https://www.iarcs.org.in/inoi/2014/zio2014/zio2014-qpaper.pdf

ZIO 2017 , P3 , PART C :
link : https://www.iarcs.org.in/inoi/2017/zio2017/zio2017-question-paper.pdf :white_check_mark:
Credit : @aryan12

ZIO 2017 , P4 :
link : https://www.iarcs.org.in/inoi/2017/zio2017/zio2017-question-paper.pdf

ZIO 2015 , P2 :
link : https://www.iarcs.org.in/inoi/2015/zio2015/zio2015-question-paper.pdf :white_check_mark:
solution : https://www.iarcs.org.in/inoi/2015/zio2015/zio2015-question-paper.pdf
Credit : @swetanjal

ZIO 2016 , P2 :
link : https://www.iarcs.org.in/inoi/2016/zio2016/zio2016-question-paper.pdf :white_check_mark:
Credit : @druh @Whiplash99

ZIO 2007 , P1 :
link : https://www.iarcs.org.in/inoi/2007/zio2007/zio2007-qpaper.pdf :white_check_mark:
Credit : @g_ajeet_11000

ZIO 2007 , P3 :
link : https://www.iarcs.org.in/inoi/2007/zio2007/zio2007-qpaper.pdf :white_check_mark:
taking average is not working
Credit : @cdsnehit

ZIO 2008 , P1 :
link : https://www.iarcs.org.in/inoi/2008/zio2008/zio2008-qpaper.pdf :white_check_mark:
Credit : @denjell

ZIO 2004 , P4 :
link : https://www.iarcs.org.in/inoi/2004/zio2004/zio2004-qpaper.pdf :white_check_mark:
Credit : @g_ajeet_11000

ZIO 2004 , P3 :
link : https://www.iarcs.org.in/inoi/2004/zio2004/zio2004-qpaper.pdf :white_check_mark:
Credit : @g_ajeet_11000

ZIO 2004 , P5 :
link : https://www.iarcs.org.in/inoi/2004/zio2004/zio2004-qpaper.pdf :white_check_mark:
Credit : @g_ajeet_11000

Pls help me if you know solutions of any of these problems

Thanks
Sudheera Y S
:slightly_smiling_face::smile:

1 Like

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:

  1. 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.
  2. Given in the question, that the total cost of constructing the highways must be as low as possible.
  3. 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.

Refer the images for more explanation:

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).

Ask if any more queries.

G Ajeet

3 Likes

I understood it completely
Thanks a lot !

2 Likes

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.

1 Like

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.

1 Like

See here’s what I understood from the ZIO 2007, P1:

  1. The formation of the Valleys( V ) and Hills( Inverted V ) are alternative, refer the image to understand what I mean.

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.

Thank You

2 Likes

What i observed:The actual layer can be put into the next step with a gap between all entries. The gaps can be filled up in the next step with the alternating pattern. It should be enough to propagate only 5 elements at the front (for b) from step to step because 5 will be added in the step. For © you can use the same strategy at the end.
I haven’t done it myself so maybe the strategy fails :-).

3 Likes

I checked it with a paper for 4 layers and it seems correct. And you can also recognize a pattern when you propagate the values further.

2 Likes

Here’s the link to the answer sheet for the question paper, you can check whether your solution is correct.

I analysed your logic for the (b) sub-question and your observation is correct, whereas I found something interesting, here it is look it carefully.

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 © part, the last 10 ending patterns.:thinking::thinking:

Hoping that this triggers some idea in your mind.

Thank You for helping!

2 Likes

Try comparing pattern of first half with second half (ignoring the middle element). There is some observation you can make.

2 Likes

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.

Do you have any? please tell me.

1 Like

https://www.iarcs.org.in/inoi/online-study-material/topics/dp-tiling.php
Check this out!

1 Like

Exactly. I think this dp tiling tutorial is a very good resource for getting the approach for this problem.

1 Like

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.

1 Like

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.

3 Likes

Hmm, but it’s still problematic to solve two recursive functions simultaneously. Don’t you think?
If NO! then could you please solve the (a) part.
:smiley::smiley:

1 Like

I will show the way up to 4:

f(0) = 1
g(0) = 0 (cannot tile a single square),
f(1) = 1
g(1) = 1 (use exactly one L-shaped tile)
f(2) = f(1) + f(0) + 2 g(0) = 2
g(2) = f(1) + g(1) = 2
f(3) = f(2) + f(1) +2 g(1)=5
g(3) = f(2) + g(2) = 4
f(4) = 11
g(4) = 9

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 :wink:

3 Likes

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.

Thank you @denjell for helping us!:smiley::smiley::smiley:

1 Like

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.

3 Likes

Hello @g_ajeet_11000 ,

No we can’t code in ZIO, they will give you paper and you have to work on paper and pen

1 Like