1

Topic: Re: problems from the headhunter

Hello, Kodt, you wrote: On  article with as it was clarified, unsuccessful decisions of problems https://habrahabr.ru/post/311908/I Suggest to knead a head independently. So the Task 1 equality in which digits are replaced with letters Is given: rqr + rqq = sqr. Find how many at it decisions if to various letters there correspond various digits (leading zero in number does not happen). With running start dared . In the image: q = 0, s = 2r it is possible . Remaining I will look then.

2

Re: Re: problems from the headhunter

> The task 1>> equality in which digits are replaced with letters Is given: rqr + rqq = sqr. Find how many at it decisions if to various letters there correspond various digits (leading zero in number does not happen). S> With running start dared . In the image: S> q = 0, s = 2r S> it is possible . Remaining I will look then. I will specify: rqr + rqq = sqr => q = 0 it is substituted q = 0: r0r + r00 = s0r => s = 2*r => r = 1. 4 4 decisions 101 + 100 = 201 202 + 200 = 402 303 + 300 = 603 404 + 400 = 804

3

Re: Re: problems from the headhunter

Hello, Kodt, you wrote: On  article with as it was clarified, unsuccessful decisions of problems https://habrahabr.ru/post/311908/OMG. They there decided to consider factorials in a forehead.

4

Re: Re: problems from the headhunter

5

Re: Re: problems from the headhunter

Hello, Lexey, you wrote: L> In msec release 137. Also it is possible  still. It is necessary! - business good, but it () , one logarithm it is possible to remove Binary search if to take lower bound for specific p equal count * (p - 1) + 1 (from the geometrical progression total), approximated upwards to sharing on p, and then to go upwards short steps on p, not  anew a factorial level, and counting an amount p in the next multiplier (on the average it will be no more than one check), and short steps such already there will be a logarithmic number. And it is possible to be played by order of prime factors, modern automatic odds is it is cool but if to go reversely, and there is enough big prime factor probably it suffices for remained small (in your example - will depart at once on continue), as a whole it can appear favourable. Well and factorization of each number is a tin, for such small numbers the sieve on 2.4  in which to each number one of its prime factors is compared is stupidly made, here probably there will be the thickest scoring. Well or at least it is standard to sort out to a root possible simple dividers, instead of to the number. In general all is sad with it , at them even close anything is not present to the reasonable decision.

6

Re: Re: problems from the headhunter

Hello, cures, you wrote: L>> In msec release 137. Also it is possible  still. A C> It is necessary! Not the fact. And so is very bright works.> Binary search - business good, but it () , one logarithm it is possible to remove a C if to take lower bound for specific p equal count * (p - 1) + 1 (from the geometrical progression total), approximated upwards to sharing on p, and then to go upwards short steps on p, not  anew a factorial level, and counting an amount p in the next multiplier (on the average it will be no more than one check), and short steps such already there will be a logarithmic number. Here it agree. A C> And order of prime factors it is possible to be played, modern automatic odds is it is cool but if to go reversely, and there is enough big prime factor probably it suffices for remained small (in your example - will depart at once on continue), as a whole it can appear favourable. Of it thought, but did not become . The C> Well and factorization of each number is a tin, for such small numbers the sieve on 2.4  in which to each number one of its prime factors is compared is stupidly made, here probably there will be the thickest scoring. Idea good. But, not in essence, for factorization all the same will be linear (only the constant decreases), and with implementation it is more than trouble. A C> Well or at least it is standard to sort out to a root possible simple dividers, instead of to the number. Get over simple to a root from N. A root from specific number in the given task it will be not strong less. A C> in general all is sad with it , at them even close anything is not present to the reasonable decision. It yes.

7

Re: Re: problems from the headhunter

Hello, Lexey, you wrote: L> Not the fact. And so is very bright works. Here is hardly more bright, though I only made  to a root in factorization. Well also rearranged sampling of time to the first output for to measure output time - overindulgence. If that, it is possible in the same place and to be measured, we - professionals of a C>> Well and factorization of each number is a tin, for such small numbers the sieve on 2.4  in which to each number one of its prime factors is compared is stupidly made, here probably there will be the thickest scoring. L> idea good. But, not in essence, for factorization all the same will be linear (only the constant decreases), and with implementation it is more than trouble. Factorization will be (almost linear on the maximum number, and at independent factorization she demands about an amount of numbers in a range, multiplied by a root from  number, that is at worst -  number in a level 1.5. L> get over simple to a root from N. Root from specific number in the given task it will be not strong less. No, get over to most N. Here if you replaced if (p> n) break; on if (p> n / p) break; that would get over to a root. Update: understood, get over to a root from the maximum number, but there will be often enough small factors that reduces search. Can try.

8

Re: Re: problems from the headhunter

Hello, Kodt, you wrote: there there will be something of type p * (any row from int (count/p ** k)) It equally count * (p - 1), plus absolutely slightly that for logarithmic number of steps steals up. By the way, if to alloy expansion and boundary finding it is possible to get rid of a vector. And sense? A vector of simple dividers small, the compiler most likely  its reassignments. But now there is no sense even to remove a logarithm, all time (35ms) leaves on factorization, try to interpose return factors.size (); in most began functions s after calculation of factors. At first it is necessary to do a sieve. Update1: here  with a sieve and steps, lifted both limits in 10 times, I offer on them and to be measured, on old too , and it is more  hardly than storage gives. Update2: made a sieve the two-byte, ceased to consider once again factorial_power; hardly time, till 0.31 seconds decreased. Measured number of jumps on steps ( under the formula), 17355 on one million, it at all a logarithm, and very good constant.

9

Re: Re: problems from the headhunter

10

Re: Re: problems from the headhunter

Hello, Lexey, you wrote: L> Here it turned out 16640. The decision not so is pleasant to me of that all the same it was necessary to a level in set to push in a double cycle. But anything the best it was not invented yet. Looks a little horribly. And why not to get  with  on a set , after expansion of each base a we find its basic base A (dividing all indexes of levels of simple factors into them ), and we add in set for A all indexes which get out from a, from g*bmin to g*bmax. Then simply we add capacities of all sets. Probably sets even , segments, but with sets more the common decision suffices. Yes, for a  than a root from amax, such that A (a) =a, it is possible not to get a set, it as basic more never floats, it is possible to add at once (bmax-bmin+1) to the answer. Total the basic bases in  there will be 7 pieces: [2,3,5,6,7,10,11]. To a heap it is possible  not to get, sort out at all the possible basic bases from 1 to sqrt (amax), to mark levels turning out from them and on the move  an appropriate range so we manage absolutely without factorization, but it is necessary bit arrays of the size (amax-amin+1) and sqrt (amax), and the operating time will be proportional to the total of their sizes that like not is worse the offered. It is possible to try for solve (3,3000000000,4,4000000000).

11

Re: Re: problems from the headhunter

The Task 1 equality in which digits are replaced with letters Is given: rqr + rqq = sqr. Find how many at it decisions if to various letters there correspond various digits (leading zero in number does not happen). Confuses that nobody asked specifications about numeration system.

12

Re: Re: problems from the headhunter

Hello, AlexeySmorkalov, you wrote:> the Task 1>> equality in which digits are replaced with letters Is given: rqr + rqq = sqr. Find how many at it decisions if to various letters there correspond various digits (leading zero in number does not happen). AS> Confuses that nobody asked specifications about numeration system. Validly, but personally I in this task went the shortest a way. Besides if it is not stipulated another it is possible to use "default", i.e. decimal . Notations.

13

Re: Re: problems from the headhunter

Hello, cures, you wrote: the C> Looks a little horribly. Yes, there is a such. A C> And why not to get  with  on a set , after expansion of each base a we find its basic base A (dividing all indexes of levels of simple factors into them ), and we add in set for A all indexes which get out from a, from g*bmin to g*bmax. Then simply we add capacities of all sets. Probably sets even , segments, but with sets more the common decision suffices. Upon, and it was necessary to do, but I at first tried to count easier counterparts and them to throw out from total number, but broke off. As a result simply minimum altered, that worked. Entirely all to alter it was simple laziness, and it would be desirable to sleep already. A C> Yes, for a  than a root from amax, such that A (a) =a, it is possible not to get a set, it as basic more never floats, it is possible to add at once (bmax-bmin+1) to the answer. Total the basic bases in  there will be 7 pieces: [2,3,5,6,7,10,11]. It agree. The C> to a heap can  to be got, sorted out at all the possible basic bases from 1 to sqrt (amax), to mark levels turning out from them and on the move  an appropriate range so we manage absolutely without factorization, but it is necessary bit arrays of the size (amax-amin+1) and sqrt (amax), and the operating time will be proportional to the total of their sizes that like not is worse the offered. It is possible to try for solve (3,3000000000,4,4000000000). Here this idea did not understand.

14

Re: Re: problems from the headhunter

The Task 1 equality in which digits are replaced with letters Is given: rqr + rqq = sqr. Find how many at it decisions if to various letters there correspond various digits (leading zero in number does not happen). One cycle from 1 to 4.

15

Re: Re: problems from the headhunter

Hello, Lexey, you wrote: the C>> to a heap can  to be got, sorted out at all the possible basic bases from 1 to sqrt (amax), to mark levels turning out from them and on the move  an appropriate range so we manage absolutely without factorization, but it is necessary bit arrays of the size (amax-amin+1) and sqrt (amax), and the operating time will be proportional to the total of their sizes that like not is worse the offered. It is possible to try for solve (3,3000000000,4,4000000000). L> Here this idea did not understand. We sort out the basic bases (not being levels of smaller numbers) to sqrt (amax). For example, 2 enters into a segment [amin. amax] in levels [2. 7]. , from the list of the basic bases it is eliminated 4 and 8 (16 already more sqrt (134), and 2 it it is even less 3) then for each of levels of a twain from the second to the seventh it is found, how many total numbers she adds in result. For example, 4 adds (bmax-bmin+1) =133 new numbers, 8 already adds less, it is necessary to subtract from its levels what we already added in quadruple, 16 adds even less, and so on to 128. It is necessary to consider an amount of added numbers probably under the switching-on-exception formula (intersection of two arithmetical sequences like too the arithmetical sequence), therefore to time complexity will be added amax. But such basic bases for which there will be many various levels, will be a little. Separately we consider an amount of numbers from a segment [amin. amax] which turned out from our levels (are already counted); after run on the basic bases we add to total result an amount of not counted bases increased on (bmax-bmin+1). Storage is necessary to mark not basic bases, bit map of the size sqrt (amax), well and a stack of the size log (amax) for the recursive calculation under the switching-on-exception formula.

16

Re: Re: problems from the headhunter

Hello, cures, you wrote: the C> Is sorted out the basic bases (not being levels of smaller numbers) to sqrt (amax). For example, 2 enters into a segment [amin. amax] in levels [2. 7]. , from the list of the basic bases it is eliminated 4 and 8 (16 already more sqrt (134), and 2 it it is even less 3) then for each of levels of a twain from the second to the seventh it is found, how many total numbers she adds in result. For example, 4 adds (bmax-bmin+1) =133 new numbers, 8 already adds less, it is necessary to subtract from its levels what we already added in quadruple, 16 adds even less, and so on to 128. It is necessary to consider an amount of added numbers probably under the switching-on-exception formula (intersection of two arithmetical sequences like too the arithmetical sequence), therefore to time complexity will be added amax. But such basic bases for which there will be many various levels, will be a little. Separately we consider an amount of numbers from a segment [amin. amax] which turned out from our levels (are already counted); after run on the basic bases it is added to total result an amount of not counted bases increased on (bmax-bmin+1). Storage is necessary to mark not basic bases, bit map of the size sqrt (amax), well and a stack of the size log (amax) for the recursive calculation under the switching-on-exception formula. So it is clear, like. Here with the formula of switching-on-exceptions I just also did not want . For to implement it strongly is drearier, than to store levels in which the basic base is raised, in set, and then to take its total capacity.

17

Re: Re: problems from the headhunter

Hello, Lexey, you wrote: L> So it is clear, like. Here with the formula of switching-on-exceptions I just also did not want . For to implement it strongly is drearier, than to store levels in which the basic base is raised, in set, and then to take its total capacity. It is apparent simplicity, a set  it is implemented through red-black trees if it was necessary to implement it hands - it would be easier to be shot. I somehow only needed to add to a set the rank statistics: an amount of elements in a set, smaller given that for a capacity logarithm was considered. So it appeared to give birth to the AVL-TREE though on him and there is no anywhere a documentation is much easier, but in 4 there was a sketch  insertions. Well and a set on billions elements it is cheerful enough, then is easier than it through bit map to make.

18

Re: Re: problems from the headhunter

Hello, LaptevVV, you wrote: LVV> One cycle from 1 to 4. The Cycle what for?

19

Re: Re: problems from the headhunter

20

Re: Re: problems from the headhunter

Hello, StatujaLeha, you wrote: SL> And such how many? SL> 3.1641809940338135 27566064194 Such on  under the second python occupied 0.95 seconds. The main time is expected cunningly on a sieve. By the way, primesBelow it would be necessary to call from N+1, suddenly someone substitutes simple upper bound. The formula for upper bound minFactorial (p, e) very strange, p ** sqrt (2*e) it nevertheless is normal much more, than p*e, there were 180628 misses instead of 114, well and a root with a level one million times to consider too . The formula for start lower bound a little bit , is better start = pe + (M - 1) - (M - 1) than % pe. M it is better to subtract from upper and range lower bound, instead of in each iteration, the Python - an interpretive language, such is not able to optimize. After optimization it is laid down in 0.4 seconds if to increase both boundaries in 10 times - in 4.2 seconds. It is possible to accelerate a little bit still if in sieve not to capture storage under even numbers (operation with them I already threw out). The main hindrance to the further acceleration - asymptotics O (N) both on time, and on storage. It would be possible prime numbers  only to sqrt (N), then them to count possible minima on [M, N], in passing dividing each number from this segment on sorted out simple then to count for the remained simple dividers, receiving complexities approximately sqrt (N) + (N - M). However thus it is necessary to divide, and it is more expensive, than to multiply, the profit will be only on big N.

21

Re: Re: problems from the headhunter

Hello, cures, you wrote: the C> Is apparent simplicity, a set  is implemented through red-black trees if it was necessary to implement it hands - it would be easier to be shot. It not apparent, but quite real. Expressed in complexity of the code and expenses of time for its implementation. unordered_set it is implemented through the hash table. In such tasks nobody implies manual implementation of standard data structures. They are in any more or less decent . The C> To me somehow only was required to add the rank statistics to a set: an amount of elements in a set, smaller given that for a capacity logarithm was considered. So it appeared to give birth to the AVL-TREE though on him and there is no anywhere a documentation is much easier, but in 4 there was a sketch  insertions. Is LLRB-tree which is implemented strongly easier, than normal RB-tree. A C> Well and a set on billions elements it is cheerful enough, then is easier than it through bit map to make. Whence billions elements there undertake? For the given dimensionality of the task there even at worst () it turns out levels of twains less than 7 * 136 elements. These are copecks.

22

Re: Re: problems from the headhunter

Hello, cures, you wrote: SL>> 3.1641809940338135 27566064194 Cs> Such on  under the second python occupied 0.95 seconds. The main time is expected cunningly on a sieve. Apprx. too the sieve occupies From me somewhere half (1.67 of 3.16 ).> By the way, primesBelow it would be necessary to call a C from N+1, suddenly someone substitutes simple upper bound. + a C> the Formula for upper bound minFactorial (p, e) very strange, p ** sqrt (2*e) it nevertheless is normal much more, than p*e, Yes, it not simply strange, but the incorrect Idea was such: if at us it is set m to count a level e from which idle time p enters in m!, we should use the known formula. This formula such that has races in points, multiple p. Therefore we search minimum q such that (p ** q)! % (p ** e) == 0, and we go downwards steps in the size p further. Replaced the formula on qMin = int (ceil (log (e * (p - 1) + 1, p))), became faster: http://ideone.com/22C4V6 But the variant with x = p*e is all the same better: http://ideone.com/vmy6tN 0.16 against 0.12 seconds of a C> It is possible to accelerate a little bit still if in sieve not to capture storage under even numbers (operation with them I already threw out). The main hindrance to the further acceleration - asymptotics O (N) both on time, and on storage. It would be possible prime numbers  only to sqrt (N), then them to count possible minima on [M, N], in passing dividing each number from this segment on sorted out simple then to count for the remained simple dividers, receiving complexities approximately sqrt (N) + (N - M). However thus it is necessary to divide, and it is more expensive, than to multiply, the profit will be only on big N. The idea was in spending storage and to receive from it a profit. I.e. 2400000 int gets into storage, therefore we take and we are not soared about storage.

23

Re: Re: problems from the headhunter

Hello, Lexey, you wrote: L> It not apparent, but quite real. Expressed in complexity of the code and expenses of time for its implementation. L> unordered_set it is implemented through the hash table. In such tasks nobody implies manual implementation of standard data structures. They are in any more or less decent . I Agree simply normally  to estimate, that convenient counters  will cost. unordered_set - not the panacea, is sometimes got hardly faster access, but at the big input parameters he demands for this great volume of storage. L> is LLRB-tree which is implemented strongly easier, than normal RB-tree. Did not hear, it will be necessary to look. At Babenko read about Splay-tree which like would shuffle elements at each reversal and too provide the correct asymptotics at simplicity . But I did not risk in the remained days (the task was allowed per day) to try to implement pioneer (in good sense development, took old antiquated AVL. L> Whence billions elements there undertake? For the given dimensionality of the task there even at worst () it turns out levels of twains less than 7 * 136 elements. These are copecks. For the given dimensionality hands consider all, without everyones there  It would be desirable to accelerate so that for the big worked. If parameters remain in frames uint32_t them can be hardly less than 2^37 that already about hundred billions. Thus the result like would be considered for quite reasonable time: for a basic level 2 it is necessary to fulfill the order amax=4G operations, for a basic level 3 already there is less than one million, further all very quickly decreases.

24

Re: Re: problems from the headhunter

Hello, StatujaLeha, you wrote: a C>> the Formula for upper bound minFactorial (p, e) very strange, p ** sqrt (2*e) it nevertheless is normal much more, than p*e, SL> Yes, it not simply strange, but incorrect Well probably it is impossible to tell that it incorrect if provides the correct result Actually true will be any formula on which the result turns out not less that minimum number, you, probably, provides it. SL> the idea was such: if at us it is set m to count a level e from which idle time p enters in m!, we should use the known formula. SL> this formula such that has races in points, multiple p. Therefore we search minimum q such that (p ** q)! % (p ** e) == 0, and we go downwards steps in the size p further. SL> Replaced the formula on qMin = int (ceil (log (e * (p - 1) + 1, p))), became faster: http://ideone.com/22C4V6 SL> But the variant with x = p*e is all the same better: http://ideone.com/vmy6tN That is took the maximum boundary approximately e * (p - 1) + 1, but approximated upwards to a number level p. I in any way will not understand, what for to approximate to a level? Abundantly clear that (e*p)! % (p ** e) == 0 (in that factorial is exactly e the factors sharing on p). On the other hand, that known formula is a geometrical progression in which from each member its integer part, therefore its total of strictly less total "not cut off"  which it is equal x / (p - 1) is taken. Total we received a segment [e * (p - 1) + 1; e * p] on which certainly lies our optimal x. As minimum x, obviously, it is multiple p (in a factorial the last factor should bring a victory), them and it is necessary to sort out, from any end. As the left boundary corresponds in a type e * p - e + 1, and the right boundary e * p is multiple p it is obvious that at e <= p (the most frequent case) on this segment lies exactly one number, multiple p - its right boundary, therefore checkFactorial it is possible not to calculate at all. That is, apparently, it is necessary to approximate to multiple, instead of to a level though (positive) the level is too multiple And though you approximate lower bound, and the total name upper, but calculation shows that this number will be valid upper bound, though probably and enough far (1481124 misses for a segment from 23M to 24M). Rescues only that for e=1 (the main case) the formula (without the registration of errors) gives exactly p (as well as previous But here if log (p, p) it appears hardly more , it is necessary to transverse p variants. And here for e=2 both give p^2 instead of 2*p, that is for such numbers, and approximately sqrt (N)/log (sqrt (N)), it is necessary to transverse them approximately p superfluous variants, that is all approximately N/log (N) that practically explains excess. SL> the idea was in spending storage and to receive from it a profit. I.e. 2400000 int gets into storage, therefore we take and we are not soared about storage. Well, received constant (multiplyings against divisions) a profit in comparison with factorization of each number by means of a sieve. There is a question how to optimize further when storages already begins  for all numbers to N, but a tested segment [M; N] still gets into storage. For  sieves on  still gave me storage for N=240M, but for N=2.4G - already hardly. And small modification of your approach can help, about it I and wrote. Basically, even if [M; N] does not get into storage, it can be broken on slightly getting and to turn with everyone this focus. And the sieve turns out semibit instead of . It is a pity only that to divisions instead of multiplyings to pass, probably, it is necessary. And yes, PyPy is slightly

25

Re: Re: problems from the headhunter

Hello, Kodt, you wrote: To be stunned! The sieve of Eratosthenes for result of prime numbers works faster, than checks on prior numbers. On 2.4 - in 6 times (0.6 against 3.7). On 24 - in 10 times (7.9 against 79). Even if to get rid of constant reselection of storage. I will know. Well knowingly he invented it the Correct sieve works for O (N*log (log (N))), check on previous - for O (N^1.5/log (N)), it without speaking about the constant price of division against multiplication. On idea, on 24 million there should be a difference of the order of hundred times, whence such optimistical digits? There is any code?