ZIO problems

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.

sudheerays123 · November 7, 2019, 5:30am

Yes , I need help in that problem , Can you pls help me by giving a hint for the problem ?

Thanks a lot !
@anon11129538 !

sudheerays123 · November 7, 2019, 5:44am

How did you get this ? @anon22682649
I saw formulas for Weighted average and there was different formula

Can you pls tell me how you got this formula ?
I used this formula and got all of them correct but now i have a doubt in the formula

Thanks a lot !

sumit_king · November 7, 2019, 5:53am

Zio 2007 P3
The question is really interesting…I was only able to do the first subtask because the value of k is constant in that.So i will tell u how i solved the first subtask
I took the median of all the values i and median of all the values of j seperately… and then the median m for i and n for j was the answer (m,n,k)… in next subtasks the value of median of i and the value of median of j comes out to be correct but the value of k i am not able to find…

sudheerays123 · November 7, 2019, 5:58am

Here is the solution for z axis @sumit_king

sumit_king · November 7, 2019, 6:00am

yeah, got it…

denjell · November 7, 2019, 7:02am

Hi,

you are absolutely right, i missed this case. But it is easy to add. Just add a f(n-3) to the formula of f(n) and you should be fine.