ZIO 2015 Discussion

general
21

@Organic-Shilling I’m not exactly sure what you did for Q2 but it looks wrong to me. I think you’re doing a lot of double counting.

This is how I did Q2:

Consider the sequence EELLEELELLEL, you can write it as EELL + EELELL + EL. But you cannot split EELL, EELELL or EL further. So they are the basic units of any sequence.

So the number of units with 1 train is 1, only EL is possible.

2 trains: E(EL)L (brackets for clarity)

3 trains: E(EELL)L, E(ELEL)L

Now we need to find the total number of sequences of length n.

I will do the second part of Q2:

for K = 4, you cannot have a unit of more than 3 trains.

So, to get N trains, we can:

  • Put a unit of 1 train, then a
    sequence of N - 1 trains
  • Put a unit of 2
    trains, then a sequence of N - 2 trains
  • Put a unit of 3 trains, then a
    sequence of N - 3 trains

i.e. f(N) = 1 * f(N - 1) + 1 * f(N - 2) + 2 * f(N - 3)
(there are 1, 1, and 2 units of length 1, 2, and 3 trains respectively)

There is only one sequence of 1 train: EL

There are two sequences of 2 trains: EL EL, E(EL)L

There are 5 sequences of 3 trains: EL EL EL, E(EL)L EL, EL E(EL)L, E(EELL)L, E(ELEL)L

So we get base cases f(1) = 1, f(2) = 2, f(3) = 5.

f(4) = 5 + 2 + 2*1 = 9

f(5) = 9 + 5 + 2*2 = 18

f(6) = 18 + 9 + 2*5 = 37

f(7) = 37 + 18 + 2*9 = 73

f(8) = 73 + 37 + 2*18 = 146

So the answer is 146. You can easily extend this for the third part:

f(9) = 146 + 73 + 2*37 = 293

f(10) = 293 + 146 + 2*73 = 585

The first part requires a modification of the function, or you can even do it by hand I guess. My answer was 90.

2 Likes
22

http://textuploader.com/ob9a
This is the list of the possible train sequences.If 90 is right according to you find a contradiction in my sequence list.

23

@Organic-Shilling 125346 is not possible rite?

24

See, in question 4, all of you are considering going to 2 and then going somewhere else, that is not possible. 2 is the destination, one would not go after reaching the destination. And if that was allowed, they would have given some hint in the example.

25

What have been the cut offs for last years?..and by when is the result declared?

26

@bs1sv13_3137 If it wasn’t,they would have given some hint in the example. LOL

27

It is Possible. 6 enters and leaves, 5 enters, 4 enters, 4 leaves, 3 enters and leaves then 5 leaves, 2 enters and leaves, 1 enters and leaves. Voila!

28

If that were the case there would be no flights going out of 2. Your job is to maximize no of flights period. If they wanted us to think like that they would have mentioned is explicitly.

29

Nvm, i interpreted it wrongly.

30

513426 doesn’t work then.

31

Yep, its not possible. My solution is wrong. :frowning: :frowning: :frowning: Do you think the solution posted by the other guy is right ?

32

I got 90 for the first one but my other answers vary.I really haven’t checked his solution but he is my classmate (LOL) so i will discuss it with him tomorrow and let you know :).

33

I am pretty sure mine is correct, but you need to present the list in terms of E and L. Not sure what notation you are using

I need to get this right, otherwise my total is only 40 :\

I made two mistakes in sub questions…

34

Mine was disproved. 513426 is not possible and I have counted it and many similar to it. So it is quite possible that yours is correct. My total is 50 but I am in 12th so I also am pretty scared that I might not appear for the second round.

35

I am in 12th as well. My total is 40 not including the second question; I’m pretty sure it’s right so in that case it’s 60.

I’m writing ZCO though so it should be okay.

36

I’ve written a brute-force algorithm to enumerate the possibilities.

The answers match up with what I’ve posted before.

Here is the program on ideone: http://ideone.com/kVLtjx

Below are the lists of sequences:

A: https://www.dropbox.com/s/figpn4kl0xwjdya/2A.txt?dl=0

B: https://www.dropbox.com/s/umwp9i1k5qbwp5n/2B.txt?dl=0

C: https://www.dropbox.com/s/rshidqvlzh2lyrx/2C.txt?dl=0

Edit: Note that E means Enter and L means Leave

37

http://textuploader.com/ob47 Q2a
http://textuploader.com/ob4v Q2b
http://textuploader.com/ob4n Q2c
Here are the corresponding final sequences. They appear to be right. Congrats.They match your text files line by line. @superty

38

Cool! Okay, so I have 60, most probably good enough to get to the next level.

Could you update the main post with all the corrected answers? Or you could write an answer and accept it.

Edit: Or I could do it, I need reputation so that I can comment on others posts :stuck_out_tongue:

39

@superty definitely good enough, My 50 marks are probably good enough. Add me as a friend on fb, i’m in ronaq’s friend list.(aditya puranik)

40

Added, I’m arjun