ZIO 2015 Discussion

zio

#1

EDIT: These are the Answers for this years zio. In case of any discrepancy Write your answer and tag me.

>     Q1)a)7300000000, b)5322222, c)9666666666
>     Q2)a)90, b)146,  c)585
>     Q3)a)123, b)72, c)107
>     Q4)a)10, b)9, c) 12

Wasn’t it easy this year ?


#2

hi!

yeah it was kinda easy,

for question 1 we have the same answers, except for c)6666666644 yours is bigger

q2) couldn’t solve
3) same answers, someone told me that 127 is also possible for a) i will update when i get the method

  1. a)8 b)9 c)10

did you even consider going to to and then going back?


#3

hi!

my answer for 4th question is
a) 9, b)8, c)11

i have doubt in answers for this question.


#4

@bs1sv13_3137 , Here you go…
Number Frequency Cost Total Cost
your c) 6 8 7 56
4 2 8 16
*56 + 16 == 72
My c) 6 9 7 63
9 1 9 9
*63 + 9 == 72


#5

Ques 4 ) My routes. Line 1 = sequence, Line 2 = bool of movement movement, line 3 = airport number

C A C B C B B B B A A A C B A
1 0 1 0 1 1 1 0 0 1 1 1 1 1 0  == 10
0 0 0 0 0 4 2 2 2 4 1 2 4 2 2

A A A C A A B C C C B A B A C
0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 == 9
0 0 0 0 0 0 0 0 0 0 4 1 4 1 2

A A B A B C C B C A C A A C A
0 0 1 1 1 1 1 1 0 1 1 1 1 1 0 == 11
0 0 4 1 0 0 0 4 0 1 2 4 1 2 0

#6

For the fourth one i got 10, 9 12
pretty sure.
for 12:
baccbcacaaca
412331341312


#7

Wouldn’t the 3c be 119?

Select 3,5,6,8,9,10,13

Also how did you manage to do the second!!
I made a logic (which can be wrong). First we know that the order for 1 is
E1 __ __ __ __ __ __ __ __ __ E6 L6 (E Enter , L leave and no represents train no)
and we can see the arrangements as shown alt text

We can reach E2 from E1 in 2 ways and so on
If wrong please explain


#8

@sidmohla
No, 3c will not be 119. Here’s your combination.

3  5  6  8 10 13
4  7 10  6  4  9
B  G  B  B  B  R
*3 *3 *3       *3
12+21+30+6+4+27 = 100

Make a table for my values and you shall get 107.


#9

I am pretty sure you can’t get 127 or 119.


#10

Q2) part A logic. N = 6, K = 8. K = 8 means next four trains can enter in any order they like after which the last train must leave the yard. In any order because it doesn’t matter when they enter and leave each action costs 1 K and 4 trains entering and leaving will cost us 8 K. Now here are all the cases.Will will consider 6 fixed in all possible positions.

1*6*2345 ]- 2345 can be in any order so 4! = 24
12*6*345 ]- 345 and 12 can be in any order so 3!*2! = 12
123*6*45 ]- 45 and 123 can be in any order so 3!*2! = 12
1234*6*5 ]- 1234 can be in any order so 4! = 24
12345*6* ] - 12345 can be in any order so 5! = 120

24 + 12 + 12 + 24 + 120 = 192.
I tried to do part B with this method but it was very time consuming so I left it. I didn’t try C because I had given up.
EDIT: EXPLANATION.
What I have done is fixed the number 6 in the output place to a particular digit, then I am moving around whatever numbers I can to take a look at permutations. For instance in first line I say 2345 can be in any order. 2345, 5324, and so on can be created without hassle. I have taken its factorial. For those who don’t know what a factorial is google it and read about permutations.
@superty Because we are having trouble with deciding the correct solution I suggest we both make a text file of our possible cases and then we can see the subset of non-intersecting cases and decide.
EDIT: THIS IS WRONG, This logic generates cases which are not possible.


#11

@Organic-Shilling : Oh no! Blunder! I selected 3,5,8,9,10,13 but made a calculation mistake! ( Selection 8 : Added 18 instead of 6 (wrong step)) Aagh!.. Anyways I wish I could upvote (low reputation)(started using forums lately but no repo yet) THANKS

EDIT: Can you explain your answer more clearly


#12

My answers are
1a-3330000000
b-5322222
c-9666666666

2a-Dont know
b-Dont know
c-Dont know

3a-123
b-72
c-107

4a-10
b-7
c-11

Does anybody know answer of Q2 and how to solve it


#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.


#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