### NBAH's blog

By NBAH, history, 11 months ago, translation, ,

## 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(n2) or O(n).

Solution

## 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)).

Solution

## 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 f1[i], f0[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] * f0[i + 1]

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.

Solution

## 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 * k2), 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.

Solution

## 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 [l1, r1] remains on its place with probability (r1 - l1) / (r1 - l1 + 1). The probability that it will be replaced by a number from [l2, r2] is 1 / (r1 - l1 + 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 [l2, r2], let it be x. Then, to update the expectation of a number from [l1, r1], we need to multiply it by (r1 - l1) / (r1 - l1 + 1) and add x / (r1 - l1 + 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))

Solution

•
• +91
•

 » 11 months ago, # | ← Rev. 2 →   0 Nice :) It was good problems!
 » 11 months ago, # |   +33 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.
•  » » 11 months ago, # ^ |   +55 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.
•  » » 11 months ago, # ^ |   0 Can you explain the meet in the middle soluton?
•  » » » 11 months ago, # ^ |   +8 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.
•  » » 11 months ago, # ^ |   0 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.
•  » » » 11 months ago, # ^ |   +1 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).
•  » » » » 11 months ago, # ^ |   0 Oh! Silly me. Thanks. :)
 » 11 months ago, # |   +8 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 the dp[i][j] it uses.
•  » » 11 months ago, # ^ | ← Rev. 3 →   +2 Lol f1[i] is the number of ways to choose an odd number of numbers out of a set of a[i] numbers, and f0[i] is the number of ways to choose an even number of numbers out of a set of a[i] numbers.It ends up being:f1[i] = 0 if a[i] = 0 and f1[i] = 2a[i] - 1 otherwise.f0[i] = 1 if a[i] = 0 and f0[i] = 2a[i] - 1 otherwise.Basically know that for k ≥ 1, the number of ways to choose an odd number of elements out of a set of k elements is equal to the number of ways to choose an even number of elements out of a set of k elements, and they are both equal 2k - 1. Here is a proof.
•  » » » 11 months ago, # ^ | ← Rev. 2 →   0 OK, but what does this have to do with the rest of the problem? Why is this being computed in the first place?
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   +4 Because the mask j becomes if you take an odd number of x but stays as j if you take an even number of x.
•  » » » » » 11 months ago, # ^ |   0 What do you mean by odd number of x ?
•  » » » » 11 months ago, # ^ |   0 vb7401, did you get it? Because, I didn't.
•  » » » » » 11 months ago, # ^ |   0 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.
•  » » » 11 months ago, # ^ |   0 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)
•  » » » » 11 months ago, # ^ |   0 Yeah you are right, what a[i] means in my comment above is the number of times i appears in the input.
•  » » 11 months ago, # ^ | ← Rev. 5 →   +4 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 105 to 70.
•  » » » 11 months ago, # ^ |   0 can anyone explain the 2nd problem?
 » 11 months ago, # |   0 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
•  » » 11 months ago, # ^ |   0 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!
•  » » » 11 months ago, # ^ | ← Rev. 3 →   0 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 anywayEDIT: Actually, precalculating powers of two up to n gives ac in first submission.
 » 11 months ago, # |   +11 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".
 » 11 months ago, # |   +19 C can be solved in a more (maybe) straightforward way.Let dp[i][mask] be the number of way to choose some subset of first i elements and their product has j-th prime with odd degree(if j-th bit of mask is 1). Directly implementing this solution results in a O(N × 219) 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 as dp[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 of dp[mask][0]. Then, considering all the number whose prime divisor contains 13, and so on.The time complexity is O(N × 25). 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).
•  » » 11 months ago, # ^ |   0 That idea make me remember this problem.https://community.topcoder.com/stat?c=problem_statement&pm=12074
 » 11 months ago, # |   +76 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.
•  » » 11 months ago, # ^ |   0 You mean the number of solutions of this system of equations gives the answer, right?! How do you find it?
•  » » » 11 months ago, # ^ |   0 If M is the matrix whose i-th column is xi, then (1+) the answer is the cardinal of the kernel of M, which is (rank-nullity theorem). The rank can be computed using Gaussian elimination in .
 » 11 months ago, # |   0 Can B be solved using two pointers. If so, then how?
•  » » 11 months ago, # ^ |   0 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
•  » » 11 months ago, # ^ |   0
 » 11 months ago, # |   0 I still don't get C. :-(
 » 11 months ago, # |   0 How to slove B?
•  » » 11 months ago, # ^ |   0 Read this solution. Ask me, what you don't understand.Div 2B Solution
•  » » » 11 months ago, # ^ |   0 Why order? this is a continuous interval and ((a[i] — 1) / x) what does it mean？
•  » » » » 11 months ago, # ^ |   +1 Why order? We have sorted the array, so we have an increasing function => the interval is continuous. (a[i] — 1) / x what does it mean？ 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.
•  » » » » » 11 months ago, # ^ |   0 Thank you! You are sooooooo cute~
•  » » 11 months ago, # ^ | ← Rev. 3 →   0 My solution with only binsearch http://codeforces.com/contest/895/submission/32701257
•  » » » 11 months ago, # ^ |   0 Could you further explain this answer to me? What's the reasoning behind: vector::iterator l = lower_bound(a.begin(), a.end(), max((long long)a[i], (long long)x * (k + (a[i] - 1) / x))); vector::iterator r = lower_bound(a.begin(), a.end(), max((long long)a[i], (long long)x * (k + 1 + (a[i] - 1) / x))); Also, why do you use lower_bound? Why not upper_bound?
•  » » » » 11 months ago, # ^ |   0 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)
•  » » » 11 months ago, # ^ |   0 max() call in second search is redundant. a[j] in that equation is always greater than or equal to a[i]
•  » » » » 11 months ago, # ^ |   0 If k == 0 then x * (k + (a[i] — 1) / x) can < a[i].
•  » » » » » 11 months ago, # ^ | ← Rev. 3 →   0 I mean second search, first one is correct. Given that x >= 1 and k >= 0: x * (k + 1 + (a[i] - 1) / x) >= x + x * ((a[i] - 1)/x) >= x + (a[i] - 1 - (a[i] - 1)%x) = a[i] - ((a[i] - 1)%x + 1) + x >= a[i] 
•  » » » » » » 11 months ago, # ^ |   0 You are right.
 » 11 months ago, # |   0 What do odd and even numbers have to do with the dp tranisition ?
•  » » 11 months ago, # ^ |   0 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.
 » 11 months ago, # |   0 3 rounds in a row we have a task on bin_pow. Coincidence?:D
 » 11 months ago, # | ← Rev. 2 →   +4 C can be solved much faster by considering prime factorisation exponents as vector space over and then answer is just 2n - b - 1 where b is size of basis.
•  » » 11 months ago, # ^ |   0 http://codeforces.com/contest/895/submission/32697113 Is this what you are referring to?
•  » » 11 months ago, # ^ |   0 What is the principle?
•  » » 10 months ago, # ^ |   0 Your idea is great. Could you give more details or code here? Thanks a lot!
 » 11 months ago, # |   0 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
 » 11 months ago, # |   0 Can anyone please, tell me the technique to solve problem A in O(n)?
•  » » 11 months ago, # ^ |   0 Use prefix sum and 2 pointers.
•  » » » 11 months ago, # ^ |   0 Thanks :) and Can you please explain, uses of those pointers?
•  » » » 11 months ago, # ^ |   0 Got that Idea. Thanks again :)
•  » » » » 11 months ago, # ^ |   0 can you please explain me the the problem A? what is a continuous sector? thanks in advance...
•  » » » » » 11 months ago, # ^ |   0 it means one cake should be consist of a[i],a[i+1]....a[j-1],a[j] or a[i],a[i+1]...a[n],a[1],a[2]...a[j]
•  » » » » 10 months ago, # ^ |   0 Could you tell me how to Use prefix sum and 2 pointers? Thanks a lot
•  » » » » » 10 months ago, # ^ |   0 You can google it "2 pointer algorithm codeforces" :)
 » 11 months ago, # |   0 Can anyone explain, why in Problem A on the test 8: 5 110 90 70 50 40 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?
•  » » 11 months ago, # ^ |   0 Test 8 picture
•  » » 11 months ago, # ^ |   0 Because, in the question it is said that you have to take continuous sector
•  » » » 11 months ago, # ^ |   0 Ahhh, I see. Thanks :)
 » 11 months ago, # | ← Rev. 2 →   0 b
 » 11 months ago, # |   0 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 INPUT: 4 170 30 150 10 (0) (1) (2) (3) here i numbered these pieces with the indices of this sector array representing the sector angle for each individual piece, (in to which the pizza was cut) . 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  sector-1 sector-2 (0) (3) (2) (1) stick to the clockwise format only (0) (3) (2) (1) (0) (3) (2) (1) 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 :  sector-1 sector-2 (0) (1) (2) (3) same case just ignore as above mentioned (0) (1) (2) (3) (0) (1) (2) (3) 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 :/""""
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 As I understood, and as I finally get "Full solution": For exmaple, we have 3 110 80 170 (Answer 20) We should take different variants of pieces: 110 110 80 110 80 170 80 80 170 170 And for each variant, we calculate sum and compare with the minimum: if (min < sum-(360-sum)) min = sum-(360-sum)Tried to explain my solution on my bad english :D
•  » » » 11 months ago, # ^ |   0 Maybe it isn't a good idea, but i can't see editorial for this problems :( Screenshot
•  » » » » 11 months ago, # ^ |   0 yes
•  » » 11 months ago, # ^ |   0 There is more combinations those your solution will check, when the while loop completes its iteration.Such as,For clockwise (3) (2) (1) (0) (3) (2) (1) (0) (3) (2) (1) (0) It will continue till it reaches (1) and these cases are also included in anti-clockwise.
•  » » » 11 months ago, # ^ |   0 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 !
•  » » » » 11 months ago, # ^ |   0 Check My Solution
 » 11 months ago, # |   +3 Am I getting this logic right for Problem B? Realize that we can find the numbers divisible by x in [l, r] by using the formula r/x — (l — 1)/x. Its (l — 1) to prevent an off by one error when l % x == 0. Sort the array (in ascending order). Iterate through the array and take a[i] to be the left bound. Since we are given a left bound we can find the lowest and highest indices that still satisfy the eq given in step 1. (use binary search at this step?) Knowing the indices we can calculate the actual number of valid right bounds for every left bound and we have our answer. 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.
 » 11 months ago, # |   0 For the problem B,Let us suppose an additional constrain is added that we can only consider pairs such that i <=j So in addition to a[i] <= a[j] , i <=j . Then the problem can be solved with a BST yes?
 » 11 months ago, # |   0 In The Problem A Test case no 50. input is: 7 41 38 41 31 22 41 146There 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!!
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 Because the numbers you have chosen are not continuous.
•  » » » 11 months ago, # ^ |   0 Thanks
 » 11 months ago, # |   -18 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.
 » 11 months ago, # | ← Rev. 2 →   0 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 32702420
 » 11 months ago, # | ← Rev. 2 →   0 can 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.9so 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?
•  » » 11 months ago, # ^ |   0 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] I am afraid that this is incorrect.E[6:10] after first move = (40-8+3)/5 = 7E[1] after the first move = (1*0.8 + 8*0.2) = 2.4E[1] after the second move = (2.4*0.8 + 7*0.2) = 3.32
 » 11 months ago, # |   0 How to solve A if the segments need not to be continuous ?
•  » » 11 months ago, # ^ |   0 Use subset sum dp and check possible sum nearest to 180. If the sum is S, your answer will be 2|180 - S|.
 » 11 months ago, # |   0 r / x–(l - 1) / x what does this mean?
 » 11 months ago, # |   0 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?
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 11 months ago, # ^ |   +5 Thanks a lot !! Beautifully explained :)
 » 11 months ago, # | ← Rev. 2 →   0 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...
•  » » 11 months ago, # ^ |   0
•  » » » 11 months ago, # ^ |   0 thank you, dalao
 » 11 months ago, # |   0 can anyone explain me hoe to solve C(square subsets) please!!
 » 11 months ago, # |   +1 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
 » 11 months ago, # | ← Rev. 3 →   0 Verdict: wrong answer in test case 13 problem: 895C - Square Subsets submission: 32803738tried 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.
•  » » 11 months ago, # ^ | ← Rev. 3 →   0 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
•  » » » 11 months ago, # ^ |   0 thank u very much, but may i ask u, how did those function cause overfolw? i am not sure about that.
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » 11 months ago, # ^ |   0 understood. thank u :)
 » 11 months ago, # | ← Rev. 2 →   0 I have find my error now....
 » 11 months ago, # |   0 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
•  » » 11 months ago, # ^ |   0 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)
•  » » » 11 months ago, # ^ |   0 Got it. Thanks
 » 11 months ago, # |   0 would anyone mind explaining solution of problem D with more details?I read the tutorial and some solutions several times, but still i don't get it :( may be it requires some algorithm or data structure i need to learn.any suggestion?
 » 11 months ago, # |   +3 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.
•  » » 10 months ago, # ^ |   0 Could you give me more details or code about your idea? Thanks a lot
 » 11 months ago, # |   0 I was struggling for two days now in order to understand problem C solution. Is there any prior knowledge (prior problem) that is needed to understand the solution easily ? The explanations given so far are not clear to me. Could somebody give a simple example with only 3 or 4 elements instead of 70 ?Thanks
•  » » 11 months ago, # ^ |   0 are you familiar with bitmask dp? if not then first u need to learn it. bitmask dpthen the rest is based on some mathematical facts. you can read it from here
 » 11 months ago, # | ← Rev. 2 →   0 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 SCANF TO CIN, not the other way around, and the corresponding data types from char array to string. Could anyone please help? Thanks in advance :)
•  » » 10 months ago, # ^ | ← Rev. 3 →   +3 For 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.
 » 10 months ago, # | ← Rev. 2 →   0 In problem A In test 50 where the input is 741 38 41 31 22 41 146the output is 14 can anyone explain to me why the answer is not 6if we took one sector the pieces 146 + 31 = 177 and the other sector will be 183 the result should be 6 so why is this wrong and 14 correct ?Thanks in advance
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 We have to choose numbers continuously in cyclic form. 146 and 31 are not together
 » 9 months ago, # | ← Rev. 2 →   0 In Problem DIV2/C (895C)"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"what do you mean by "Number of ways we can take odd and even amount of it from a."UDP: I got it.