ZIO problems

help
, ,
72

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 !

1 Like
73

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

Thanks a lot !

2 Likes
74

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.

1 Like
75

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 !

1 Like
76

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

1 Like
77

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

Thanks a lot !
@anon11129538 !

1 Like
78

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 !

1 Like
79

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…

81

Here is the solution for z axis @sumit_king

2 Likes
82

yeah, got it…

83

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.

1 Like
84

It should be f(n-2) not f(n-3) right ?

If so , it is the same old formula :sob:

1 Like
85

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)

grafik

2 Likes
86

Oh ok
Thanks a lot ! , The excel is cool
Will try to understand the recurrence

Thanks a lot @denjell

1 Like
87

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?

2 Likes
88

@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 :slightly_frowning_face: )

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

  1. My procedure works ONLY when 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.
  2. My solution is not a generalized algorithm. I exploited the fact that I had testcases, in this case three testcases. This is much like the things you do in an MCQ test.
  3. The solution implicitly assumes that one of the people is already in the optimal coordinate. In other words, the optimal coordinate must be one of the coordinate where there is a person. However this is neither guaranteed in the question, nor I have proved this fact. So, mathematically speaking, my solution is unacceptable because it uses unproved facts to prove something else.

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

2 Likes
89

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 !!!

2 Likes
90

I was able to solve ZIO 2014 , Q3

2 Likes
91

Can you give me some hints on how I could solve it? Also did my solution for 2012 Q4. makes any sense?

1 Like
92

doing it…

1 Like