Discussion @ 1223. Chernobyl’ Eagle on a Roof @ Timus Online Judge

esbybb what is the so-called initial step for 2 eggs / 20 floors? [9] // Problem 1223. Chernobyl’ Eagle on a Roof 16 Mar 2016 03:44

spot check shows me that it should be 7 am i right? then the answer is 8 moves??

esbybb Re: what is the so-called initial step for 2 eggs / 20 floors? [8] // Problem 1223. Chernobyl’ Eagle on a Roof 16 Mar 2016 03:45

        EGGS=2, FLOORS=20
        (20 eggs, initial step = 7)
        e=20(20)
        7 14 17 18 19
        e=19(20)
        7 14 17 18 19 (+7, +3)
        ...(e=18..14 )
        e=13(20)
        7 14 8 9 10   11 12 13 [7 moves]
        (20 eggs, initial step = 7)

        (20 eggs, initial step = 6)
        e=5(20)
        6 1 2 3 4 5
        e=17(20)
        6 12 18 13 14 15 16 17 [8 moves]

        (20 eggs, initial step = 5)
        e=20(20)
        5 10 15 18 19 20
        e=17(20)
        5 10 15 18 16 17
        e=14(20)
        5 10 15 11 12 13 14

        (20 eggs, initial step = 4)
        4 8 12 16 20 17 18 ..
thanks! also what is the algorithm for this particular test case? thanks

esbybb Re: what is the so-called initial step for 2 eggs / 20 floors? [7] // Problem 1223. Chernobyl’ Eagle on a Roof 16 Mar 2016 05:13

or maybe step is not fixed at all? like step0=7, step1=6, step2=5?

esbybb Re: what is the so-called initial step for 2 eggs / 20 floors? [6] // Problem 1223. Chernobyl’ Eagle on a Roof 16 Mar 2016 05:19

+6 +5 +4 +3
6 11 15 18

5
6 1 2 3 4 5
10(or 11)
6 11 7 8 9 10
14(or 15)
6 11 15 12 13 14
17(or 18)
6 11 15 18 16 17
20
6 11 15 18 19 20
hmm for 2 eggs / 20 floors the answer is 6, this is weird

Edited by author 16.03.2016 05:21

esbybb Re: what is the so-called initial step for 2 eggs / 20 floors? [5] // Problem 1223. Chernobyl’ Eagle on a Roof 16 Mar 2016 05:29

2eggs 100floors (14)
+14 +13 +12 +11 +10 +9 +8 +7
14 27 39 41 52 62 71 80 88 95
39
14 27 39 28 29 30 31 32 33 34 35 36 37 38
100
14 27 39 41 52 62 71 80 88 95 96 97 98 99

Jane Soboleva (SumNU) Re: what is the so-called initial step for 2 eggs / 20 floors? [4] // Problem 1223. Chernobyl’ Eagle on a Roof 16 Mar 2016 06:15

IIRC for this task we need to save the last egg at all costs, until the moment we figure out the exact answer.
For 2 eggs / 20 floors, that would be:
1st try: 6, and if breaks — 1, 2, 3, 4, 5 in worst case for last egg (so it breaks when we figure out the answer for sure).
2nd: 11, if breaks — 7, 8, 9, 10.
3rd: 14, if breaks — 11, 12, 13.
4th: 17, if breaks — 15, 16
5th: 19, if breaks — 18.
6th: 20
So in worst case, 6 tries.
Then again, i didn't solve it yet, so i can't guarantee anything, but that's how i understood it from previous discussions.
And yeah, you already described it above, i didn't read. Sorry.

Edited by author 16.03.2016 06:26

esbybb Re: what is the so-called initial step for 2 eggs / 20 floors? [3] // Problem 1223. Chernobyl’ Eagle on a Roof 16 Mar 2016 23:02

the direction is right, step0 is the answer, for 2 eggs
dunno for 3 eggs also coz i не решил еще тоже

Jane Soboleva (SumNU) Re: what is the so-called initial step for 2 eggs / 20 floors? [2] // Problem 1223. Chernobyl’ Eagle on a Roof 16 Mar 2016 23:38

Well, intuitively, with 3 eggs we should put the first one in the middle, to minimize a floor quantity in worst case for remaining two eggs?

esbybb Re: what is the so-called initial step for 2 eggs / 20 floors? [1] // Problem 1223. Chernobyl’ Eagle on a Roof 17 Mar 2016 18:32

intuitively this is DP problem with precomputing table of 1001x1001 cells
row 1 contain values -1 1 2 3 4 5 ..
row 2 contain values -1 1 2 2 3 3 ..
row 3 ??

with 3 eggs we do move0 somewhere in the middle, doing loop from Eggs to 1, computing
min(row1[step1]+row2[step22]) (or minimize step1+step2, maybe) for 3 eggs:

for (step2=e; step2>1; step2--)
for (step1=i2; step1>1; step1--)

esbybb Re: what is the so-called initial step for 2 eggs / 20 floors? // Problem 1223. Chernobyl’ Eagle on a Roof 18 Mar 2016 03:06

row 2 : -1 1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 7 8 ..

Discussion of Problem 1223. Chernobyl’ Eagle on a Roof