ZIO problems

sudheerays123 · October 31, 2019, 5:49pm

Pls help me guys …
Only 10 days left for ZIO …
Not able to do these problems …

@anon38711361 @g_ajeet_11000 @mathecodician @p_square

Thanks

sudheerays123 · November 2, 2019, 6:30pm

I tried to do the ZIO 2009 , P1 ( the tiling problem ) but I am not able to do it . Can you pls help @denjell ( as always as you did) ?

Link for the problem : https://www.iarcs.org.in/inoi/2009/zio2009/zio2009-qpaper.pdf

Thanks a lot
Sudheera Y S

sudheerays123 · November 2, 2019, 6:39pm

Hello @all ,

I found a very good article on Tiling problems , so I would love to share with you guys

Here is the amazing website I found: Way to solve Tiling Problems - Journey of CP with DP

@denjell You will definitely love this website

Hope all of you guys find it useful

Thanks !
Sudheera Y S

sudheerays123 · November 6, 2019, 11:22am

Somebody Plsssss help me

Thanks !

sudheerays123 · November 6, 2019, 11:31am

Pls help to solve this problem @denjell !!!
I am not getting it

Thanks a lot !!

sudheerays123 · November 6, 2019, 1:25pm

I found a solution for this problem which i didnt understand
Here is the solution : gEh2SH - Online Java Compiler & Debugging Tool - Ideone.com

Can someone plssssss help me understand what the code is even doing ?

Thanks a lot !!!

anon95832944 · November 6, 2019, 2:27pm

DP(i, j, k) is the number of sequences from column n to column j(inclusive) and the last connected band is in column j in row i and you’ve currently encountered k red bands modulo 2 (so k is only 0 or 1)

sudheerays123 · November 6, 2019, 2:44pm

Why are they taking modulo 2 ?

And even in the code everywhere they are taking modulo 3
Why ?

anon22682649 · November 6, 2019, 3:24pm

This is my solution for ZIO 2007 Ques 3

@sudheerays123 you mention taking average in your first post.
What you need to actually do is to is slightly different.

Follow the following steps:

Write down the coordinates for a specific axis in ascending order.
Let n = no. of people.
For each axis, consider the cost of moving in a certain direction. For eg. in z axis, cost of moving up is 3 while that for moving down is 1. So, 3*(n-1)/(3+1) people will move down (let this number be d) and 1*(n-1)/(3+1) people will move up.(let this number be u)
Now, from the start of your list of ascending sorted list of coordinates, cross out u people. From the end, cross out d people. You’ll be left with one coordinate, and that will be your answer.
Carry out the above steps for each coordinate.(ie, x, y and z)

Now,if you notice, the cost of moving in either direction in x or y axis is same. So, for those two axes, you can directly take the median for the coordinates as the answer. That will be equal to crossing out 2*(n-1)/(2+2) coordinates from the bottom and the same number of coordinates from the top.

I’ll do the procedure for the z axis in part c of the question.
Number of people here is 21.
List of z-coordinates (unsorted) :

List

69
43
33
48
66
84
3
43
10
1
74
54
39
65
43
20
12
37
41
36
16

List of z-coordinates sorted

List sorted

1
3
10
12
16
20
33
36
37
39
41
43
43
43
48
54
65
66
69
74
84

Crossing out 5 numbers from top and 15 from end, we are left with coordinate ‘20’ which is the answer.
You’ll need to do this individually for x and y also.

EDIT 1: I had used the term ‘weighted average’ for the procedure I’ve presented. I used it to hint the OP that he was thinking in the right direction. However, the term actually means something different and I’ve removed that phrase to avoid any confusion.

sudheerays123 · November 6, 2019, 7:29pm

Thanks a lot for such a detailed solution !
First I was confused why you have crossed out u people from the start when you should cross them from the end and then understood that you have arranged them in ascending order

And i even found that we need not sort the whole numbers for example in the Z axis of c subtask we can just write the first 6 numbers
but thanks for writing the whole array again ( it was easy to understand )

I learn something new today ( weighted average , which i hadnt even heard before )

Thanks a lot again @anon22682649 !!

anon95832944 · November 6, 2019, 7:36pm

Because we only care if we’ve taken an even number of red bands. Sure, you could instead let the third parameter of the dp be the number of red bands (0, 1, 2…) which would also give you the right answer. But when you’re going to calculate the answer, you’re going to take the sum of the dp values at k = 0, k = 2, k = 4 etc even numbers. If you wanted to find number of Sequences such that you choose X red bands then you would use this method as you care about the specific value of the number of red bands.
But as we only care about the parity in the ZIO question, we take k mod 2. So now the answer is stored in the dp values where k = 0

sudheerays123 · November 6, 2019, 7:41pm

Oh , Now i understand why they have taken parity , but what i dont understand is :

In the output they have done dp[0][0][0] + dp[1][0][0] + dp[2][0][0] . Why ?
Why everywhere in the recurrence they have done ( i+1)%3 or ( i+2)%3 ?

anon95832944 · November 6, 2019, 7:44pm

DP(0, 0, 0) is number of paths from coulmn n to column 1 that end in the first row and have even number of red bands.
DP(1, 0, 0) is number of paths from coulmn n to column 1 that end in the second row and have even number of red bands.
DP(2, 0, 0) is number of paths from coulmn n to column 1 that end in the 3rd row and have even number of red bands
So summing these gives desired answer as All possible paths are encompased in these 3 dps.

sudheerays123 · November 6, 2019, 7:45pm

OH OK !!
Now i understand
Thanks a lot !!!

anon95832944 · November 6, 2019, 7:48pm

If i=0(Row is 1)
(I+1)%3 = 1
(I+2)%3 = 2

If i=1(Row is 2)
(I+1)%3 = 2
(I+2)%3 = 0

If i=2(Row is 3)
(I+1)%3 = 0
(I+2)%3 = 1

it’s just an Implementation trick to get the other 2 row values by using mod

sudheerays123 · November 6, 2019, 7:50pm

OH OK !!

Now i understood completely , should implement now
Thanks a lot for the explanation @anon95832944

A newbie for dp here !
So didnt understand this

Now this is clear
Thanks a lot !

sudheerays123 · November 6, 2019, 7:52pm

Will try to write a different recurrence ( opposite to what they have done in the code )

Thanks a lot !

denjell · November 6, 2019, 9:09pm

Are you able to follow the solution idea of ZIO 2006 , P3?

If yes then you can apply the same idea to ZIO 2009 , P1.
Only difference is that no 4 corners should be present in our tiling.
This is the same as saying that the pattern
==
should not be used.
I solved this constraint by not allowing the
=
pattern (on its own). I only allow it with an added L-shape (for example: =L).
Recurrence will then be something like this:
f(n) = f(n-1) + 2g(n-2) + 2g(n-4)
g(n) = f(n-1)+g(n-1)
Note: Only the formula for f(n) is changed. We omitted the f(n-2) term which is used when we add = pattern. We add 2*g(n-4) to account for the =L and the flipped version of it.
Important is that we need to find initial values of f for n <= 4. Because there we don’t need the aditional L-shape.

sudheerays123 · November 7, 2019, 5:15am

Yes , For this problem also i wrote a recurrence but getting wrong answer

But this is allowed to use

Only one pattern which is not allowed is ==
then why are you not considering the case of =| ?

Thanks a lot !

anon11129538 · November 7, 2019, 5:28am

Hey, do you still need help with 2012 Question. 4? I was able to get all correct answers.