hi!
my answer for 4th question is
a) 9, b)8, c)11
i have doubt in answers for this question.
hi!
my answer for 4th question is
a) 9, b)8, c)11
i have doubt in answers for this question.
@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
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
For the fourth one i got 10, 9 12
pretty sure.
for 12:
baccbcacaaca
412331341312
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
We can reach E2 from E1 in 2 ways and so on
If wrong please explain
@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.
I am pretty sure you can’t get 127 or 119.
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.
@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
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
@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:
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.
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.
How did you solve question number 4. I mean brute force is way too hard and without any clever algorithm it is almost impossible??
Are 90, 146 and 585 for question 2 confirmed? Because those are what I got too.
Well for Q2 , how can train 5 enter BEFORE train 1??
I have a feasible solution as in the image
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
@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
@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?
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