Thanks!!

Can you add subtitles. Unable to understand you.

Why don't you make Tutorials of harder problems like F?
I'm not saying that C was easy.

Problem C detailed video explanation: Link

me https://codeforces.net/contest/1355/submission/80328002

I did it and I don't understand why my solution get TLE https://codeforces.net/contest/1355/submission/80314876

Div2 isn't supposed to be friendly with newbies. That's why we have Div3's and now Div4.

C: "Non-degenerate triangles".

CF users:

DURING THE CONTEST WHEN YOU TRIED TO SOLVE TASK C VERY HARD BUT LATER SAW TASK D

it's not a problem it can be some joke, thats trains you to read all problems

Yes.

You have ignored the restriction of $$$x$$$ and $$$y$$$ when calculating $$$useless$$$. $$$x$$$ should be in $$$[A,B]$$$ and $$$y$$$ should be in $$$[B,C]$$$.

Could someone explain the mistake. thanks in advance

i know first was hard to strike the mind

Better to have strong test cases than get hacked afterwards

When $$$X = 2^{29}$$$, your code will return $$$12$$$ but the answer is $$$30$$$ which is not correct. right?

Yes, we have solution that solves problem in 17 queries. But we make bound a bit bigger.

I have a randomised solution here. Can it be hacked or improved ??

Here are the details of my solution:

I ask for all the primes less than (10^9)^(1/4). Which can be packed into 4 queries. Then I ask for the primes found in another 5 queries. Now the remaning part has atmost 3 primes. Let's denote the remaning part as 'Y' and the no. of divisors found so far as "res".

Case 1 : Y = p / p*p / p*p*p / p*q , answer = res*2

Case 2 : Y = p*q*r / p*q*q ,

Here If I manage to find atleast one prime's existence, I can safely answer res*4, otherwise I answer res*2.

Atleast one prime among these will be less than X^(1/3). So for each remaning query, I shuffle the remaining primes from (10^9)^(1/4) to (10^9)^(1/3) and ask the query by taking maximum primes.

hmm

If we assume S<2*N and assume K>0, then we calculate prefix sum array M{ M1, M2, M3,...,Mn}. Now, we are marking all the number that are of the form M1+T*S, M2+T*S, ... , Mn+T*S for all T>=0. An observation is made that if for any integer X, X and X+K is marked, then the array will contain a segment with sum K. This is because if X and X+K is marked then X = Mi + T*S and X+K = Mj + T*S, Mj>=Mi. "T" will not change because K<=S. Now, (X+K)-X = Mj-Mi=K which is the sum of the segment [j...i+1]. hence this segment will contain sum as K. Now we are considering the range [0,..,2*K*S-1]. This contains 2*K*N marked elements because marked elements are M1, M2,..., Mn, M1+S, M2+S,...,Mn+S,....., M1+(2K-1)*S, ...., Mn+(2K-1)*S (Next element M1+2*K*S>2*K*S hence out of range) ----> these are 2*K*N elements.Also all the numbers in the range[0,2KS-1] can be divided in pairs(x,y) such that y-x=K hence (0,K), (1,K+1), (2,K+2), ..., ,(2*K*S-K-1,2*K*S-1). Number of pairs are K*S. Since we are assuming that Petya will lose, so there is no segment whose sum is K, so there is no marked element X for which X+K is marked, So in each pair atmost 1 element will be marked since y-x=K. So number of marked element in the range [0,2KS-1] are less than or equal to KS (number of pairs). But number of marked elements in the range[0,2KS] are 2*K*N. Hence 2*K*N<K*S ---> 2N<S But initially we assumed that S<2*N which is a contradiction.

Here's another way to look at the proof of D:

Let's look at the prefix sums modulo $$$S$$$. There are $$$N$$$ different prefix sums: $$$M_1, M_2, \ldots,M_N=0(mod\;S)$$$. They are distinct because elements of the array are positive.

Now, for a given $$$K >0$$$, look at the $$$N$$$ numbers $$$M_1+K, M_2+K,\ldots,M_N+K\,(mod\;S)$$$. These again are distinct among themselves.

Now you have a total of $$$2N$$$ numbers in $$$[0,S-1]$$$, and since $$$2N > S$$$, two of them must be equal. So we have some $$$1\leq i\neq j \leq N$$$ such that $$$M_i + K = M_j\,(mod\;S)$$$. If $$$i \lt j$$$, then the segment $$$[i+1,j]$$$ sums to $$$K$$$, otherwise if $$$i \gt j$$$ then the segment $$$[i+1,j]$$$ (of the cyclic array) sums to $$$K$$$

i would say B and D.

I got the solution for A in 3 minutes, but spent 30 minutes trying to convince myself i was right, but i couldn't, then i tried to submit it anyway.

it worked, awesome

Can you explain your approach?

what about this #include <bits/stdc++.h> instead of that many?

There is a similar one with nicer code formatting. Can somebody explain how it works? Thanks!

Yeah, it will be really great to increase the frequency of Div1 contests. I haven't participated any rated Div1 in about one month.

I'm NOT

Explanation of prefix sum approach

Alternative approach

not really, c++ also TLE, though i think it is O(n) my submission

yeahh... we all know that dude

I also didn't waste time in proving. Just run the cost function from 1 to 100 for various arrays.

could you explain proof ?

The (intermediate) goal is to calculate the number of (x, y) pairs such that x + y = s for each possible sum s. (It is convenient to keep this counts in a frequency vector indexed by values of s.) For that we can iterate over valid values of x, i.e. from A to B and for each value of x iterate over valid values of y, i.e. from B to C. That enumerates all (x, y) pairs and for each such pair we can add 1 to the count of pairs with sum x+y, thus obtaining the total count of pairs per possible sum value in the end. This has a bad complexity and should be optimized.

Note that for a given value of x, while iterating over y values, we add 1 to frequencies of all sums in the contiguous interval from x + B to x + C. Think of the desired frequency vector as a prefix array, which we will calculate later. And for now let us compute the vector whose prefix sums we are going to calculate to obtain it. To increase an interval in the prefix vector by 1, increase the element at the beginning of the same interval (index x + B), but in the original array, by 1 and decrease the element past the end of the interval (index x + C + 1), also in the original array, by 1. Iterate over values of x and do the same constant time operation just described (+1/-1) for each x. At the end compute the prefix sums vector to obtain the desired frequencies of the sums s.

After calculating frequencies of x+y sums, the z variable comes into play. For the triangle to exist and not be degenerate, x + y > z must be satisfied. (x + z > y and y + z > x are already satisfied due to the increasing order restriction from the condition.)

Now we can either iterate over values of s=x+y and calculate how many z values from the interval C to D are smaller than the given value of s and add the count to the answer. Or we can iterate over values of z from C to D like in the editorial and calculate the number of (x, y) pairs that satisfy x+y > z for the given z, again adding up all counts. To be able to get the number of (x, y) pairs with sum exceeding z in constant time, the second prefix sum calculation mentioned in the editorial is required.

My Explanation

Explanation of prefix sum approach

Alternative approach

I think comparing C and D isn't logical. D is more about thinking and proving the case and it is easy to code. While C has completely different story!!

When I read problem A, I looked at contest name if it was div1 contest!

Read about time complexity. Your code is O(K) and K can go upto 10^18. Hence this TLEs.

My Explanation

Not sure what specific kind of solution you mean, but the implementation of this approach can be done in one loop.

How come it is working? About 3*10^7 runs in 1s, then shouldn't it be TLE?. Please correct me if I am wrong.

Because, you can rewrite some sums.

Let $$$H$$$ = $$$\dfrac{\sum\limits_{i=1}^N h_i}{N}$$$.

So we know, that $$$\sum\limits_{i=1}^N h_i - H=\sum\limits_{i=1}^N h_i - N * \dfrac{\sum\limits_{i=1}^N h_i}{N} =0$$$. By the defenition, $$$P = \sum\limits_{i \in X}H - h_i,$$$ $$$Q = \sum\limits_{i \in Y}h_i - H$$$, where is $$$X$$$ is the set of indexes $$$i, h_i \leq H$$$, and set $$$Y$$$ is the set of indexes $$$i, h_i > H$$$.

$$$\sum\limits_{i=1}^N h_i - H = Q - P = 0 \Rightarrow Q=P$$$

i did it as follows: if u need length n try to fill the array with ones except for the last position for example if n = 5 and sum = 10 the the array will be 1 1 1 1 6 at this case if k = 5 then u win then u need k to be more than the sum of ones and less than the last number. let the last number t, t = S — (n — 1) = S — n + 1 then t — (n — 1) >= 2 S — n + 1 — (n — 1) >= 2; S — 2n + 2 >= 2 S — 2n >= 0 then S >= 2n hope it helps

I did using presums but this method seem simpler. Can you explain the two lines in the for loop, I mean how you count for a particular value of $$$z$$$

Let's start with the inequality x + y > z itself. If we find the number of solutions of the equation x + y <= z, then we can get the answer by subtracting it from total combinations of x and y i.e. (B - A + 1)*(C - B + 1).

We know how to find the number of non-negative integral solutions of the equations of the kind a₁ + a₂ + ... + a_r = n. So to reduce our inequality to get an equation like above, we need to get rid of the <= symbol by adding a dummy variable d. Now we have the equation x + y + d = z. But there is still a problem. Variables x and y can not be non-negative. To achieve this, we replace x with X + A and y with Y + B.

Now our equation looks like this X + Y + d = z - A - B. So the number of solutions for this equation(without taking into account the upper limits of X and Y) is $$$\binom{z - A - B + 3 - 1}{3 - 1}$$$. Now to remove the solution where x >= B + 1 or X + A >= B + 1, we can replace X with (B — A + 1 + dx) to get the equality dx + Y + d = z - 2*B - 1. It has $$$\binom{z - 2*B - 1 + 3 - 1}{3 - 1}$$$ solutions. Do the same for Y. Thus total number of solutions for a given z becomes: (B — A + 1)*(C — B + 1) — ($$$\binom{z - A - B + 3 - 1}{3 - 1}$$$ — $$$\binom{z - 2*B - 1 + 3 - 1}{3 - 1}$$$ — $$$\binom{z - A - C - 1 + 3 - 1}{3 - 1})$$$. Hope it helps:)

Just replace input() with sys.stdin.readline() (import sys before obviously). Input() is too slow, need to read number(s) faster.

Same concept in C++ will be an AC

actually it's kind of optimized ternary search.link