| Show all threads Hide all threads Show all messages Hide all messages |
| Mistake in English statement? | mouse_wireless2 | 1117. Hierarchy | 6 Aug 2018 11:30 | 2 |
The statement says
"The number of intermediate levels of employees between an arbitrary employee who has subordinates (an ordinary employee) and the employee who has no superiors (the main superior) is the same for all ordinary employees."
However, in the first paragraph, it says that "ordinary employee" means an employee who has NO subordinates. Therefore, I think the statement should say:
"The number of intermediate levels of employees between an arbitrary employee who has NO subordinates (an ordinary employee) and the employee who has no superiors (the main superior) is the same for all ordinary employees."
I looked at the Russian version of the statement with google translate and that seems to be the case. There is also no mention in the statement that the structure is that of a SINGLE tree (and not a forest), but the answer seems to assume this.
The statement only says that each employee has "not more than one direct superior", therefore one can understand that it is possible, for example, that no employee has a direct superior (and therefore the structure is a forest of single-node trees). |
| Error in problem statement | Otrebus | 1117. Hierarchy | 12 Apr 2015 19:09 | 1 |
"There is no subordinate of ordinary employees"
vs
"an arbitrary employee who has subordinates (an ordinary employee)" |
| AC program DP idea | lakerka | 1117. Hierarchy | 4 Jun 2014 18:03 | 1 |
Main idea:
Number tree levels from bottom to top like: 0th, 1st, 2nd ...
We can traverse the whole tree, but it would take at most 2^31 vertexes to visit. I call [traversing the whole tree]: going from bottom left vertex to bottom right vertex of the tree. So we can observe that we can skip traversing some part of the tree. Since traversing tree A of level AL is the same as traversing two smaller trees with levels (AL-1) + 2*(cost to go from bottom to top (highest) vertex of tree A). Example:
+-----+4+----+
+ +
++2++ ++6++
+ + + +
1 3 5 7
To traverse tree A (from 1 to 7) with level 2 is the same as traversing tree B (from 1 - 3) with level 1 twice and adding costs: from 3 to 4, from 4 to 5.
Let's call m[level of tree] = min cost to traverse tree with such level from bottom left to bottom right of tree. Then we could find out what is traversal cost for each tree with arbitrary level like:
for 1..MAX_LEVEL_OF_TREE:
m[i] = 2 * m[i - 1] + 2 * (i - 1);
We traverse tree from left to right. We shall call destination vertex d, current vertex c and level of tree where we can find c: cl. Initially c is vertex we start from.
We know that if we are standing at c, vertex number that is one level above c is: upRight = c + 2^cl. So if d >= upRight we have to go to upRight vertex, because here: [c ; upRight-1] is no destination vertex.
Similarly we know that if we are standing at c, vertex number that is at 0th level to the right of c is: downRight = c + 1. We should go to downRight if: d < upRight.
So finally:
cost(v) - cost by going directly from bottom vertex to v. Example: cost(8) = 2, cost(16) = 3.
We go up right if d >= upRight :
[whole cost] = [whole cost] + m[cl - 1] + cost(c) + cost(upRight)
c = c + 2^cl
We go down right if if d < upRight:
[whole cost] = [whole cost] + cost(c)
c = c + 1
Complexity similar to log(n)^2 |
| Dymanic Programing. | Y.Y.M. | 1117. Hierarchy | 4 May 2013 19:11 | 7 |
Time Limit Exceeded Test#12
what do? I think we only remember 1 to 2^i this mean G(1,i) then
F(1,N]=F(1,2^i)+i-1+F(2^i+1,N) ==>
F(1,N)=G(1,i)+i-1+F(2^i+1,N) while the last F(2^i+1,N)=F(1,N-2^i-1) and so on
certainly f(1,1)=0;
Edited by author 04.05.2013 19:28 I just use something like low_bit and calc the answer easily in logN time. You may use Abs(Dis(1,A) - Dis(1,B)) it is a good way to solve this problem.
Sorry for my poor English.
Edited by author 14.11.2005 21:19 15 strings - And AC - Cool!!! - time 0.015 |
| I got AC , but who can tell me how to use DP there (I solved this problem without DP , using log2 ) | nobik | 1117. Hierarchy | 21 Jun 2012 17:18 | 1 |
I got AC , but who can tell me how to use DP there (I solved this problem without DP , using log2 ) |
| what is the answer for 1 15 ? | MadPsyentist/Sam | 1117. Hierarchy | 28 Sep 2009 21:48 | 6 |
agree blue dog 15 Feb 2002 08:08
Edited by author 28.09.2009 21:55 |
| Invalid test 9 | Fyodor Menshikov | 1117. Hierarchy | 29 Oct 2008 10:28 | 2 |
In test 9 numbers in input are equal. But they should not be equal, because there is no reason to deliver message from an employee to herself. And anyway the problem statement does not define how much time it will get to deliver message from i to i. |
| Hint ++ with tests! | Tolstobrov_Anatoliy[Ivanovo SPU] | 1117. Hierarchy | 9 Jan 2008 19:03 | 3 |
Use this and you got AC!
Answer(n,m)=abs( Answer(1,n)-Answer(1,m) )
check this(130 tests) and YOU got AC (I think)
(N M Answer)
1 1 0
1 2 0
1 3 0
1 4 1
1 5 2
1 6 2
1 7 2
1 8 4
1 9 6
1 10 6
1 11 6
1 12 7
1 13 8
1 14 8
1 15 8
1 16 11
1 17 14
1 18 14
1 19 14
1 20 15
1 21 16
1 22 16
1 23 16
1 24 18
1 25 20
1 26 20
1 27 20
1 28 21
1 29 22
1 30 22
1 31 22
1 32 26
1 33 30
1 34 30
1 35 30
1 36 31
1 37 32
1 38 32
1 39 32
1 40 34
1 41 36
1 42 36
1 43 36
1 44 37
1 45 38
1 46 38
1 47 38
1 48 41
1 49 44
1 50 44
1 51 44
1 52 45
1 53 46
1 54 46
1 55 46
1 56 48
1 57 50
1 58 50
1 59 50
1 60 51
1 61 52
1 62 52
1 63 52
1 64 57
1 65 62
1 66 62
1 67 62
1 68 63
1 69 64
1 70 64
1 71 64
1 72 66
1 73 68
1 74 68
1 75 68
1 76 69
1 77 70
1 78 70
1 79 70
1 80 73
1 81 76
1 82 76
1 83 76
1 84 77
1 85 78
1 86 78
1 87 78
1 88 80
1 89 82
1 90 82
1 91 82
1 92 83
1 93 84
1 94 84
1 95 84
1 96 88
1 97 92
1 98 92
1 99 92
1 100 93
1 101 94
1 102 94
1 103 94
1 104 96
1 105 98
1 106 98
1 107 98
1 108 99
1 109 100
1 110 100
1 111 100
1 112 103
1 113 106
1 114 106
1 115 106
1 116 107
1 117 108
1 118 108
1 119 108
1 120 110
1 121 112
1 122 112
1 123 112
1 124 113
1 125 114
1 126 114
1 127 114
1 128 120
1 129 126
1 130 126 Use this and you got AC! I think big test is also useful: 1 2147483647 2147483586 Also usefull tests:
WA 8:
4 12 (answer = 6)
WA 18:
7 9 (answer = 4) |
| pls pls pls pls pls help... how to store so many numbers | manishmmulani | 1117. Hierarchy | 3 Jan 2008 18:51 | 3 |
for the range 1 to 2^31-1 even O(n) soln won't work
i.e even a single loop will take more time
if we want to use f(n,m) = abs(f(1,n)-f(1,m))
we need to store 2^31 values... how is it possible to store so many numbers!!!!
You don't need to store so many numbers. Tey to find another way (try to see how change length between fixed nodes). f(n,m) = abs(f(1,n) - f(1,m)) - it's ok. |
| Would someone tell me what is the answer for : 1 2^31-1. | Rostislav | 1117. Hierarchy | 22 Feb 2007 18:58 | 4 |
It's not 2346241344.
Edited by author 27.04.2004 19:09 |
| Could anyone explain me why the answer for test 1 8 is 4? | Dima | 1117. Hierarchy | 8 Aug 2006 21:09 | 3 |
1 gives to 2 - 0
2 gives to 3 - 0
3 gives to 4 - 1
4 gives to 5 - 1
5 gives to 6 - 0
6 gives to 7 - 0
7 gives to 8 - 2 My awfull mistake!!!
Forgot, that
the message delivery takes an amount of days that is equal to the number of intermediate employees between the sender and recipient.
Thank you. |
| some more test pls....I got WA on test #16 | yuri | 1117. Hierarchy | 6 Aug 2005 17:10 | 3 |
there is some test (100):
N M Answer
707719609 435056164 272663445
99221521 210395025 111173494
687488400 209062681 478425711
732189481 223203600 508985881
220760164 235714609 14954443
875627281 54612100 821015179
400040001 630763225 230723214
682724641 899640036 216915381
15968016 262569616 246601592
363093025 236196 362856825
710862244 193154404 517707834
6697744 54081316 47383566
779191396 222875041 556316353
844193025 614444944 229748093
36566209 280529001 243962796
82846404 1331716 81514680
1030024836 183385764 846639072
992016 1014049 22031
57562569 396686889 339124318
248409121 542936601 294527484
990864484 759774096 231090388
129777664 129322384 455280
485144676 24482704 460661968
15673681 458302464 442628781
6084 652444849 652438753
5031049 3025 5028020
556346569 811794064 255447487
24870169 38464804 13594641
274498624 2859481 271639145
173132964 265592209 92459239
36096064 85636516 49540446
316626436 617796 316008630
110923024 317053636 206130606
930616036 296976289 633639749
154405476 72165025 82240451
6375625 69006249 62630614
720385600 319229689 401155911
113529025 282710596 169181565
787083025 444450724 342632301
236083225 951599104 715515871
632271025 26173456 606097559
137757169 566154436 428397257
933302500 943472656 10170162
673350601 71048041 602302564
806404 604569744 603763340
63888049 955489921 891601872
2152089 2805625 653528
51222649 33860761 17361882
3717184 276290884 272573690
85710564 506610064 420899506
892097424 13512976 878584440
5621641 604028929 598407302
60902416 6400 60896008
720868801 331776 720537009
275360836 123565456 151795390
40653376 907274641 866621259
1051315776 798684121 252631659
286421776 854743696 568321912
768564729 1025344441 256779720
413552896 899820009 486267109
569204164 249008400 320195760
942060249 7507600 934552643
372991969 93837969 279153996
349914436 45495025 304419411
407313124 688642564 281329442
207763396 471932176 264168784
217356049 452157696 234801643
609349225 71824 609277385
18224361 24216241 5991880
165148201 2160900 162987285
189585361 386201104 196615747
1028805625 144504441 884301180
212255761 24940036 187315727
507240484 379509361 127731127
702780100 11648569 691131529
8473921 673039249 664565318
415099876 511664400 96564528
362140900 683561025 321420133
8916196 620259025 611342817
41049649 226472401 185422742
412658596 940096921 527438325
750376449 1061000329 310623874
347636025 14814801 332821220
59136100 1022784361 963648247
13242321 209207296 195964971
36180225 482022025 445841784
771783961 2873025 768910934
741309529 533794816 207514711
13344409 93644329 80299922
9235521 108764041 99528508
16096144 42471289 26375151
242518329 460059601 217541262
194463025 122279364 72183663
785400625 787868761 2468124
82283041 221265625 138982578
260100 926410969 926150849
872434369 207072100 665362283
1035294976 400440121 634854857
681157801 303073281 378084506
226352025 591656976 365304961
Edited by author 27.07.2004 13:35
Edited by author 27.07.2004 13:35 STRANGE!! Tolstobrov_Anatoliy[Ivanovo SPU] 6 Aug 2005 17:10
My wrong program chech all this tests and got WA3
When i fixe BUG i got AC and my AC program too check all this tests!! |
| can any one tell me the meaning of this problem? | liuzhizhi | 1117. Hierarchy | 22 Jul 2004 15:22 | 1 |
|
| Why is the prob statement so tortuous? Just saying the hierachy is a 'full sorted binary tree with continuous integer labels starting with 1' is enough, so why waste as many as two paragraphs? | Maigo Akisame (maigoakisame@yahoo.com.cn) | 1117. Hierarchy | 15 Jul 2004 13:44 | 1 |
|
| At the first glance,this problem is hard to understand what it says and seem to be difficult.After thinking for a while,you'll find it can be done in a very easy way.(Email:hyz12345678@163.com) | Huang Yizheng | 1117. Hierarchy | 3 Jun 2004 19:32 | 2 |
i get wa for abouta month...
please can you send your ac to macarie@k.ro ?
thankx |
| How to slove it?? Any hints? | tbtbtb91 | 1117. Hierarchy | 23 Apr 2004 11:10 | 2 |
|
| Who can explain me this problem?(-) | Algorist | 1117. Hierarchy | 10 Aug 2002 16:04 | 5 |
hmm (+) MadPsyentist/Sam 12 Mar 2002 08:29 the structure of employees is in the form of binary search tree and you
have to find the cost of transfering message from one employee to the
other employee
is this enough? I got that :)) But I could not understand how the costs are formed. I
mean, how 1 15 is 8 (that is posted on the webboard) and such
stuff.... what are the prices of transferring one message from one
employee to another? That's what I couldn't get first of all , draw the binary search tree of 1-15 in your paper and look
at it along with the explaination
1 to 2 : 0 : they are direct subordinate and superior
2 to 3 : 0 : direct superior and subordinate
3 to 4 : 1 : 3 have to send to 2 to have 4 get the message
4 to 5 : 1 : have to pass 6
5 to 6 : 0 : again, direct
6 to 7 : 0
and this is a important part to make you really understand: 7 to 8 : 2 :
have to pass to 6 and then 4 to have 8 have the message
you sould understand now if my english is not too bad
anyway
8 to 9 : 2
9 to 10 : 0
10 to 11 : 0
11 to 12 : 1
12 to 13 : 1
13 to 14 : 0
14 to 15 : 0
and total is 8 |
