## 895A - Pizza Separation

We can notice that if one of the sectors is continuous then all the remaining pieces also form a continuous sector.If angle of the first sector is equal to *x* then difference between angles of first and second sectors is |*x* - (360 - *x*)| = |2 * *x* - 360| = 2 * |*x* - 180|. So for each possible continuous sector we can count it's angle and update answer.

Time complexity *O*(*n*^{2}) or *O*(*n*).

## 895B - XK Segments

First, we need to understand how to find the number of integers in [*l*, *r*] segment which are divisible by *x*. It is *r* / *x*–(*l* - 1) / *x*. After that we should sort array in ascending order. For each left boundary of the segment *l* = *a*[*i*] we need to find minimal and maximal index of good right boundaries. All right boundaries *r* = *a*[*j*] should satisfy the following condition *a*[*j*] / *x*–(*a*[*i*] - 1) / *x* = *k*. We already know (*a*[*i*] - 1) / *x*, *a*[*j*] / *x* is increasing while *a*[*j*] increases. So we can do binary search on sorted array to find minimal/maximal index of good right boundaries and that mean we can find the number of good right boundaries.

Time complexity *O*(*n* * *log*(*n*)).

## 895C - Square Subsets

We can notice that *x* is a perfect square of some integer if and only if each prime number enters decomposition of *x* into prime factors even times. There are only 19 prime numbers less than 70. Now we should find the bitmask for each integer in [1, 70] by the following way: There is 1 in bit representation of mask in *k*-th place if *k*-th prime number enters decomposition of that number odd times. Else there is 0. For each integer between 1 and 70 we need to find the number of ways we can take odd and even amount of it from *a*. Let *f*1[*i*], *f*0[*i*] be that number of ways relatively. Let *dp*[*i*][*j*] be the number of ways to choose some elements which are <= *i* from *a*, and their product has only those prime numbers in odd degree on whose index number *j* has 1 in binary representation. Initially *dp*[0][0] = 1.

*dp*[*i* + 1][*j*] + = *dp*[*i*][*j*] * *f*0[*i* + 1]

The answer is *dp*[70][0].

Time complexity is *O*(*max**2^cnt(max)), where *max* is maximal integer *a*[*i*], and *cnt*(*max*) is the number of prime numbers less than *max*.

## 895D - String Mark

Suppose that we can calculate the function *f*(*s*) equal to the number of permutations of the string *a* strictly less than *s*. Then the answer is *f*(*b*) - *f*(*a*) - 1. Now we need to understand how to find *f*(*s*). First we should count the number of occurrences of each letter in the string *a*, *cnt*[26].Than we can iterate through the position of the first different symbol in the permutation *a* and the string *s* and update the number of remaining symbols *cnt*[26]. For each such position, we need to iterate through the symbol in the permutation of *a* which will stand in this position. It must be less than the character at this position in the *s* string. For each such situation we can calculate and add to the answer the number of different permutations that can be obtained using symbols not currently involved. Their number is stored in *cnt*[26]. In its simplest form, this solution works in *O*(*n* * *k*^{2}), where *k* is the size of the alphabet. Such a solution can't pass the tests, but it can be optimized to *O*(*n* * *k*), and that is enough to solve the problem.

Time complexity *O*(*n* * *k*), where *k* is the size of alphabet.

## 895E - Eyes Closed

For each position we need to maintain mathematical expectation of the value on it. Initially, for position *i*, it is *a*[*i*]. Let's process the query of the first type. Each number from the interval [*l*1, *r*1] remains on its place with probability (*r*1 - *l*1) / (*r*1 - *l*1 + 1). The probability that it will be replaced by a number from [*l*2, *r*2] is 1 / (*r*1 - *l*1 + 1). The mathematical expectation of the number to which it will be replaced is the arithmetic mean of sum of the mathematical expectation of numbers in [*l*2, *r*2], let it be *x*. Then, to update the expectation of a number from [*l*1, *r*1], we need to multiply it by (*r*1 - *l*1) / (*r*1 - *l*1 + 1) and add *x* / (*r*1 - *l*1 + 1) to it. That is, the query of the first type is reduced to the query multiplying all the numbers in a segment and adding to them a number. To process the second type query, you must find the sum of the numbers in the segment. All these queries can be processed with the help of segment tree.

Time complexity *O*(*x* + *q* * *log*(*n*))

Nice :) It was good problems!

Hi! As a tester, I enjoyed solving the problems. Thanks to NBAH for problems.

Problem E was nice segment tree with advanced lazy propagation problem, the special lazy propagation in this problem was instructive.

Problem D was mixing of the known dp-on-digits idea and some combinatorics, it was a bit hard for this position.

Problem C could be solved by a straight-forward meet-in-the-middle solution that is really hard for this position. Also, it could be solved with dp-on-masks. I think that this idea is a bit hard for div.2 C problem, too.

To summarize, although the round was a bit hard, because of problems C and D, anyway, the problems were nice.

I don't think D was that hard for Div2 D. Neither the idea or the implementation of the procedure described in the editorial isn't very difficult, you don't have to do DP on digits. The required combinatorics knowledge wasn't unreasonable, too. D was arguably easier than C, I think.

Can you explain the meet in the middle soluton?

Show each number as a 19-digit mask. There is at most 44 different masks (you can test). Divide this masks into two groups. For each group find all of the different masks they can make by xor of some subset. The answer can be calculated easily using meet in the middle.

Could someone please explain in problem C what exactly

`dp[i][j]`

is? I understood that`i`

is the upper limit of the number but what exactly is`j`

? Also, if`i`

is the upper limit then shouldn't the`dp`

array be`ll dp[71][1<<20]`

, so why does the author's solution set it as`ll dp[2][1 << 20];`

. Please explain. Thanks.If you understand the definition of

`dp[71][1<<20]`

, then you're on the right track! For this case,`dp[i][j]`

is only dependent on`dp[i-1][j]`

— previous step, therefore, we don't need to store all steps until`i-1`

(exclusively).Oh! Silly me. Thanks. :)

Would anyone mind explaining the solution to Problem C in more detail? I understand the bitmask, but I don't understand the definitions for

f1[i],f0[i] and thedp[i][j] it uses.Lol

f1[i] is the number of ways to choose an odd number of numbers out of a set ofa[i] numbers, andf0[i] is the number of ways to choose an even number of numbers out of a set ofa[i] numbers.It ends up being:

f1[i] = 0 ifa[i] = 0 andf1[i] = 2^{a[i] - 1}otherwise.f0[i] = 1 ifa[i] = 0 andf0[i] = 2^{a[i] - 1}otherwise.Basically know that for

k≥ 1, the number of ways to choose an odd number of elements out of a set ofkelements is equal to the number of ways to choose an even number of elements out of a set ofkelements, and they are both equal 2^{k - 1}. Here is a proof.OK, but what does this have to do with the rest of the problem? Why is this being computed in the first place?

Because the mask

jbecomes if you take an odd number ofxbut stays asjif you take an even number ofx.What do you mean by odd number of x ?

vb7401, did you get it? Because, I didn't.

Its like basic knapsack, if you include x or don't. If you include x, the mask becomes j ^ mask[x] whereas if you don't include x, the mask remains j only. The point is if you include x , you can include odd number of times x , the mask will still remain j ^ mask[x] ( xor properties) and if you take even number of times of x , the mask will still be j.

Here's another explanation.

Suppose you multiply,

2^3. 3^1. 5^2, with 2^5. 3^2. 5 ^3,

What do you get ?

2^8. 3^3. 5^5

The first number's mask = 110 Second number's mask = 101

Now, their product = 011

(it is like adding the bits, with no carry — this is another definition of the XOR operation).

So, if

f(i, mask) is the number of ways to use the first i numbers and get a product such that we get a prime with an odd power if the corresponding bit is set in mask, then.

f(i + 1, mask) = f(i, XOR(mask, MASK(i + 1)) )*f1(i + 1) + f(i, mask)*f0(i + 1)

This is because if we choose (i + 1) an even number of times, it doesn't affect the mask. But, if we choose it an odd number of times, we must perform bitwise addition of the mask and the MASK of (i + 1).

I tried to solve this problem inspired by these comments. I used top-down DP and my solution works for the first 12 test cases but fails with test case 13 and I don't get why. My code is very short. I would really appreciate if somebody could help me understand what I'm doing wrong :S. Here is the code: https://codeforces.com/contest/895/submission/45750333

a[i] in your explanation is not the same array that was given in the problem right? The way I understand it is that it is a new array that counts number of occurrences of a given number i, which can be in the range of [1,70] which in the problem was referred to as ai (1 ≤ ai ≤ 70)

Yeah you are right, what a[i] means in my comment above is the number of times i appears in the input.

Although the answer is same, I reached at it in a different way.

If there was a lower constraint on n, what would have been the solution?

Note that, it does not matter in which order we process

a[i] , the above dp holds.Let's come back to the original problem. Let's sort all the numbers. We will take advantage of the fact that there are only 70 distinct numbers and try to simulate the dp correspondigly.

If the frequency of a number would have been 1,

If the frequency of a number would have been 2,

Extending,

Now you easily shrink the first dimension from 10

^{5}to 70.Can anyone tell me why this submission 32697001 for problem C gets TLE? This 32697019 got ac, as you can see the only difference is the order i build dp states but the complexity remains the same

Hi, I think it has the same problem I had.

It is calling fast_pow(2, freq[num] — 1), that is log(n) in EVERY state of the recursion, when it could be calculated at most 70 times.

Hope this helps!

Hi,

Both submissions call fast pow(2, freq[num] — 1) in every state of the recursion, and one of them got accepted, so i don't think that should be a problem.

Thanks for the reply anyway

EDIT: Actually, precalculating powers of two up to n gives ac in first submission.

I find it a pretty nice coincidence that both today's C and the F from the last educational round required to calculate C(n, 0) + C(n, 2) + C(n, 4) + ... as a subproblem.

In the educational round, I spent some time thinking about the sum, eventually arriving to the conclusion that it's equal with 2^(n-1). Today's round, I simply brute forced the sum, without too much thought. When I looked at other submissions, I saw the 2^(n-1) term in them, and I was something like "hmmm... okay... I solved this just 3 days ago and I've already forgotten about it".

C can be solved in a more (maybe) straightforward way.

Let

dp[i][mask] be the number of way to choose some subset of firstielements and their product hasj-th prime with odd degree(ifj-th bit ofmaskis 1). Directly implementing this solution results in aO(N× 2^{19}) solution which is too slow.However, for each number

x≤ 70, only 2, 3, 5, 7 can have power more than 1. If we group up all the number whose prime divisor contains 11, we can have a smaller dp state asdp[mask][11?] denoting the parity of current product on 2, 3, 5, 7, 11. After going through all these numbers, we can get rid of everything about 11 and only store the information ofdp[mask][0]. Then, considering all the number whose prime divisor contains 13, and so on.The time complexity is

O(N× 2^{5}). In this way, we can even solve the problem with different weight on each element(i.e. sum of total weight of choosing a subset whose product is a square number).That idea make me remember this problem.

https://community.topcoder.com/stat?c=problem_statement&pm=12074

C can be solved by equation set module 2。 like a_11x_1+a_12x_2...+a_1nx_n=0 a_ij dones whether the jth number have the ith prime odd times or even times，x_i dones whether the ith number will be chosed. And the solution for these equations is the answer for the problem.It can be solved in O(n*19) using bitmask.

You mean the number of solutions of this system of equations gives the answer, right?! How do you find it?

If

Mis the matrix whosei-th column isx_{i}, then (1+) the answer is the cardinal of the kernel ofM, which is (rank-nullity theorem). The rank can be computed using Gaussian elimination in .Can B be solved using two pointers. If so, then how?

I think yes. First you sort array a. Then for every a[i], you have pointer l which a[l] is the first element has (a[l] — 1) / x == a[i] / x — k, and a[l] <= a[i]; and pointer r which a[r] is the last element has (a[r] — 1) / x == a[i] / x — k and a[r] <= a[i]. You can find r by brute-force from the current l, and for next i, you can find l by brute-forces from the last l

32681970

I still don't get C. :-(

How to slove B?

Read this solution. Ask me, what you don't understand.

Div 2B Solution

Why order? this is a continuous interval and ((a[i] — 1) / x) what does it mean？

We have sorted the array, so we have an increasing function => the interval is continuous.

Assuming that a[i] is a left border we can calculate how many integers divisible by x there are in interval [0; a[i]]. It will be a[i] / x obviously. We can do the same operation with the right border. Okay, now we want to calculate amount of integers on a segment [l; r]. It seems like it will be a[right] / x — a[left] / x, but it's wrong. For example: x = 3, a[left] = 3, a[right] = 5. We can do the following operation and get 0, but we need 1. Therefore we need to use a[i] — 1 to prevent this situation when the a[left] divisible by x.

My solution with only binsearch http://codeforces.com/contest/895/submission/32701257

Could you further explain this answer to me? What's the reasoning behind:

Also, why do you use lower_bound? Why not upper_bound?

Just cos u need to find all numbers in [max((long long)a[i], (long long)x * (k + (a[i] — 1) / x)); max((long long)a[i], (long long)x * (k + 1 + (a[i] — 1) / x))), not in() (We include lower bound)

`max()`

call in second search is redundant.`a[j]`

in that equation is always greater than or equal to`a[i]`

If k == 0 then x * (k + (a[i] — 1) / x) can < a[i].

I mean second search, first one is correct. Given that

`x >= 1`

and`k >= 0`

:You are right.

What do odd and even numbers have to do with the dp tranisition ?

If u use i even number of times, mask will not change because even number of x means that you will multiply with a square. If u use i odd number of times, you must change mask, because it wont stay same.

3 rounds in a row we have a task on bin_pow. Coincidence?:D

C can be solved much faster by considering prime factorisation exponents as vector space over and then answer is just 2

^{n - b}- 1 where b is size of basis.What is the principle?

Your idea is great. Could you give more details or code here? Thanks a lot!

I think D can be solved in O(n*logk) if we use Fenwick Tree to keep the number of each letters,where k is the size of the alphabet.It doesn't work better for this problem,but things will be different if k is up to 10^5 or more.

My submission

Can anyone please, tell me the technique to solve problem A in O(n)?

Use prefix sum and 2 pointers.

Thanks :) and Can you please explain, uses of those pointers?

Got that Idea. Thanks again :)

Could you tell me how to Use prefix sum and 2 pointers? Thanks a lot

You can google it "2 pointer algorithm codeforces" :)

Can anyone explain, why in Problem A on the test 8:

The answer is 40? We can take 90 40 50 and 110 70 — 180 and 180, so the answer is 0, isn't it? Or did I misunderstand it?

Because, in the question it is said that you have to take continuous sector

can anyone please tell me about the query which i will present you below.. read it carefully

""""

I solved problem A. by this way... let us consider an example where

now i arrange these pieces in a fashion like this: starting from the +x axis extreme right going anticlockwise through each sector angle and then making the 4 pieces in anticlockwise sense such that the order follows (0)->(1)->(2)->(3)->(0)

now the possible combinations for the 2 continuous sectors can be like this if starting from (0) (i.e first piece) By considering the clockwise format

Note that sector-1 will not contains the all 4 pieces then in that case min diff will be max.(which will not be the ans) similarly if starting pos is (1),(2)or (3) all possible combinations can be obtained But the point here is .. i am just considered the clockwise direction initially and wrote my code and it gets accepted verdict . here is link http://codeforces.com/contest/895/submission/32719630 But now just figure out this thing when i consider the anti-clockwise direction of these cutted pieces the possible permutations for the case when starting done at (0) (i.e 1 piece is) like this :

I am not checking for these cases it might be possible that i get more minimum value here than the previous cases Can plzz anyone tell me why my code gets accepted even though i not checked for anticlockwise direction ... plzz clear this doubt it just sucks me :/

""""

There is more combinations those your solution will check, when the while loop completes its iteration.

Such as,

For clockwise

It will continue till it reaches (1) and these cases are also included in anti-clockwise.

ya i just recognize this thing .. thnks for ur help bro can u otimize my solution or can u tell me the one given in editorial !

Check My Solution

Am I getting this logic right for Problem B?

Is this logic correct? I think I am still getting TLE because I am not using Binary Search. I got a bit lost in the editorial starting at step 3.

In The Problem A Test case no 50. input is: 7 41 38 41 31 22 41 146

There have minimal difference is 6. 41+41+41+38+22=183 146+31=177 So, 183-177=6. But How to ans is 14?

Anyone Explain please!!

Because the numbers you have chosen are not continuous.

THIS IS VERY IMPORTANT !!! I submitted my solution for problem A during the contest and it passed the pretests then I got RTE on test 49 during system test phase, after the contest I resubmitted the exact same code and I got ACCEPTED !!!! submission during contest : http://codeforces.com/contest/895/submission/32683171 submission after the contest : http://codeforces.com/contest/895/submission/32733925 PLEASE nbah CHECK THIS PROBLEM ! THANKS.

For primes greater than 35 the only number that can affect the mask that correspond to that primes is exactly that prime, and those nombers doesn't affect the other bits on the mask. So, the unic solution for each of those numbers is to select en even ammount of them, and for primes <= 35 you can solve using the Editorial approach in

O(70* 2 ^ 11)which is the overall complexity 32702420can you explain the sample test case 3 for problem E?

after 2 moves

[1 1 5 6 10]

[1 1 5 6 10]

the mathematical expectation should be

[2.6 3.6 4.6 5.6 6.6 4.4 5.4 6.4 7.4 8.4]

then [1 1 3 6 9]

the mathematical expectation of left should be 3.6 and the mathematical expectation of right should be 5.9

so the answer of query [2 1 3] should be 2.6+3.6+4.6+5.9-3.6=13.1 why it is 14?

I am afraid that this is incorrect.

E[6:10] after first move = (40-8+3)/5 = 7

E[1] after the first move = (1*0.8 + 8*0.2) = 2.4

E[1] after the second move = (2.4*0.8 + 7*0.2) = 3.32

How to solve A if the segments need not to be continuous ?

Use subset sum dp and check possible sum nearest to 180. If the sum is

S, your answer will be 2|180 -S|.r / x–(l - 1) / x what does this mean?

I am getting TLE in D, because my solution is running in O(n * k * k). I am not able to reduce it to O(n * k). The code given in the editorial is not clear to me. It doesn't look very intuitive. Can someone please help?

Check out my code, or someone else's.

When trying to count the permutations of A less than B, fix the prefix that will be the same for both strings (N ways). Then, the next character of A has to be less than the character of B at that place. So, if you have countA[26], telling you how many of which character you have in A after the prefix, you can in O(k) add, for each character c < B[i], if countA[c] > 0, the number of ways to finish the string, which is just the number of permutations of the letters you have in countA[] (without c).

You can make it so that you only call the fast_pow(x, y) function O(n) times, so the complexity is O(n(k + log mod)).

You can also precompute the required modular inverses in O(n) with some maths knowledge, which leads to a O(nk) solution.

Thanks a lot !! Beautifully explained :)

in problem D's solution,most people use two array fac and ifac,fac[i]=i! ifac[i]=fac[i]^1e9+5.can anyone tell me what's the usage of ifac and why is it right? thanks in advance...

See: https://en.wikipedia.org/wiki/Fermat%27s_little_theorem

thank you, dalao

For people struggling to convert O(n * k * k) solution to O(n * k) , this is a very clear submission that I happened to find. Hope it helps.

Submission

Verdict: wrong answer in test case 13 problem: 895C - Square Subsets submission: 32803738

tried to solve it by recursive dp+bitmask. long long int produces MLE and int produces WA.

would you mind giving me suggestion how to get rid of this situation? manually tested all the small test cases and they are ok.

Your big_mod function and the following two lines can overflow.

long long int p1=((ncr[p]%mod)*(fun(p+1,m^mask[p])%mod))%mod;

long long int p2=((ncr[p]%mod)*(fun(p+1,m)%mod))%mod;

Add 1LL before the multiplication. fix: 32808994

thank u very much, but may i ask u, how did those function cause overfolw? i am not sure about that.

mod = 1000000007

x%mod can be 1000000006;

so x*x larger than 32 bit;

add 1LL in front of it to force it to become a 64 bit integer first.

hope it's clear.

Problem A failed Test 50 7 41 38 41 31 22 41 146 Output 6 Answer 14 Checker Log wrong answer 1st numbers differ — expected: '14', found: '6'

But the right output shouldn' be 6 as the minimum ? A takes 146 + 31 = 177 B takes 41 * 3 +38 + 22 = 183

The elements should be continuous, 146 and 31 are not. Also they can be continuous in circular fashion (i.e 146 is next to 7)

In problem C; I think we can only use the prime number in [1,35],because if the prime number is bigger than 35,it means the number is equal it;So we can ignore them,and the solution will get Accepted(Its time complexity is O(n*cnt(2^(max/2))). Time complexity O(max*cnt(2^(max/2))) It is very quick! Sorry about for my poor English.

Could you give me more details or code about your idea? Thanks a lot

Hi everyone! I ran into a weird bug in my code for problem D. This http://codeforces.com/contest/895/submission/32918069 solution gets accepted and this http://codeforces.com/contest/895/submission/32918020 does not. The only difference between the two is

I REPLACED THE FORMAT OF STRING INPUT FROM, not the other way around, and the corresponding data types from char array to string. Could anyone please help? Thanks in advance :)SCANFTOCINFor some weird reason, gcc decided not to hoist the

`strlen(a)`

call out of the for loop. Since`strlen()`

is linear-time, that particular for loop is quadratic in the length of a.`string::size()`

is O(1) because strings store their length.This is a standard optimization (though, to be honest, you should never rely on it), so I am not sure why gcc failed to do it. Clang does well here.

Problem C. Square Subsets can be done in $$$O(N)$$$, with $$$N$$$ is the constraint in the problem ($$$N <= 1e5$$$) if combine eddy1021's solution above and the editorial solution. Here: 83570186

Can anyone point out the problem in the code 216499815, Why MOD operations are so costly? when I make some changes in the mod operation it passes 216501286