There exists 4 bacteria in your shoes at time t=0 seconds.

A bacteria replicate into 2 with a probability p and otherwise die every second.
What is the expected number of bacteria's at the end of 70 seconds.

Constraints:
(0<=p<=1)
And you have to report the floor of the answer.

I saw this question on a test which allowed usage of computer but I think it can be done using total maths too.
I thought of doing a dp with state { time , number of bacteria's } which is exponential in nature.
Either way I don't have a solution.
Obviously, if we can solve it for 1 bacteria we can solve it for 4 too but this isn't a significant improvement either .

ASN — Algorithm Society of NSIT, are proud to announce the ASN Epoch1.0!

It will be a Short contest consisting of 5 problems with all problems visible from the start and no hacks. Its a 3 hour contest with 5 problems.

Details

Contest Date : 19th February 2016

Time : 2130 to 0030 IST

Programming Partner : Codechef

Contest Link : CodeChef

Prizes

• There are cash prizes worth ₹ 5,000 for top 3 NSITians.

• Top 10 Global competitors will be awarded CodeChef Tshirts too.

The problems in the contest are prepared by anh1l1ator , notiitian and I_Love_CardiB.

Special thanks to code_destroyer , Sandeep_2795 and Mayank Hooda for their help.

For more details / contact details, visit:

• Our Facebook Event Page
• Or contact us at: ASN

Do share it with your friends who are interested :D We assure you that we have tried our level best to give everyone a good set of problems and clear problem statements with nice test data(as I am the tester of the round :D ) .

Good Luck! Hope to see you participating! There will be a detailed analysis after the Contest is over!

I am familiar with Mo's algorithm and there are multiple blogs explaining it!

But this problem Link although based on square root decomposition only had a very nice idea. Can someone post similar problems? According to Editorialist this approach is known as Caching of updates/queries ( Google tells some random stuff and nothing useful).

Thanks!

I was trying to solve COURIER on spoj . [ Link ]

As the Sum of couriers to be send are only 12 I broke up it into 12 individual orders.

My state : F[i][mask] represents the minimum cost for completing all the couriers in mask with last courier activity completed being i.

Recurrence : F[i][mask] = minimum of ( k belongs to subset denoted by mask F[k][ subset — { i } th courier ] + Cost of going from end of k th courier to beginning of the i th courier + Cost of going from beginning to end ).

Now, My answer will be F[ x ][ all the couriers denotes by 11111... ] + Cost to go from end point of x activity to starting point

Base Case being for all subsets containing only one activity with cost = the cost of going to the end of the courier from starting point through the starting point of the courier.

The Cost for going from some point to other point is calculated via All pair shortest path (Floyd Warshall)

I have been trying it for 8 hours now , and my code doesn't give right output on sample case I don't know why !! Can someone point out the mistake in my method or recurrence or state ??

Just in case if you want to check out if there is some mistake in my code ?

http://ideone.com/FLhsog

I saw some solutions too online they had a different state but I think my state has every important information for transitions!! Moreover their solutions too had same kind of idea!!

So , formally the problem statement :

You are given a sequence A of N (N≤250000) integers between 1 and 50000. On this sequence you have to apply M (M≤10000) operations of the form: modify the i-th element in the sequence and then say how many inversions are there in the sequence. The number of inversions in a sequence is given by the number of pairs (i,j) with i < j and Ai > Aj.

My approach is to , 1) Divide the array into square root pieces , and maintain a fenwick tree for each of the blocks that stores 1 corresponding to each number in that block ( For querying number of numbers lesser than a particular value in that block )

2) Count the inversions .

3) Now whenever Update comes , I update get inversions from all blocks except the index's box(I count the difference between the inversions due to the new value — inversions due to old value and add it to the inversions) and add it ! Plus I traverse the block of index ! Total Query time O( Sqquare root of N * log 50000 ) .

It is giving TLE Even with fast scanning and outputting Here is my code , can it be further optimised ? Ideone

Link to problem Spoj

Is there any other approach to it ?

In general , I am sometimes stuck at creating bottom up for a question... So I want to know how to think while constructing bottom up... For example while I was able to think the recursive solution for this question, I am simply unable to construct bottom up for this question(and not able to understand the solutions of others too)...Problem linkLink Link to my memoized solution Solution