### E404_Not_Found's blog

By E404_Not_Found, 7 weeks ago,

Hello everyone!

Thanks for participating in TheForces Round #5 (PerfectForces).

[problem:425963A]

Editorial

[problem:425963B]

Editorial

[problem:425963C]

Editorial

[problem:425963D]

Editorial

[problem:425963E]

Editorial

[problem:425963F]

Editorial

[problem:425963G]

Editorial

• +25

 » 7 weeks ago, # |   0 For problem F we can use a sieve to precalculate the number of divisors of each number from 1 to N.My submission
 » 7 weeks ago, # |   0 can anyone explain D question i m not getting editorial
•  » » 7 weeks ago, # ^ |   +8 First sentence of editorial means that: $a_1$ & $\ldots$ & $a_n=x\implies\forall i:a_i=x$ | $smth_i$& will keep only the bit which is present in all operands. You, probably, got it.Second sentence of editorial means that: $smth_1$ & $\ldots$ & $smth_n = 0$There is no benefit of having some bit in all $smth_i$. And the other reason is that the first equality will not hold (smth is smth, but smth is not any). I quess, you fiqured it out during a contest. Now:Third sentence: We want minimum $a_n$. Bits that are set in x also are set in $a_i$. What is the minimum possible $a_1$? Well, we can take $a_1=x$. What is minimum possible $a_2$? we can take $a_1$ and set 'the least significant' zero-bit in it to one. What is minimum possible $a_3$? We take $a_1$ and set 'the next least significant' zero-bit to one. What is minimum possible $a_4$? We take $a_1$ and set both 'the least significant' and 'the next least significant' zero-bit to one. Now you need to notice that $a_i$ are constructed in a way of filling empty slots (zero-bits) of $a_1$. So if we want to make $m$ steps from $x$ we need to look at a binary representation of $m$ and fill this representation in empty slots of $x$.For example: $x=100101_2$ $m=4=100_2$Then: $a_1=x$Empty slots of $x$ are $1[0][0]1[0]1_2$And $a_{1+m}=a_5$ will be $1[1][0]1[0]1_2$
•  » » » 7 weeks ago, # ^ |   0 what will be the values of a for x u have taken in example
•  » » » » 7 weeks ago, # ^ |   0 Your guess..
•  » » » » » 7 weeks ago, # ^ |   0 100101 100111 101101 101111 110101
•  » » » » » » 7 weeks ago, # ^ |   0 i got much of the solution but checking on binary representation of m how will this help?
•  » » » » » » » 7 weeks ago, # ^ |   0 So you know what to do on paper, but don't know how to instruct a machine to do the same? I think the more problems on bit manipulation you encounter, the more 'manipulative' in regard to bits you will become. You can look at program text, if you wish. I don't think my explanation will be more clear then the code.Binary representation of m is needed to know what to insert in empty slots of $x$. In initial problem we need to find $a_n$ that means that we need to make $n-1$ steps from $a_1=x$. We can say that to solve initial problem we consider $m=n-1$. To implement this we traverse index on $m$ and for it we search for empty slot of $x$ with the help of while-loop.The intuition is simply we write $m$ inside $x$.
 » 6 weeks ago, # |   0 Hey there! Can someone help me with this? 193508278 this code, the output for the last test case i.e. for 1 1000000000000000000 my local machine is giving the right answer which is expected here. But when submitted it is giving WA verdict.