ZIO 2015 Discussion

general
13

@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
14

@Organic-Shilling 125346 is not possible rite?

15

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.

16

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

17

How did you solve question number 4. I mean brute force is way too hard and without any clever algorithm it is almost impossible??

18

Are 90, 146 and 585 for question 2 confirmed? Because those are what I got too.

19

Well for Q2 , how can train 5 enter BEFORE train 1??
I have a feasible solution as in the image

Explaination 1

Page 2

E1 __ __ __ __ __ __ __ __ __ E6 L6 (since each train can come in a specific order…)

Here E1 means train has Entered while its train no 1
Since we know when can each train go, we can find no. of ways
We first select the position of E2 then E3 … When we are at last node ,we note no of ways ,move up a branch and similarily find all the ways

I am damn sure this answer is correct

20

@c1_6 Depends on what you mean by confirmed.

I wrote a program that basically checks every possible sequence and then reports the total number of valid sequences, which agreed with this answer.

There is no official confirmation though.

Edit: Here’s my explanation:
http://discuss.codechef.com/questions/56777/zio-2015-discussion?page=1#56884

1 Like
21

@superty I tried reading your answer, but my notation and method was far different … basically brute force.

Will an answer key be released? And is it true that the cut-off is 30 for class 11th students?

22

You’re right. I saw a flaw in my answer…
I assumed that the sequence EEEELLLLEELL is an illegal sequence but as it turns out my answer is incomplete

23

So How many marks is everybody getting ? Mention your marks and class in the comments.
50 marks 12th grade

24

No reputation == No comments
Also I am class 12 and marks are 40 (two epic mistakes in one sub part each of Q1 and Q3 + total downfall in Q2).

25

@Organic-Shilling No comments for me too - Class 11th, 70 marks (got 4c wrong)

26

Class 10th. 50 Marks.

27

Yes but I am a little weak in algorithms

28

@Organic-Shilling

Q2)

your answer for part b and c are correct (even I got the same)
but for part (a) i got 96

given n=6 & k=8 (Ti denotes train i, E-enter, L-leave)

first T1 enters(obviously)
now since k=8 we can have maximum of 4 more trains entering and leaving before T1 leaves

case 1:

4 trains(T2 to T5) enter and leave before T1 leaves,that is, fix the position of T1 as 5 in the output sequence:
there are 14 possible ways in which T2 to T5 occupy the first 4 positions in the output sequence(can be easily verified)

For each of these 14 ways,there is only 1 way in which T6 can occupy the sixth position(EL)

So, 14 x 1 = 14;

case 2:

3 trains(T2 to T4) enter and leave before T1 leaves,that is, fix the position of T1 as 4 in the output sequence:

there are 5 possible ways in which T2 to T4 occupy the first 3 positions in the output sequence(can be easily verified)

For each of these 5 ways,there are 2 ways in which T5 & T6 can occupy the 5th and 6th position(EELL and ELEL)

So, 5 x 2 = 10;

case 3:

2 trains(T2 , T3) enter and leave before T1 leaves,that is, fix the position of T1 as 3 in the output sequence:

there are 2 possible ways in which T2 & T3 occupy the first 2 positions in the output sequence

For each of these 2 ways,there are 5 ways in which T4 to T6 can occupy the last 3 positions.
So, 2 x 5 = 10;

case 4:

1 train(T2) enter and leave before T1 leaves,that is, fix the position of T1 as 2 in the output sequence:
there is only one possible way in which T2 occupies the first position in the output sequence
For this one way,there are 14 ways in which T3 to T6 can occupy the last 4 positions.

So, 1 x 14 = 14;

So far total output sequences generated: 14+10+10+14=48;

case 5:

zero trains enter and before T1 leaves,that is, fix the position of T1 as 1 in the output sequence:
now again we have 5 more trains(T2 to T6) which have 48 output sequences as shown above.

hence total no. of output sequences = 48x2 = 96;

ANS:96

29

I am getting 50. Grade 10. Can i be selected with this much . made a silly mistake , else would have got 60

30

@a1a99_3

The answer for case 5 is 42, not 48. The sum of previous cases is not equal to the last case, it needs to be calculated separately.

@adityakhanna1999

It is unlikely that cutoff for 10th will be more than 40.

31

@superty

for case 5

now you have T2 to T6 instead of T1 to T5 and rest is the same

even though u calculate separately u will again repeat cases 1 to 4 and hence the count is 48 only.

32

What is expected cut off for class 11?
Last year in class 10 my score was 40 and class 10 cut off was 25 and 11 cut off was 30.
This year my score is 35