| ENG RUS | Timus Online Judge |
Обсуждение задачи 1117. Иерархияcoolboy19521 I solved it without dp. // Задача 1117. Иерархия 5 июл 2024 02:05 The solution is actually really easy when not dp. It is just the count of numbers that are divisible by (1ll<<i) and only by (1ll<<i) times 2(i-1). If you just draw 1-15 tree and try to solve for 1 15 you'll observe it. You just have to make these checks (i'm too lazy to explain it, but if you want just comment): for (int i = 30; i >= 1; i--) { int powerOf2 = 1ll << i; int ci = countMultiples(n, m, powerOf2); ci -= al; int r = m / powerOf2; int l = n / powerOf2; an += 2 * (i - 1) * ci; if (m % powerOf2 == 0 && (r % 2 != 0 || r == 0) && ci > 0) {// <-- These are the checks an -= (i - 1); } if (n % powerOf2 == 0 && (l % 2 != 0 || l == 0) && ci > 0) { an -= (i - 1); } al += ci; } mouse_wireless2 Mistake in English statement? [1] // Задача 1117. Иерархия 6 авг 2018 11:24 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. mouse_wireless2 Re: Mistake in English statement? // Задача 1117. Иерархия 6 авг 2018 11:30 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). Otrebus Error in problem statement // Задача 1117. Иерархия 12 апр 2015 19:09 "There is no subordinate of ordinary employees" vs "an arbitrary employee who has subordinates (an ordinary employee)" lakerka AC program DP idea // Задача 1117. Иерархия 4 июн 2014 18:03 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 Y.Y.M. Dymanic Programing. [6] // Задача 1117. Иерархия 22 июн 2004 18:49 paulo Re: Dymanic Programing. [3] // Задача 1117. Иерархия 5 июл 2004 16:31 Time Limit Exceeded Test#12 what do? Yu YuanMing make a table to remember something...althought you can't remember all....but that is enough [2] // Задача 1117. Иерархия 6 июл 2004 14:24 ahmasoi Re: make a table to remember something...althought you can't remember all....but that is enough [1] // Задача 1117. Иерархия 27 июл 2004 13:43 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; Snayde Re: make a table to remember something...althought you can't remember all....but that is enough // Задача 1117. Иерархия 4 май 2013 19:11 Edited by author 04.05.2013 19:28 Chidori Re: Dymanic Programing. [1] // Задача 1117. Иерархия 14 ноя 2005 21:18 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 Piratek-(akaDK) Re: Dymanic Programing. // Задача 1117. Иерархия 30 июл 2008 23:44 15 strings - And AC - Cool!!! - time 0.015 nobik I got AC , but who can tell me how to use DP there (I solved this problem without DP , using log2 ) // Задача 1117. Иерархия 21 июн 2012 17:18 I got AC , but who can tell me how to use DP there (I solved this problem without DP , using log2 ) MadPsyentist/Sam what is the answer for 1 15 ? [5] // Задача 1117. Иерархия 2 фев 2002 01:43 Carlos Cardonha Re: what is the answer for 1 15 ? [4] // Задача 1117. Иерархия 12 фев 2002 08:29 > The answer is 8. blue dog agree [3] // Задача 1117. Иерархия 15 фев 2002 08:08 > MadPsyentist/Sam Thank you ^^ At first , I didn't understand the problem at all. Now I got AC. [1] // Задача 1117. Иерархия 17 фев 2002 18:10 > > > Fyodor Menshikov I didn't understand the problem twice. :-) // Задача 1117. Иерархия 22 фев 2007 18:57 eXeLLenT No subject // Задача 1117. Иерархия 28 сен 2009 21:48 Edited by author 28.09.2009 21:55 Fyodor Menshikov Invalid test 9 [1] // Задача 1117. Иерархия 22 фев 2007 19:11 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. Yitao Re: Invalid test 9 // Задача 1117. Иерархия 29 окт 2008 10:28 It's ZERO. Tolstobrov_Anatoliy[Ivanovo SPU] Hint ++ with tests! [2] // Задача 1117. Иерархия 6 авг 2005 17:15 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 Fyodor Menshikov Re: Hint ++ with tests! [1] // Задача 1117. Иерархия 22 фев 2007 19:02 Tolstobrov_Anatoliy[Ivanovo SPU] писал(a) 6 августа 2005 17:15 Use this and you got AC! I think big test is also useful: 1 2147483647 2147483586 elmariachi1414 (TNU) Re: Hint ++ with tests! // Задача 1117. Иерархия 9 янв 2008 19:03 Also usefull tests: WA 8: 4 12 (answer = 6) WA 18: 7 9 (answer = 4) manishmmulani pls pls pls pls pls help... how to store so many numbers [2] // Задача 1117. Иерархия 29 дек 2007 20:10 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!!!! Chmel_Tolstiy Re: pls pls pls pls pls help... how to store so many numbers [1] // Задача 1117. Иерархия 30 дек 2007 15:16 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. manishmmulani Re: pls pls pls pls pls help... how to store so many numbers // Задача 1117. Иерархия 3 янв 2008 18:51 ok thanx .. will try it Rostislav Would someone tell me what is the answer for : 1 2^31-1. [3] // Задача 1117. Иерархия 7 май 2002 15:07 Thank you! Rostislav Everything is OK don't reply! 10x anyway! [2] // Задача 1117. Иерархия 7 май 2002 15:30 > Thank you! 黄源河 Re: Everything is OK don't reply! 10x anyway! [1] // Задача 1117. Иерархия 27 апр 2004 19:07 It's not 2346241344. Edited by author 27.04.2004 19:09 Fyodor Menshikov 2147483586 // Задача 1117. Иерархия 22 фев 2007 18:58 Dima Could anyone explain me why the answer for test 1 8 is 4? [2] // Задача 1117. Иерархия 8 авг 2006 15:14 I think it must be three. 1 gives to 2 - 0 2 gives to 3 - 0 3 gives to 4 - 1 4 gives to 5 - 2 5 gives to 6 - 2 6 gives to 7 - 2 7 gives to 8 - 3 I cant understand how it can be 4. Even Tolstobrov_Anatoliy[Ivanovo SPU] gave some tests (http://acm.timus.ru/forum/thread.aspx?space=1&num=1117&id=11659&upd=632589453091063750) and there are such tests: 1 7 2 1 8 4 So I'm right up to the 7'th employee. Then we add 1. Thank. Burunduk1 Re: Could anyone explain me why the answer for test 1 8 is 4? // Задача 1117. Иерархия 8 авг 2006 17:30 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 Dima Re: Could anyone explain me why the answer for test 1 8 is 4? // Задача 1117. Иерархия 8 авг 2006 21:09 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. yuri some more test pls....I got WA on test #16 [2] // Задача 1117. Иерархия 3 июн 2004 16:33 ahmasoi Re: some more test pls....I got WA on test #16 [1] // Задача 1117. Иерархия 27 июл 2004 13:32 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 Tolstobrov_Anatoliy[Ivanovo SPU] STRANGE!! // Задача 1117. Иерархия 6 авг 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!! liuzhizhi can any one tell me the meaning of this problem? // Задача 1117. Иерархия 22 июл 2004 15:22 Maigo Akisame (maigoakisame@yahoo.com.cn) 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? // Задача 1117. Иерархия 15 июл 2004 13:44 Huang Yizheng 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) [1] // Задача 1117. Иерархия 29 дек 2001 05:06 sloboz Re: 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) // Задача 1117. Иерархия 3 июн 2004 19:32 i get wa for abouta month... please can you send your ac to macarie@k.ro ? thankx tbtbtb91 How to slove it?? Any hints? [1] // Задача 1117. Иерархия 10 апр 2004 10:54 tbtbtb AC now! // Задача 1117. Иерархия 23 апр 2004 11:10 Algorist Who can explain me this problem?(-) [4] // Задача 1117. Иерархия 9 мар 2002 01:40 MadPsyentist/Sam hmm (+) [3] // Задача 1117. Иерархия 12 мар 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? Algorist Re: hmm (+) [2] // Задача 1117. Иерархия 12 мар 2002 14:50 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 MadPsyentist/Sam yeah, I shall explain with this case (+) [1] // Задача 1117. Иерархия 12 мар 2002 16:14 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 Koala Thanks for your patient exposition!!! Now I can understand it. // Задача 1117. Иерархия 10 авг 2002 16:04
|