because greed is good.

https://www.youtube.com/watch?v=6bbzwJ0Sx48

sorry bro by mistake vote -ve ho gaya

If you have to do something else, just don't do the contest here instead of whining about it in the comments. There's no contest time that can satisfy everyone in every time zone.

here

https://csacademy.com/lesson/segment_trees/

Here it is

I tried and got MLE on test 51 :(

yes, it can.

The link describes it as "Smallest positive integer k such that n = +-1+-2+-...+-k for some choice of +'s and -'s." What's the relation between this and problem B ?

Try for cases like 2 4 (Ans:3) or 5 14 (Ans:5)

Subscribed :)

42 minutes ?!

Wow! That's really cool. Hoping to get more of them

Can you explain how solve the problem B? I see that you are making some solution based on bits, But I could not get your solution...

input: 1 31 20

output : 5

test this: 1 5 answer is 3 because: 1) 1 6 2) 3 6 3) 6 6

using 2 prefix sum arrays and then using maps

Let us suppose you eat s1 strawberries and b1 blueberries in the left and s2 strawberries and b2 blueberries to the right. If total strawberries is s and b, then we want s — (s1 + s2) = b — (b1 + b2). Or, equivalently, (s — b) — (s1 — b1) = (s2 — b2). So, for given s1 and b1, you need search for minimum steps in the right to make difference equal to the above. You can maintain hashtable to store for every (s2 — b2) the minimum steps to reach it in the right. This will speed up the search...Complexity O(nlogn)

What is wrong in the greedy approach?

Cant I just eat up the jar which is closest to me?

I reversed the problem; find the maximum possible of jars remaining such that the two types are equal in number. It is easy to see that such jars must form a prefix and a suffix of the given array.

I thus separate the array into two halves ($$$A$$$ and $$$B$$$) and reverse the second half. I also treat strawberry as $$$+1$$$ and blueberry as $$$-1$$$. I then iterate through $$$A$$$ collecting prefix sums and storing it in a map (be sure to set $$$M[0] := 0$$$ before), thus for each prefix sum I now know the biggest prefix of $$$A$$$ with that sum.

I then do similarly with $$$B$$$, except this time I treat strawberry as $$$-1$$$ and blueberry as $$$+1$$$, and I look up the prefix sums in the map. If the match exists, I add the two lengths and keep the biggest candidate seen. Finally, I restore the original answer by subtracting the maximum remainder from $$$2n$$$.

Sample: 67283206

Suppose you can build answer for any subtree of the current tree. Answer for subtree is a list of segments. We will say that the last segment in this list is the root.

Then you have a tree, you built answers for every children.
If there are no children, you can return a single segment {0,1}.
Otherwise you do something that is drawn on the picture. Real segments mean a last (root) segment and the area near it means other segments in this subtree.
a, b, c are children of d and a', b', c', d' are other segments in that subtrees. In this picture we build a tree d.
You can see that there are no intersections between the children, but all the children root's are intersected with d.

If you take the biggest (by count of segments in it) child as a base, you can add other children to this child and in total it will take nlogn time.

I tried with binary search but i got Wrong answer on test 2

Actually I managed to do that, you just need to build prefix differences (num2 — num1) & suffix differences, then sort the suffix ones and find a pair where suffix difference = -prefix difference using binary search.

1. Get the absolute difference.
2. Keep increasing the sum and count from 1.
3. If the sum equals the difference print the count. else keep adding to sum till both diff and sum are odd or even.
4. Print count
5. Try in cpp and try to decode the logic.
6. Thank me later! ;) T.c O(1e5)

My answer for B. A and B

Let the numbers be $$$a$$$ and $$$b$$$. After the operations, we end up with another number that is $$$c$$$ where $$$c\ge \max(a, b)$$$. Now the operations are adding $$$1, 2, 3 ...$$$ so after $$$n$$$ operations we have $$$\frac{n\cdot(n+1)}{2}$$$ as total increment in $$$a$$$ and $$$b$$$, distributed among them in some way.

Now this total increment is also equal to $$$c-a + c-b = 2\cdot c -a-b$$$. Thus we have $$$\frac{n\cdot(n+1)}{2} = 2\cdot c-a-b$$$. Increment can also be written as $$$ |a-b|+2(c - \max(a,b))$$$.

From here we get the two required conditions. We loop over $$$n$$$ to get first $$$n$$$ that satisfies:

1. $$$\frac{n(n+1)}{2} \ge |a-b|$$$

2. $$$\frac{n(n+1)}{2} - |a-b|$$$ should be divisible by $$$2$$$

Now since we need increment $$$\frac{n(n+1)}{2} \ge \max(a,b)$$$ so at the max $$$n^2 = 10^9$$$, so the time complexity is $$$\sqrt{\max(a, b)}$$$.

My submission: 67218512

Btw I was watching William Lin's screencast, I have no idea what he has done. People have done it very quickly!

EDIT: Just realised, no need to loop over so many values, since we know $$$\frac{n(n+1)}{2} \ge \max(a, b)$$$. Thanks to @aniervs. That will give constant complexity..

I took 2's as -1 and maintained prefix sum of array from left to center at each position and the same for the right of center.Then I stored first occurence of distinct prefix sum's to the left and right in different tables.Now just iterate over tables and check if an element in left table has a negative counterpart in the right one, if it does, then the gap is one of the possible answers.

That moment when C is easier than B :sad:

Did you cover the case when you eat up no jar from the left side or right side?

I don't think C is possible with bianry search, since (number of jar to use)->(whether the goal is possible) function is not monotonic.

you don't cover the case when you eat no jar from the left or right

You may have missed some corner cases..

Essentially, the problem is this (My solution requires some knowledge about calculus and probability) Given a binomial distribution $$$B(n, \frac{1}{m})$$$, we want $$$E(X^k)$$$.

Consider moment generating function $$$M(t) = E(e^{tX})$$$. Then, k-th moment, which is $$$E(X^k)$$$, can be achieved as $$$\frac{d^k}{dt^k} M(t)$$$ evaluated at $$$t = 0$$$. (one can prove this by taylor expansion)

Also, a mathematical fact — $$$M(t) = (pe^t + 1 - p)^n$$$ for $$$B(n, p)$$$.

Considering all this, try actually computing some derivatives. You can notice some pattern. By this pattern, we can get some $$$k$$$ degree polynomial about $$$n$$$ and $$$p = \frac{1}{m}$$$. The actual computation was quite messy, but the pattern was clearly noticable. The only task left is to implement this function and evaluate with rational numbers as given.

Let's rewrite $$$x^k$$$ as the number of tuples $$$(x_1, x_2, \dots, x_k)$$$ such that $$$1 \le x_i \le n$$$ and for every $$$i$$$, the $$$x_i$$$-th shuffle of the deck resulted in a joker. Then the expected value of $$$x^k$$$ is the expected number of such tuples.

For each tuple, we need to determine the probability that it belongs to the set of tuples. If the number of distinct elements in a tuple is $$$y$$$, then this probability is $$$\frac{1}{m^y}$$$. Then for each $$$y$$$ calculate the number of tuples of size $$$k$$$ with exactly $$$y$$$ distinct elements; this can be done with dynamic programming — let $$$dp_{i, j}$$$ be the number of tuples of size $$$i$$$ with $$$j$$$ distinct elements; during each transition we either add a new element (there are $$$n - j$$$ ways to do it) or add a previously added element (there are $$$j$$$ ways to do it).

See this problem.

Yes, as I wrote in the comment right above your comment, I tried computing some derivatives and could get $$$k$$$ degree polynomial. We start with $$$(pe^t + (1-p))^n$$$, and we differentiate it $$$k$$$ times. Also notice that since we are dealing with $$$t = 0$$$, $$$e^t$$$ term left in the solution will be evaluated to 1.

Note that we only need to find the expected value of $$$X^k$$$, where $$$X$$$ is a binomially distributed random variable with parameter $$$1/m$$$. For binomially distributed random variables, we know that the $$$E[D_r(X)] = \frac{n!}{(n-r)!} \cdot p^r$$$, where $$$D_r(x)$$$ is the falling factorial function with degree $$$r$$$. Also, we know that $$$x^k = \sum_{i=0}^{i=k} S(k, i) D_i(x)$$$, where $$$S(k, i)$$$ is the Stirling number of the second kind. Now the answer can be computed using a dp to compute $$$S(k, i)$$$ and then by taking the expected value of the identity above.

After ends the hacking phase , hope so.

4

1 4

2 5

3 8

6 7

The answer should be NO.

problem C

Imagine two numbers a and b. a=1 and b=5. The difference between both is 4. So we need a summation that is bigger than 4 like 1+2+3 which is equal to 3 steps. lets take the all the summation and add it to B so now the B becomes 11 and the difference is now 10. If you took the 2 from the summation and deleted it from B and added it to A, the difference will become 6 as you subtracted 2 from B and added it to A. do the same for the 3 and now the difference become 0. So overall, it has double the effect. 1+2+3=6 that summation accepts the difference between A and B to be:6,4,2,0. To sum up the idea, the summation result and the difference between A and B should be both either even or odd! I hope this helped!

Whenever you solve a problem(or maybe you fail to) always try to understand the mathematical solution behind it. It will add up to your knowledge and may help you next time. This is a never-ending process, you have to learn something new, every time.

I think that each individual develops their own mathematical intuition for different types of problem and I am sorry to say that there is no shortcut to approach such problems, except one, practicing and up-solving lots and lots of math problems.

1 — Solve codeforces under 1000-dif-math problem This is best way to get a better view of math problems(also all A&B problem)[I had the same problem solving math problems] and how to think better. As you done(became master solving this kind of problems easily), Start solving under 1500-dif and so on.
2 — Study number theory.
3 — Every step in thinking on a problem ask yourself what to do now? this gives your mind a really nice view about the problem.
4 — Don't ignore some dumb ideas on a problem (sometimes this dumb ideas are the solution)
5 — Search for the pattern not for a single testcase you wrote, think more open (for example : in problem B, it was better to write down all the differences that adding 1 to n can make. (I also did this & got Acc on B)
Hope it was helpful.

basic idea is sort the range in increasing order of l. now consider a range at index i {l,r} find all the range that start b/w (l,r) and end after r then there will be intersection b/w segment without completely inside of another.

now how can we do that optimally, maintain a segment tree such that v[i]=range[i].r after sorting. we can find the range of index of segment for which segment start b/w (l,r) using lower_bound. now we can update using segment tree, if max of v[i] is less than r for an interval in segment tree then we won't go into that node, otherwise there can be atleast one segment for which it start b/w (l,r) and end after r.

In worst case there could nc2 edges but we don't need to go beyond n-1 edges. once there are n edges in graph it will no longer remain tree. so we can use dsu to maintain whether we got the cycle or not.

to find a node in segment tree such that there will be intersection b/w segments, its complexity will be O(logn) using segment tree. we need to add atmost n-1 edges so combined complexity will be O(nlogn) and we need to maintain dsu for cycle check that can be O(nlogn) so overall complexity will be O(nlogn) Here is my Submission

Get all the edges until it's less that n :) 67240718

I think so using prefix and suffix sums and jumping pointers.

Instead of using a map to query the nearest index in the right half with required difference in strawberries and blackberries, we can maintain an array with size $$$2n$$$ initialized to -1. This works since difference ranges between $$$-n$$$ and $$$+n$$$. This will run in $$$O(n)$$$.

Well yes, we can surely do that, but is there some general method to find if there exists a subarray whose sum is a given value, in linear time?