621A - Wet Shark and Odd and Even

First, if the sum of all the numbers is already even, then we do nothing. Otherwise, we remove the smallest odd number. Since, if the sum is odd, we need to remove a number with the same parity to make the sum even. Notice it's always bad to remove more odd numbers, and it does nothing to remove even numbers.

Let's start with two bishops (x1, y1) and (x2, y2). Notice that if (x1, y1) attacks (x2, y2), either x1 + y1 == x2 + y2 OR x1 — y1 == x2 — y2. So, for each bishop (x, y), we will store x + y in one map and x — y in another map.

Let *f*(*x*) be the probability that the product of the number of flowers of sharks *x* and is divisible by *p*.

We want the expected value of the number of pairs of neighbouring sharks whose flower numbers are divisible by *p*. From linearity of expectation, this is equal to the probabilities that each pair multiplies to a number divisible by *p*, or *f*(0) + *f*(1) + ... + *f*(*n*). (Don't forget about the wrap-around at *n*)

Now, for each pair of neighbouring sharks, we need to figure out the probability that their product is divisible by *p*. Consider an interval [*l*_{i}, *r*_{i}]. How many numbers in this interval are divisible by *p*? Well, it is easier if we break the interval [*l*_{i}, *r*_{i}] up into [1, *r*_{i}] - [1, *l*_{i} - 1]. Since 1, 2, ..., *x* contains numbers divisible by *p*, the interval [*l*_{i}, *r*_{i}] contains numbers divisible by *p*.

Now, consider two numbers and , with . Let *a*_{i} be the number of integers divisible by *p* in the interval [*l*_{i}, *r*_{i}], and define *a*_{j} similarly. Now what's the probability that *f*_{i}·*f*_{j} is divisible by *p*? We can count the opposite: the probability that *f*_{i}·*f*_{j} is not divisible by *p*. Since *p* is a prime, this means neither *f*_{i} nor *f*_{j} is divisible by *p*. The number of integers in [*l*_{i}, *r*_{i}] not divisible by *p* is *r*_{i} - *l*_{i} + 1 - *a*_{i}. Similar for *j*. Therefore, the probability *f*_{i}·*f*_{j} is not divisible by *p* is given by . Therefore, the probability it is can be given by . Now, just sum over this for all *i*.

The tricky Rat Kwesh has finally made an appearance; it is time to prepare for some tricks. But truly, we didn't expect it to be so hard for competitors though. Especially the part about taking log of a negative number.

We need a way to deal with *x*^{yz} and *x*^{yz}. We cannot directly compare them, 200^{200200} is way too big. So what we do? Take log! is an increasing function on positive numbers (we can see this by taking , then , which is positive when we are dealing with positive numbers). So if , then *x* ≥ *y*.

When we take log, But *y*^{z} can still be 200^{200}, which is still far too big. So now what can we do? Another log! But is it legal? When *x* = 0.1 for example, , so we cannot take another log. When can we take another log, however? We need to be a positive number. *y*^{z} will always be positive, so all we need is for to be positive. This happens when *x* > 1. So if *x*, *y*, *z* > 1, everything will be ok.

There is another good observation to make. If one of *x*, *y*, *z* is greater than 1, then we can always achieve some expression (out of those 12) whose value is greater than 1. But if *x* < 1, then *x*^{a} will never be greater than 1. So if at least one of *x*, *y*, *z* is greater than 1, then we can discard those bases that are less than or equal to 1. In this case, . Remember that , so . Similarly, .

The last case is when *x* ≤ 1, *y* ≤ 1, *z* ≤ 1. Then, notice that for example, . But the denominator of this fraction is something we recognize, because 10 / 3 > 1. So if all *x*, *y*, *z* < 1, then it is the same as the original problem, except we are looking for the minimum this time.

First, let us build an X by X matrix. We will be applying matrix exponentiation on this matrix. For each modulo value T from 0 to X — 1, and each value in the array with index i between 1 and n, we will do: matrix[T][(10 * T + arr[i]) % X]++. This is because, notice that for each block we allow one more way to go between a modulo value T, and (10 * T + arr[i]) % X. We are multiplying T by 10 because we are "left-shifting" the number in a way (i.e. changing 123 -> 1230), and then adding arr[i] to it. Notice that this basically simulates the concatenation that Wet Shark is conducting, without need of a brute force dp approach.

How foolish i am, i thought of the Problem C's Independence.at the end of the contest i finally figure out that if ppl_2 have a number can be divisible by p,we dont need to care about what number ppl_1 and ppl_3 take:(

They are not people. They're sharks :p

D is more difficult than E...

That's ridiculously common...

Probably it's just because DP/Matrix exp. are well-known and heavily trained topics, whereas D is somewhat non standard. I solved D in 12 minutes and E in more than 1 hour... Though I used python's decimal for D which is a bit hacky.

in Problem C why did you say x*(x+1) mod n divisible by p?

isin't x(x+1) divisible by p?

Sorry, I fixed it.

Problem E can be solved without matrix exponentiation. Denote by DP[b] the solution array (i.e. DP[b][k] is the actual solution, the others are needed for the computation). Now, if we compute DP[2 ^ i], for all i < 31, we can easily get DP[b] by making use of the binary representation of b. The whole solution hinges on a function Unite(a, b), which computes DP[a + b] from DP[a] and DP[b] in time O(x ^ 2).

same solution

There my solution (runtime somewhere, but guess idea is correct)

denote D1[d][k] count d-digit numbers with k-reminder. Easy to calcuate by:

D1[d][(10 * j1 + j2)] += cnt[j1] * D1[d — 1][j2]; 0 <= ji < x;

Now make blocks 1000, 1000, 1000,.... b % 1000 digits (b / 1000 + !!(b % 1000) blocks);

denote D2[d][k] count d-block numbers with k reminder. Calculate absolutely analogically.

Then ans is D2[blockCount — 1][k]. Complexity is O(1000*x^2).

If i'm thinking correct, complexity would be O(10^6 * x^2). You'll make D1 in O(1000*x^2) but then there can be 10^6 blocks of 10^3 length . If you again divide your 10^6 blocks into 10^3 "big" blocks , then it should work.

Thanks for correcting, I'm "the genius of Math":D

Can you elaborate slightly on your approach?

What exactly are we doing with matrix exponentiation in problem E? Can somone please explain. I am not able to understand the editorial solution!

Optimize dp.

Thank you. That was very informative :P

:)

To simplify the explanation, it is assumed that all computations are done modulo 1, 000, 000, 007.

First, note that the

ngiven digits are not important -- what is important is the occurrences of each digit. Letocc[d] be the occurrences of digitd.We will try solving this problem using DP. Let

dp[i][j] = the number of ways we can pickidigits such that the final modulo isj.The base case is obviously

dp[0][0] = 1. Fori> 0, the recurrence can be given as:dp[i][j] =sum{occ[d] ×dp[i- 1][a]}, for all 1 ≤d≤ 9, and for eachd,ais an integer 0 ≤a<Xwhere (a× 10 +d)%X=j.(Intuitively, given a number consisting

i- 1 digits that isamodulox, we can form a number consisting ofidigits that isa× 10 +dmoduloX=j, by appending the digitd.)The final answer would be

dp[B][K]. Unfortunately, this DP will get TLE asBcan be up to 10^{9}. To speed it up, we will use matrix exponentiation trick on the recurrence.Suppose we have a vector

F_{0}consisting ofXelements, where.

Exercise 1: Compute the value of the elementsF_{0}!Now, construct a

X×XmatrixT, in such a way thatF_{1}=TF_{0},where

.

Exercise 2: Compute the value of the elements ofT!In a similar way, we can compute

F_{2}=TF_{1}=T^{2}F_{0}. Now, we want to computeF_{B}=T^{B}F_{0},which is,

.

The answer will be...

F_{B}[K], which isdp[B][K]!T^{B}can be computed in using exponentiation-by-squaring, which will fit the time limit.That was cool. Thank you very much.

I think it's possible to solve in without matrix multiplication. Submission: 15723291

And it looks like with FFT it can be optimized to

This is wonderful.

But how to construct the matrix T?

Initialize the matrix with all zeroes, then increase the cells in the way mentioned in the editorial.

You can check http://fusharblog.com/solving-linear-recurrence-for-programming-contest/ :)

thank you !

D can be solved with complex numbers, to avoid having to treat cases where some numbers are smaller than one, differently. Note that the real part of

log(log(x)) is growing iflog(log(x)) is real, and decreasing if it has an imaginary part. So you can just write a comparison function to find the maximum.Awesome, now we can easily handle such cases that log(x) is less than zero. Thanks for your idea.

great idea!

Can you explain how to compare between complex numbers?

If

x> 1, thenlog(log(x)) is an increasing function, and ifx< 1, thenreal(log(log(x))) is a decreasing function, because taking a logarithm of a negative number results in something like this:log( -x) =log( - 1·x) =log( - 1) +logx=iπ +log(x). (Assuminglog(x) is done in basee) Therefore, to compare two numbers by their loglog, you can do something like this:"long double" is still required,because the result of y^z^x will exceed the range of "double" on (test 9: 185.9 9.6 163.4 ) when using "complex"

You shouldn't ever actually calculate the value of y^z^x, since

log(log(y^{zx})) =log(z^{x}log(y)) =xlog(z) +log(log(y)). That's the whole point of using log log, you can compare those gigantic numbers without actually calculating them.I made a mistake. :< I forgot to modify the calculation function.I just calculated log(y^z^x).

Is there a good matrix library in C++? Or you simply write an algo for matrix binpow each time you need it?

But

y^{z}can still be 200^{200}, which is stillfar too big.Apparently, one of the passed solution use that method.

Interesting. How it works? In C# we will just get Infinity value in such case, and Infinity is equals to another Infinity, so wrong result on case #9.

Codeforces compiler suggest that maximum range of long double is 1.18973 × 10

^{4932}, which is greater than 200^{200}≈ 1.6 × 10^{460}Ouch, nice. In C# max for double is just 10^308.

longdouble. C# does not support it.C# also has BigInteger type. Wouldn't be suitable for this particular problem, but very useful for others.

Can somebody help me with this 15713106 submission for C? I cannot understand why it failed.

UPD: I fixed it by changing the printf call to cout 15715786

Is this issue known/documented somewhere? MikeMirzayanov

http://codeforces.com/blog/entry/23147?#comment-275981

E can be done in too- let

v_{j}be the array of sizexsuch thatv_{j}[i] is the number of ways of getting a number that isimod(x) after j steps;v_{2j}andv_{2j + 1}can be computed fromv_{j}in . The crucial fact here is that if the value of the firstpblocks isimod(x) and that of the lastqblocks isjmod(x), then the whole number will bei+ 10^{q}·jmod(x).You mean the whole number is (i * 10 ^ q + j mod x) since i comes first .

Thanks for the editorial post. :D

can anyone explain C in easier way

The intuition is that if you can find out the probability of each person, then you can solve the whole problem. This is because the whole sum of money is the expectation of each cases(1-2, 2-3, etc..). The expectation of each pair is 1 — (1-p_i)(1-p_j) because the pair would not get paid only when both don't satisfy the condition. This is same for all the pairs, so now we just need to find out the probability(expectation) of each person. This is explained in the editorials

thank you so much but i want to ask if you can tell me about a good resource to learn about this kind of problems

I'm not sure if your "these kind of questions" meant algorithm questions is general, or this particular question, but assuming the latter I recommend studying basic discrete mathematics. This set especially had a lot of math questions, and understanding of discrete mathematics will make you have a better intuition of solving problems. The more you learn, the more you'll see.

thank you

Why this approach is wrong for B

iterate each diagonal of the grid and count the number of bishop x in that diagonal .

if the number of bishop is > 1 than we add x(x+1)/2 to the answer .

i get accepted with the same idea you may made a mistake in the code http://codeforces.com/contest/621/submission/15705229

This is my submission

It has to be x(x-1)/2 rather than x(x+1)/2. A.Magdy7's solution works because he decreases x by 1 before calculating with the x(x+1)/2 formula.

yeah you are right , silly mistake but even when i changed x by x-1 its still give WA .

Nope.

Consider there are x bishops in a diagonal. The first bishop has x-1 bishops to pair with, the second bishop has x-2 bishops to pair with, and so on. We can notice the number of pairs is (x-1)+(x-2)+...+1 which can also be expressed as (x-1+1)(x-1)/2 = x(x-1)/2.

i fix that but still got a WA

because you don't search in all the diagonals you always search above the main diagonal in both direction and don't search under it

You right , i got AC , thanks .

My solution of C : First we see how to find the expected money given to any two neighbouring sharks :

Here, is my code which i couldn't submit because of internet issues : Code

Can you explain something about linearity of expectation?

So Java's sorting does some sketchy things, but only some of the time...lol

http://codeforces.com/contest/621/submission/15716716 AC

vs

http://codeforces.com/contest/621/submission/15716729 TLE

with the only difference switching

with the unrelated

At least my rating is historic now!

I'm pretty sure this is because Arrays.sort calls quick sort for primitive data types and merge sort for objects. So there must have been an anti quick sort test case, in which quick sort is called for one solution but not the other.

Why can't I open problem D? it says : Can't read or parse problem descriptor. Is any one else getting this error?

Why my code although passing test-case 9 of 100000 numbers but getting TLE on test-case 15 of 500 numbers http://codeforces.com/problemset/problem/621/A http://ideone.com/OWI8Ba

i=n-1; in each iteration, cycle infinity, for example, in this test: 3 2 3 4

"But y^z can still be 200^200, which is still far too big" Can anybody help to find a test that breaks my solution 15713937 ?

For D: Python's decimal for the win :) one logarithm is enough

15703568

Could anyone help to understand what is wrong here with Problem D?

submission with EPS = 1e-14 gives wrong answer on test #134: 200.0 200.0 200.0: 15719829,

the same code with EPS = 1e-13 gives AC: 15719618.

I've logged the difference between two values of

m*log(m) +log(log(m)) form= 200.0 in first case and it appears to be ~5e-14, so this is the reason. But when I'm trying to reproduce this problem manually (see main at 15719829), it is giving zero difference. On my mac with clang 6.0 compiler case 200.0 200.0 200.0 gives proper answer: x^y^z.It is OK that taking of two exactly the same arithmetic expressions with "equals" double numbers can give a different answer?

15735486 I change left + EPS < right to left — right < 0. Also you can use long double instead double.

Thank you! But another interesting thing is that solution with 1e-14 passed when I changed compiler on the MS Visual Studio 2010 on CF: 15735359.

Calculating C the probability itself (and not the 1-p) gives WA because of error approximation.

I calculated the probability of every single position getting a multiple of the prime (multiplied by 4000) and, using inclusion-exclusion principle, removed the the cases where two consecutives where primes (multiplied by 2000).

If someone could explain me why this is incorrect or if the jury had a tighter error, I'd be very grateful.

I don't know how to post links, but the submission was: 15706251

Your submission link: To post a link, just hit ctrl+L and enter the link.

Thank you for the tip. I still don't think the maximum error in the problem C was correct since the direct was generated error almost 10^5

In test 69 of problem D x=0.2, y=0.7, z=0.6. My program output (y^z)^x on this test. But there is expected (y^x)^z. But

(0.7^0.6)^0.2>(0.7^0.2)^0.6! I have checked this on the calculator. (0.7^0.6)^0.2-(0.7^0.2)^0.6=1.9535924907431949702433539286085e-38.In fact, (0.7^0.6)^0.2=(0.7^0.2)^0.6 since (a^b)^c=a^(b*c). Thus you do the one with the smaller index.

I see, thank you.

I bet D is simpler, so left no time for E.....

Problem D can be coped with in this way: notice that log log x^y^z = z*logy + log log x, log log (x^y)^z = yz log log x; so the only problem to discuss is log log x. if log x is positive, that is easy, cuz f(x) = log log x is a strictly increasing function, so the larger the better. if log x is negative, we take log -log x for the log log x part. so the function became strictly decreasing, and since two cases use different functions, they can not be compared. And then the only problem is the order.

Isn't that what's written in the editorial?

In problem C : Aren't f(i) and f(i+1) dependent? Is linearity valid even if they are dependent?

Yes. That's called "linearity of expectation".

I am a bit confused. You mean to say that f(i) and f(i+1) are dependent?

They are dependent, but their expected sum is not -- E[f(i) + f(i+1)] = E[f(i)] + E[f(i+1)], so you can compute the values independently.

Thanks for clearing my head. :)

I failed main test C, just because I haven't changed the answer into double, and printed 6 decimal digits behind the point :(

How does this solution get accepted ?

Apparently, long double covers a large portion of the numbers if thats what you are wondering about. Even larger than 200

^{200}Check this snippet Credit: S.Saqib

Hey, everyone?

I am still unable to fully understand the explanation for problem 3. I think that there must be some sort of relation between pair (i,i+1) and pair (i,i-1) (and/or pair (i+1,i+2)) as if s[i]*s[i+1] is divisible by p, then s[i+1]*s[i+2] and/or s[i-1]*s[i] will be divisible by p. How can we just sum them up independently like that?

Could someone please elaborate on this case for me? Thank you.

You can iterate through the array, calculating expectation for each element, thus you will get the relation you're looking for. You need to handle 2 cases: when the selected "shark" gets a number divisible by p, and when it does not, but one of it's 2 neighbours does. You can check out my code if needed

Oh, i see your point, you're asking why we can handle each pair separately. See,

`E = x[1] * p[1] + x[2] * p[2] + ..`

, where E — the expected value, p[i] — probability with which x[i] will be added to the answer. The thing is, the mathematical expectation can be easily divided into independent terms, because in fact, expectation is a linear polynomial, and it's distributive property allows us to calculate expectation for sub-problems, summing up the resulting values. I mean,`if x[i] = x[i]' + x[i]'' -> p[i] * x[i] = p[i] * x[i]' + p[i] * x[i]''`

Therefore, we can divide the sum for the whole circle into sum of pairs' answersOh thank you so much, the trouble seems to come from my limited knowledge of mathematics. Your comment helps me figure out that it is linearity of expectation. I will do some googling on it.

"can be

EASILYdivided into independent terms, because in fact, expectation is a linear polynomial, and it's distributive"I'd like to give one more level of intuition upon that, cause I saw exactly that in the wikipedia and for some reason it haven't satisfied me :)

But, before telling the whole story and laying out all of my thoughts, I'd like to test my metaphors. My metaphors work for me, but they might not work for you. If it seems appealing to you, I will continue to end the story. If not... well, at least I've tested my hypothesis :)

Let's try to establish the similarity of the problem to the sequence of 8 bits like that:

`01110010`

.If we stretch our imagination we can see the relationship is as follows: when the pair of sharks grows

goodamount of flowers the Wet Shark gives away1, when they grow thebadamount of flowers the Wet Shark gives away0.The total amount of money that the Wet Shark gives away in the case

`01110010`

is 0 + 1 + 1 + 1 + 0 + 0 + 1 + 0 =4. The maximum amount of money that the Wet Shark can possibly give away is 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 =8* 1 =8.Imagine that the Wet Shark should prepare it's money beforehand in the bags for money. How many bags should the Wet Shark prepare? These are all the possible

sums ={0, 1, 2, 3, 4, 5, 6, 7, 8}.Now there are a lot of bags the Wet Shark prepared, but, to the time the flowers grow up, it would be nice to have the bag he needs to give away be right before him, so that the Wet Shark doesn't need to look for the right bag among all of those in the pile.

So, what is the bag that the Wet Shark should

expectto give away? To know this, we have to know how many of the possible events force the Wet Shark to give away the bag labeled with some number X.Let's go through all these bags one by one and see how many ways there are to arrive at each amount.

For bag labeled

X= 0 there is only one way to arrive at it, namely`00000000`

.For bag labeled

X= 1 there are = 8 ways to get it:`10000000`

,`01000000`

,`00100000`

,`00010000`

,`00001000`

,`00000100`

,`00000010`

,`00000001`

.For bag labeled

X= 2 there are = 28 ways to get it (without details :) )For bag labeled

X= 3 there are = 56 ways to get it.For bag labeled

X= 4 there are = 70 ways to get it.For bag labeled

X= 5 there are = 56 ways to get it.For bag labeled

X= 6 there are = 28 ways to get it.For bag labeled

X= 7 there are = 8 ways to get it.For bag labeled

X= 8 there is again only one way to get that result:`11111111`

.So, now we can make up the function

Pwhich has as an input the label on the bagX= {0, 1, 2, 3, 4, 5, 6, 7, 8} and returns the number of ways to force the Wet Shark to give that bag of money.P(x) = :P(X= 0) = 1P(X= 1) = 8P(X= 2) = 28P(X= 3) = 56P(X= 4) = 70P(X= 5) = 56P(X= 6) = 28P(X= 7) = 8P(X= 8) = 1The function

Pcould be extended to all natural numbers by returning0to all of the inputs except for the inputs in the range 0..8, e.g.:P(X= 115) = 0 <- There arezeroways to force the Wet Shark pay 115 dollars.By the way, a good read about the linearity of the expected value: an intuitive explanation for the linearity of expectation.

It's a dumb mistake.