Idea: BledDest

**Tutorial**

**Solution 1 (BledDest)**

```
t = int(input())
for i in range(t):
n, m, k = map(int, input().split())
d = n // k
a1 = min(m, d)
a2 = (m - a1 + k - 2) // (k - 1)
print(a1 - a2)
```

**Solution 2 (BledDest)**

```
t = int(input())
for i in range(t):
n, m, k = map(int, input().split())
ans = 0
d = n // k
for a1 in range(m + 1):
for a2 in range(a1 + 1):
if(a1 > d):
continue
if(a1 + a2 > m):
continue
if(a1 + (k - 1) * a2 < m):
continue
ans = max(ans, a1 - a2)
print(ans)
```

Idea: BledDest

**Tutorial**

**Solution (pikmike)**

```
t = int(input())
for _ in range(t):
n, m, x, y = map(int, input().split())
ans = 0
y = min(y, 2 * x)
for __ in range(n):
s = input()
i = 0
while i < m:
if s[i] == '*':
i += 1
continue
j = i
while j + 1 < m and s[j + 1] == '.':
j += 1
l = j - i + 1
ans += l % 2 * x + l // 2 * y
i = j + 1
print(ans)
```

Idea: adedalic

**Tutorial**

So there are two kinds of stops to consider: $$$k$$$ hot and $$$k$$$ cold cup and $$$(k + 1)$$$ hot and $$$k$$$ cold cups.

The first case is trivial: the temperature is always $$$\frac{h + c}{2}$$$. In the second case the temperature is always strictly greater than $$$\frac{h + c}{2}$$$. Thus, if $$$t \le \frac{h + c}{2}$$$, then the answer is $$$2$$$.

Let's show that otherwise the answer is always achieved through the second case.

The temperature after $$$(k + 1)$$$ hot cups and $$$k$$$ cold cups is $$$t_k = \frac{(k + 1) \cdot h + k \cdot c}{2k + 1}$$$. The claim is that $$$t_0 > t_1 > \dots$$$. Let's prove that by induction.

**Proof 1**

$$$t_0 = h, t_1 = \frac{2 \cdot h + c}{3}$$$. $$$c < h$$$, thus $$$t_0 > t_1$$$.

Now compare $$$t_k$$$ and $$$t_{k+1}$$$.

We can also show that this series converges to $$$\frac{h + c}{2}$$$:

**Proof 2**

I'm sorry that I'm not proficient with any calculus but my intuition says that it's enough to show that $$$\forall k~t_k > \frac{h + c}{2}$$$ and $$$\forall \varepsilon \exists k~t_k < \frac{h + c}{2}$$$ with $$$k \ge 0$$$.

So the first part is:

And the second part is:

So that claim makes us see that for any $$$t$$$ greater than $$$\frac{h + c}{2}$$$ the answer is always achieved from the second case.

That allows us to find such $$$k$$$, that the value of $$$t_k$$$ is exactly $$$t$$$. However, such $$$k$$$ might not be integer. $$$\frac{(k + 1) \cdot h + k \cdot c}{2k + 1} = t \leftrightarrow$$$ $$$\frac{k \cdot (h + c) + h}{2k + 1} = t \leftrightarrow$$$ $$$k \cdot (h + c) + h = 2kt + t \leftrightarrow$$$ $$$k \cdot (h + c - 2t) = t - h \leftrightarrow$$$ $$$k = \frac{t - h}{h + c - 2t}$$$.

The only thing left is to compare which side is better to round $$$k$$$ to. It seems some implementations with float numbers might fail due to precision errors. However, it's possible to do these calculations completely in integers.

Let's actually rewrite that so that the denominator is always positive $$$k = \frac{h - t}{2t - h - c}$$$. Now we can round this value down and compare $$$k$$$ and $$$k + 1$$$.

So the optimal value is $$$k$$$ if $$$|\frac{k \cdot (h + c) + h}{2k + 1} - t| \le |\frac{(k + 1) \cdot (h + c) + h}{2k + 3} - t|$$$. So $$$|(k \cdot (h + c) + h) - t \cdot (2k + 1)| \cdot (2k + 3) \le |((k + 1) \cdot (h + c) + h) - t \cdot (2k + 3)| \cdot (2k + 1)$$$. Otherwise, the answer is $$$k + 1$$$.

You can also find the optimal $$$k$$$ with binary search but the formulas are exactly the same and you have to rely on monotonosity as well. Also, these formulas can get you the better understanding for the upper bound of the answer.

Overall complexity: $$$O(1)$$$ or $$$O(\log h)$$$ per testcase.

**Solution (pikmike)**

```
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
int tc;
scanf("%d", &tc);
forn(_, tc){
int h, c, t;
scanf("%d%d%d", &h, &c, &t);
if (h + c - 2 * t >= 0)
puts("2");
else{
int a = h - t;
int b = 2 * t - c - h;
int k = 2 * (a / b) + 1;
long long val1 = abs(k / 2 * 1ll * c + (k + 1) / 2 * 1ll * h - t * 1ll * k);
long long val2 = abs((k + 2) / 2 * 1ll * c + (k + 3) / 2 * 1ll * h - t * 1ll * (k + 2));
printf("%d\n", val1 * (k + 2) <= val2 * k ? k : k + 2);
}
}
return 0;
}
```

1359D - Yet Another Yet Another Task

Idea: BledDest

**Tutorial**

**Solution (pikmike)**

```
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int INF = 1e9;
int main() {
int n;
scanf("%d", &n);
vector<int> a(n);
forn(i, n) scanf("%d", &a[i]);
long long ans = 0;
forn(mx, 31){
long long cur = 0;
long long best = 0;
forn(i, n){
int val = (a[i] > mx ? -INF : a[i]);
cur += val;
best = min(best, cur);
ans = max(ans, (cur - best) - mx);
}
}
printf("%lld\n", ans);
return 0;
}
```

Idea: BledDest

**Tutorial**

**Solution (BledDest)**

```
#include<bits/stdc++.h>
using namespace std;
const int N = 500043;
const int MOD = 998244353;
int fact[N];
int add(int x, int y)
{
x += y;
while(x >= MOD) x -= MOD;
while(x < 0) x += MOD;
return x;
}
int mul(int x, int y)
{
return (x * 1ll * y) % MOD;
}
int binpow(int x, int y)
{
int z = 1;
while(y > 0)
{
if(y % 2 == 1)
z = mul(z, x);
x = mul(x, x);
y /= 2;
}
return z;
}
int inv(int x)
{
return binpow(x, MOD - 2);
}
int divide(int x, int y)
{
return mul(x, inv(y));
}
void precalc()
{
fact[0] = 1;
for(int i = 1; i < N; i++)
fact[i] = mul(i, fact[i - 1]);
}
int C(int n, int k)
{
if(k > n) return 0;
return divide(fact[n], mul(fact[n - k], fact[k]));
}
int main()
{
int n, k;
cin >> n >> k;
int ans = 0;
precalc();
for(int i = 1; i <= n; i++)
{
int d = n / i;
ans = add(ans, C(d - 1, k - 1));
}
cout << ans << endl;
}
```

Idea: BledDest

**Tutorial**

**Solution (pikmike)**

```
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define x first
#define y second
using namespace std;
const double INF = 1e13;
struct line{
int A, B, C;
line(){}
line(int x1, int y1, int x2, int y2){
A = y1 - y2;
B = x2 - x1;
C = -A * x1 - B * y1;
// A is guaranteed to be non-zero
if (A < 0) A = -A, B = -B, C = -C;
int g = __gcd(A, __gcd(abs(B), abs(C)));
A /= g, B /= g, C /= g;
}
};
bool operator ==(const line &a, const line &b){
return a.A == b.A && a.B == b.B && a.C == b.C;
}
double x;
bool operator <(const line &a, const line &b){
double val1 = (-a.A * x - a.C) / a.B;
double val2 = (-b.A * x - b.C) / b.B;
return val1 < val2;
}
struct car{
int x, y, dx, dy, s;
line l;
double vx, vy;
};
int n;
vector<car> a(n);
long long det(int a, int b, int c, int d){
return a * 1ll * d - b * 1ll * c;
}
bool inter(const line &a, const line &b, long long &D, long long &Dx, long long &Dy){
D = det(a.A, a.B, b.A, b.B);
if (D == 0) return false;
Dx = -det(a.C, a.B, b.C, b.B);
Dy = -det(a.A, a.C, b.A, b.C);
return true;
}
int sg(int x){
return x < 0 ? -1 : 1;
}
int sg(long long a, long long b, int c){
// sign of a/b-c
if (b < 0) a = -a, b = -b;
return a - c * b < 0 ? -1 : (a - c * b > 0);
}
bool inter(int i, int j, double &len){
if (i == -1 || j == -1)
return false;
long long D, Dx, Dy;
if (!inter(a[i].l, a[j].l, D, Dx, Dy))
return false;
if (sg(Dx, D, a[i].x) != 0 && sg(a[i].dx) != sg(Dx, D, a[i].x))
return false;
if (sg(Dx, D, a[j].x) != 0 && sg(a[j].dx) != sg(Dx, D, a[j].x))
return false;
double x = Dx / double(D);
double y = Dy / double(D);
double di = (a[i].x - x) * (a[i].x - x) + (a[i].y - y) * (a[i].y - y);
double dj = (a[j].x - x) * (a[j].x - x) + (a[j].y - y) * (a[j].y - y);
return len * len >= di / a[i].s && len * len >= dj / a[j].s;
}
vector<set<pair<line, int>>::iterator> del;
set<pair<line, int>> q;
void get_neighbours(int i, int &l, int &r){
l = r = -1;
auto it = q.lower_bound({a[i].l, -1});
if (it != q.end())
r = it->y;
if (!q.empty() && it != q.begin()){
--it;
l = it->y;
}
}
bool check(double t){
vector<pair<double, pair<int, int>>> cur;
del.resize(n);
forn(i, n){
double x1 = a[i].x;
double x2 = a[i].x + a[i].vx * t;
if (x1 > x2) swap(x1, x2);
cur.push_back({x1, {i, 0}});
cur.push_back({x2, {i, 1}});
}
q.clear();
sort(cur.begin(), cur.end());
for (auto &qr : cur){
x = qr.x;
int i = qr.y.x;
int l, r;
if (qr.y.y == 0){
get_neighbours(i, l, r);
if (r != -1 && a[i].l == a[r].l)
return true;
if (inter(i, l, t))
return true;
if (inter(i, r, t))
return true;
del[i] = q.insert({a[i].l, i}).x;
}
else{
q.erase(del[i]);
get_neighbours(i, l, r);
if (inter(l, r, t))
return true;
}
}
return false;
}
int main() {
scanf("%d", &n);
a.resize(n);
forn(i, n){
scanf("%d%d%d%d%d", &a[i].x, &a[i].y, &a[i].dx, &a[i].dy, &a[i].s);
a[i].l = line(a[i].x, a[i].y, a[i].x + a[i].dx, a[i].y + a[i].dy);
double d = sqrt(a[i].dx * a[i].dx + a[i].dy * a[i].dy);
a[i].vx = a[i].dx / d * a[i].s;
a[i].vy = a[i].dy / d * a[i].s;
a[i].s *= a[i].s;
}
double l = 0, r = INF;
bool ok = false;
forn(_, 100){
double m = (l + r) / 2;
if (check(m)){
ok = true;
r = m;
}
else{
l = m;
}
}
if (!ok)
puts("No show :(");
else
printf("%.15lf\n", l);
return 0;
}
```

How to solve problem D if the value of the array is much bigger ?

Refer this thread.

You can precompute for each element of the array, the segment that he is the maximum element, this can be done with a stack, finding the rightmost element which is greater than ai and its from 1 to i-1 for each i and then do the dame for the right, then in this interval, for each you need to find the smallest prefix sum un the range from ci to i (here ci is the rightmost element in the left which is greater than ai) and the maximum prefix sum from i to di (here di is the leftmost element in the right which is greater than ai), and the optimal range which its maximum is ai will be this range, the maximum and minimum prefix sums can be computed with segment tree in nlogn. Sorry for my poor english.

can you please tell , how to use stack to find rightmost element greater than $$$a_i$$$ ?

here's an implementation for problem D using this approach: 81753071

Can you tell me that isnt the answer maximum contiguous subset sum — maximum element in that subset ?

I did till finding the max and element at both sides but I couldn't find maximum prefix sum. I was wondering if there is anything better to find prefix sums. And then I came across your comment about segment trees. This is so awesome. Now I know what segment trees can do. Just learning them without any need would be boring. Now I have a need. Thanks Man

EUREKA!!!! I solved it after learning Segment trees. So Damn happy !!!! EDIT: Link to my Solution

Well, maybe I can try. Let's fix an index i. We need find the minimum left index L and maximum right index R such that left maximum number in the range [L, R] be a[i]. How can we do this? Use binary search on index with range maximum query. Complexity for this would be O(n (log n)^2).

Then, at the particular index l in [L, i] and r in [i, R], such that the ans for the fixed i be maximum. Now, notice the following observation. l would be the index in [L, i] such that suffix sum till index l is maximum. Similarly, r would be in the range [i, R] such that prefix sum till r be the maximum. Now, we have to do range maximum query on prefix sum and suffix sum. Simple. Use segment tree once again. Complexity would be O(n log n).

Now, after we find the index l and r, now construct the ans. ans would be suff[l] — suff[i] + pref[r] — pref[i], it's easy to find out. So, it's given on yourself.

Now, we would do this for every i from 1 to n and update the answer.

Yeah bro, that's it. Final complexity is O(n (log n)^2).

Hello, can you please explain your comment line:: "We need find the minimum left index L and maximum right index R such that left maximum number in the range [L, R] be a[i]. How can we do this? Use binary search on index with range maximum query."

How to find these L and R? A better elaboration would be helpful.

And your solution link would be a great help!!

Thanks in Advance!

I calculated prefix sum as well as suffix sum. Since array was immutable, so I created sparse table for array,prefix array and suffix array.

Then for each Index i, find the maximum subarray range that can be formed by applying binary search on sparse table of given array. After that find the maximum suffix sum in left part and maximum prefix sum in right side of that index. If the sum are positive add them.

Here is my solution for the above approach Solution

Let's find for some position "pos" L, R that in the interval from L to R the value in position pos is the largest, then you just need to find the maximum from pos to R and the minimum from L to pos. Now the answer can be MAX (pos, R) — MIN (L, pos) — a [pos], and therefore we iterate over all positions and perform these operations at each position

Давай найдем для какой то позиции "pos" L, R, что в интервале от L до R значение в позиции pos является наибольшим, тогда вам просто нужно найти максимум от pos до R и минимум от L до pos. Теперь ответ может быть MAX (pos, R) — MIN (L, pos) — a [pos], и поэтому мы перебираем все позиции и выполняем эти операции на каждой позиции

How to find the maximum?

Segment tree / sparse table / Fenwick tree

Thanks. I did it!!!

Can't we find a positive-maximum sub-array using Kadane Algorithm in O(n) and subtract the maximum of same range computed using segment tree in O(logn) My Solution

But I am getting the wrong answer in 7th test case I have a rather fair idea that this approach is wrong.

But still can someone please let me help out with the "Same idea of Segment tree and Kadane Algo" with further changes to solve this problem.

Thanks in advance!!

Nice problems, waiting for F editorial, thanks for the contest :)

For problem D, what is the purpose of the

`best`

variable? I don't see a correspondence between it and any variables in Kandane's (https://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane's_algorithm)Best variable stores the minimum prefix sum that we have seen so far. In Kadane, at index i, the question is what is the maximum sum subarray that ends at index i. In other words, we want to find the maximum value of cur-pref where cur is the total sum of [0,i] and pref is some prefix sum of elements from [0,j] where j<i. So we want the minimum prefix sum we have seen so far in order to obtain the maximum value for cur-pref which is in our case cur-best. Then we also subtract mx as it will be removed.

Great explanation! It's really cool how the Kadane's algo can be rephrased using the prefix sum method you described. I only knew of the max / min way described on Wikipedia before :)

Sir, I kindly request you to explain why are we taking this infinity to replace a[i] if it is greater than max?

We are taking MINUS infinity. One other way of doing it is to simply consider only those intervals with all elements <= mx and ignore the ones that are greater. Then simply run Kadane on each of those intervals independently and update the answer. Setting values >mx to negative infinity has the same effect as Kadane will automatically never take those elements in a subarray (as they have minus infinity value) and this makes the code quite a bit easier to write.

A note for my not so experienced companions-In the editorial of

problem E, if someone else is also having trouble understanding why the following is true,( x mod a ) mod ( b a ) = ( x mod ( b a ) ) mod a = x mod aThen here's why,

For

( x mod a ) mod ( b a ) = x mod aWe know that

x mod awill already give us something smaller thanbaso that's whymod (ba)will have no effect on it.For

( x mod ( b a ) ) mod a = x mod aWhen we do

x mod (ba)we end up with something of the formx — k*(ba)(which is by definition of modulo). So we have subtractedafromx,k*btimes already but the remainingxmay still be big enough for morea's to be subtracted. That happens when we take its mod withaand we are ultimately left with the answer which we would have got if we had just donex mod aother way to prove

`Other way to prove (x mod (ba)) mod a = x mod a`

since`x mod (ba) = x - k*(ba)`

where k is some integer we can apply`mod a`

on both sidesHow to solve Problem C with binary search..as mentioned in above..

I used a ternary search for u can refer my solution 81858123. If u have any problem understanding do ask.

Using Binary Search

Hey anshumankr001, Why did you take the last for loop from(max(0,l-5),l+5)... is it just to be on the safe(st) side?

I did that because, in my solution I'm breaking the loop when

`l == r`

, and using this value as the optimal value. But, in my solution if`func(mid) > t`

I'm assigning`l = mid+1`

. It's possible that mid was the actual optimal value but I assigned`l = mid+1`

, and now, I'll end up with`l = (optimal value) + 1`

. You can now judge that, my solution would've worked if I had used 1 instead of 5 too but doing that was a necessity.Hi anshumankr001 can you please look at 81855634 once and tell me where i did wrong. Thank you!!

You're missing one case. Inside

`if(val >= (ld)t)`

, you'll also have to add`if(ans == val - t && last > mid) last = mid;`

to complete the solution.Thank you so much!!Understand

Hi anshumankr001,

I had similar approach as yours but because of one condition i was getting wrong answer then i looked at your solution and removed that condition and it got accepted but still i didn't get why it happened.

So i tried to submit your solution itself with that change and surprisingly that also got WA but i think that condition shouldn't have any affect on the answer.

I am sharing the two links one accepted and one wrong, can you please help me out?

WRONG ONE 82039446

ACCEPTED 82039513

Only difference is that in one of solution "cur = abs(func(mid)-t);" this line is commented and in one this is not

It's possible that two values will give the same difference say, a, b (a > b). After the binary search, you might get mid = a which will give you the optimal difference, but not the optimal answer. This modified code will give you the right answer:

CodePrevious code:

Modified Code:

even after this it is giving WA 82142984

can you help me ? not able to figure out the issue (just a guess can it be due to some precision issues?)

You forgot

`ans = min(ans, i)`

. Either add that, or loop in reverse, i.e.`for(int i=l+5, i>=max(0LL, l-5); i--)`

. Both will effectively do the same job.thanks got accepted :)

How are you deciding upper bound for binary search?

Hi @anshumankr001 , your solution would still work if u take the upper limit of binary search (r) as (h+1).IT is not necessary to take it as 1e9.

Maybe this explaination might help — https://pro-coder.tech/cf-1359-problems/

This might help!

https://codeforces.com/blog/entry/78116?#comment-632536

81792654 Have a look!

That allows us to find such k, that the value of tk is exactly t. However, such k might not be integer. (k+1)⋅h+c/2k+1 forgot to multiply k with c

Do you have any suggestions for this method?

Task C took soul out of me but never showed AcceptedTry tracing an example. let's say h=10 c=5, try taking 1,2,3 and so on. if we take 1, the average would be 10, taking 2 the average would be 7.5, taking 3 the average would be 8.333 , taking 4 the average would be 7.5, notice that if you take any even number, the average would be the same. so in this example if 7.5 is the closest to t, we would surely take 2 because it is the minimum even number. Going on taking odd numbers you will notice that the average goes down towards 7.5 but never below it. That means that when you take larger odd numbers you would converge to the average when taking any even number(all gives the same average). Now as the average is always going down as we are taking larger odd numbers we can use binary search to know which is the optimal odd number that we should take to make the average as close as possible to t. Supposing that t is less than or equal to the average when taking an even number, the answer would be 2 because when taking odd numbers, the average would never cross the even average and if we assume that the average when taking an odd large number can ever reach the even average. we would still pick 2 becuase it is smaller than that odd number. so if t<=(h+c)/2.0 "the even average" , the answer would be 2 , else we know that t is greater than the even average. we also know that as the odd number goes to infinity the odd average converges to the even average, so if t is greater than the even average , we are sure that there exists an odd number that its average is as close as possible to t, so we do a binary search considering only odd numbers and calculate the average for that mid then checking if average>t then we want a smaller number so we discard the left half else we want a larger number so we discard the right half. Going on, we would get the number that gives the closest average possible to t. if anything is still not clear, feel free to ask.``

I think the guy for whom you wrote such a descriptive comment does not deserve it.

Check out his submissions. You will find out.

Well you may be right. but i did it anyway assuming that he really needs help. It can also help someone else who may be struggling solving the problem.

Beautiful explanation... Thank you so much Magdy_Sedra !!!

Really nice explanation but I have a little doubt. When we are performing binary search on the odd numbers, what would be the upper and lower limits?

I don't see a single submission from your account for problem C. Please can you explain how did it took the soul out of you?

If i am not wrong you must be the kind of guy who creates new id just for the sake of posting comments.

check this video for detial explanation of problem c

https://youtu.be/Ts6to-_N-Y0

IT confused me why there were so few correct submissions for F — the time limit is very generous and you only have N^2/2, which is about 3e8 pairs to check if you brute force. So brute force should easily pass.

Unfortunately I didn't debug in time during the contest itself...

Yeah, brute force passes all the tests. I don't understand why the author's solution is so hard.

can anyone explain Problem A in a more beginner- friendly and easy way. or else tell me where i have gone wrong.

MY SUBMISSION: https://codeforces.com/contest/1359/submission/81751748 code is in C++. thank you!

It is not true. Here is the accepted submission.

I have a challenge for E

Solve it without having a % operator!

Could you please elaborate it?

Is it replacing every $$$a \% b$$$ with $$$(a - (a / b) * b)$$$

My submission : 81937062

That's good! Your code has no %. Now don't use modulo in any forms.

why did u just said dont' use modulo in any forms !! does that helps and if yes how ??

If anyone need detail explanation for C Here

How to solve D in $$$O(Nlog(N))$$$? Any D&C approach?

Edit: D&C $$$\implies$$$ Divide-and-conquercheck this video editorials for c and d C : https://youtu.be/Ts6to-_N-Y0 D : https://youtu.be/1h1D7wMbDis

I will share the approach of one of my friend 81836011.

If we need to find the answer between

`L`

and`R`

index, then we can do the followingLet

`i`

be the index of any maximum element in range`L`

to`R`

. There are three possiblities`L`

to`i - 1`

`i + 1`

to`R`

`i`

and therfore maximum of this subarray will be element at index`i`

.Now first two cases are recursion and for the third you need to find the maximum prefix sum for range

`i + 1`

to`R`

and maximum suffix sum for range`L`

to`i - 1`

. So these queries (maximum index, maximum suffix sum, maximum prefix sum) can be done by segment tree. The merging step will take O(logN) time and therefore even though our problem doesn't always reduce into two equal halves, we will achieve a time complexity of O(NlogN).I really like the idea, can you please help me to understand what build2 and build3 stands for in the code.

`build1`

is used for calculating the index of the maximum element in the range`build2`

is used for calculating maximum prefix sum for a range`build3`

is used for maximum suffix sum for a rangeFor the understanding of build2, you can see that when you merge two nodes either the max prefix will be one of that of max prefix sum of the left node or it could be taking full left node and taking max prefix sum for the right node. The segment tree is storing a pair in case of build2 where first of that pair is max prefix and second is sum of that range. A similar idea could be applied to build3 as well. You can refer the following link

Thankyou so much

This code has greatly helped me solidify my concepts on suffix sums, thanks a lot for sharing this code

Can anyone help with my approach? I am getting Wa but couldn't find why? My submission

can anybody tell me why i am getting WA?My submission I am getting answer 5 on my ide but on codeforces it shows "expected 5 ,found 7"

take test case 999977 17 499998 answer is 499981 but i think it should be 499979

please explain why?

.

$$$val1$$$ and $$$val2$$$ are only numerators, you have to compare $$$\frac{val1}{k}$$$ and $$$\frac{val2}{k+2}$$$

Thanks man I just understood that.

Did anyone do D with sparse table?

In problem E, should'nt it be (d-1)P(k-1) instead of (d-1)C(k-1), because the problem asks only to reorder the elements?

For example if the minimum element is 1, and the k=3, then {1,2,3} and {1,3,2} are both stable arrays but we are counting only one in the answer. What am i getting wrong?

You haven't got the question right but don't worry.

The question asks for how many different arrays are stable where a stable array is one that gives the same remainder irrespective of the permutation of the array.

For instance, {1,2,3} and {1,3,2} are not two different stable arrays but two permutations of the array {1,2,3}. Notice how in the question it is mentioned that we have to find the arrays such that 1 <= a1 < a2 < a3 <...<an <= n. This is a strictly increasing array.

Thanks a lot, i did not notice that last constraint

Am not able to completely understand Editorial of Problem D

CAN SOMEONE PLEASE WRITE AN ELABORATE EXPLANATION FOR IT.

Thanks in Advance.

Edit : No Longer needed , i got the idea from code in this video:https://www.youtube.com/watch?v=0WNladOR-XM

Please can you explain Problem D...i also can't able to under stand D.Although it looks straighforward

here in tutorial replacing value greater than max with infinity is quite confusing .. it's just saying that when A[i]>mx just start a new segment from i+1.. hence initialize again curr and best = 0 initialization again becoz we cannot include A[i] in current segment.

What I am doing wrong? https://codeforces.com/contest/1359/submission/81957966

in question c for testcase 999977 17 499998 answer should be 499979 because for number of cups 499979 and 499981 the temprature of barrel are 499998.0000020001 and 499997.9999979999 respectively so as mention in question answer should be 499979.

In D can't we just use Kadane's algorithm to find the maximum sub-array and then find the maximum number in that array and just subtract if from sum of the maximum array?

TC: 11 3 0 1 -2 5 -5 -1 0 3 2 2 My ans: 3 expected: 4 y is it 4? total is 8 and max number is 5 so ans should be 8-5=3

what subarray are u referring to ?

case : -1 10 -20 1 5 Max sub array is 10 , u subtract 10 ans will be 0. But optimally it should be 1 5 , subtract 5 , u get 1. This happens because in sub array with maximum sum if the most contribution is from max element itself and later u will hv to remove it , we deviate from the ans .

see this for better understanding 5 elements 1 50 -60 4 4

Thanks a lot man! I was having a hard time understanding what was the problem with my approach now clear :)

You can choose subarray $$$3$$$ $$$2$$$ $$$2$$$ and $$$sum = 7$$$, $$$max = 3$$$, so $$$sum - max = 4$$$

yeah, but according to my approach, I would have selected the entire array which was wrong :P now got the mistake thanks

How should I handle the test case 3 (9 6 3) in Problem A. I am not getting proper logic for else part. Please Help.

`cin>>n>>m>>k; if(m==0) cout<<0<<endl; else if(n/k>=m) cout<<m<<endl; else {//}`

For problem A, in the editorial.

a2 = (m — a1 + k — 2) / (k — 1).

Can Someone tell why 2 is subtracted from k in the above equation?

for calculating a2 the question boils down to distribute m-a1 card among k-1 players such that the max no. of cards any player gets is as min as possible, for this the only way is to distribute m-a1 cards equally among k-1 players. Now your would say that ans should be (m-a1)/(k-1) as this is equally dividing cards but you should also take care of (m-a1)%(k-1) cards as all cards need to be picked so in order to handle that what you can do is add largest remainder which u can get by dividing by k-1 which is k-2 hence you add k-2 also to the numerator. Its just a way of doing ceil operation. If after this also you dont want to add k-2 then you can check my solution without k-2

link — https://codeforces.com/contest/1359/submission/82014761

Nicely explained. Thanks!

tnx bro,for ceil() method..

For their solution in problem E, is there a reason they had to write an add function? Would simply adding and then using % not work?

It will lower the constant since you don't need to use % every time, which will make your program faster.

does basically writing out the mod function like that work faster than using the % operator? If so, why?

Here, only when $$$x\ge MOD$$$ or $$$x < 0$$$ you will take the modulo. But if you write it as

you need to take modulo every time, which may make your program slower.（Because % operator is the slowest among all operators)

can we find

`ncr % 998242353`

using DP(pascal's triangle).Because it am getting TLEthat's O(n^2), which is not fast enough for n<=5*10^5.

use c(n,r)=n!/r!/(n-r)! instead: 1. precomputing x! % 998242353 and 1/x! % 998242353. this takes O(k*n), k is a small constant. 2. for 1/x!, you need inverse modulo. 3. computing with n!/r!/(n-r)! takes O(1).

1379D - New Passenger Trams

`You can see that for any value between y and mx the maximum sum segment will always be that chosen one.`

Can Someone explain this?

`

i like that editorial has proofs . i wish every editorial had it

Is there someone else as well who just sinked into the floating point numbers for solving problem C but never get accepted.I hope now it's clear to you why using float will not work there........

HAHA me!

I understood the problem C wrongly, I don't know if I was the only one lol, I thought that after pouring a cup you wait for the temperature to stabilize and AFTER that you pour the next cup, which will change the equation.. because if we note t_k the temperature after the k-th pour then for even k we have t_k=(t_(k-1)+c)/2 and for odd k we have t_k=(t_(k-1)+h)/2...

I see where your confusion comes from, but the problem clearly stated that:

"The water temperature in the barrel is an average of the temperatures of the poured cups."

I recommend that if you're not getting the correct answer in the test cases you re-read the problem (or the notes). This should've solved your doubt.

In Problem C, I was thinking the same Strategy but I got stuck so can you guys help me out. I am assuming total "n" cups are used. so the following cases are possible.

1. CASE:Half of the cups are hot and half of them are of cold water. Then the following equation is formed ((n/2)*h + (n/2)*c)/n or (h+c)/2. If this is the case then average temp. T is (h+c)/2.

If temperature t <= (h+c)/2 then always 2 cups of water are used.2. CASE:Another case I was thinking of if (n-1)/2 + 1 hot water cups and (n-1)/2 cold water cups then according to average temp. T is (((n-1)/2 + 1)*h + ((n-1)/2)*c)/n.

I get average temperature T = ((n+1)*h + (n-1)*c)/2*n .Now after this how I proceed.??

I didn't understand the last statement in PROBLEM E

`On the other hand, suppose there exists an element ai such that it is not divisible by a1. Let's take x=ai and two following reorders of the array a: [a1,a2,…,ak] and [ai,a1,a2,…,ai−1,ai+1,…,ak]. For the first array, we get xmoda1=aimoda1, which is non-zero; and for the second array, aimodai=0, so the result is zero.`

if ai is not divisible by a1 then it will leave a (non-zero)remainder upon being further divided by multiples of ai whereas the ai in the second permutation will clearly amount to zero.

for problem D : lets say the current value of mx is 5 and we dont have any 5 in our array how can current answer for this sub task be sum of largest segment — 5 ??

Can someone please tell me what is error in my code for problem C. I have used almost same approach that is given in tutorial. But my code is failing for test case "999977 17 499998" The error msg is :- wrong answer 14th numbers differ — expected: '499981', found: '499979'. my code

I tried to print abs(temp-t) value at steps 499981 and 499979 and both the values are coming same. (2.00007e-06). Is it because of precision error? Thanks in advance

I had the exact same error on the same problem. Looking into the case, it seems like floating point precision is insufficient (i.e. the numbers appear the same when compared), so it cannot properly determine whether to pick k or k + 1 (explained in the tutorial).

Thanks jay_vish, it the problem of floating-point precision.

What's the meaning of "Trivial" in the explaination Of Problem 'C' in the editorial. Sorry if it's a dumb question but i don't know the meaning.

In Problem F dx_i is suppose to be always between 1 and 10^3. That's what is given in the problem.

If that is true then why do we have negative dx_i in the examples itself ??

Am I missing something ?

Sorry it is the absolute value of dx, and not the actual value of dx.

In Problem F can someone please explain what is the meaning of :

Are we launching all the cars at the same time ? Or are you launching them all at different times ?

What is the meaning of "choosing all ti" ??

can some one explain this part of problem ..how can we split the remaining jokers among the k-1 players by this way... (m — a1 + k — 2) // (k — 1)

m is the total number of jokers. a1 is the number of jokers for the first hand.

Subtract m — a1 you get the remaining jokers to distribute to the rest of the hand.

The rest of the number of groups from the hand is k — 1.

We then do ceil((m — a1) / (k — 1)) to get our answer.

Adding k — 2 and then dividing k — 1 is the same as doing the ceiling.

How to solve problem B if tiles are rotatable? And is it even possible to solve it without a complete search?

Can somebody please help me with Question C. Since |tb-t| is a unimodular function we can apply ternary search and we have to find the lowest point. I have ternary searched over the total number of cups. Hot cups will be total/2 ceiling and the left will be cold cups; then i have calculated temp and applied ternary search but it is not working. Can somebody help.

https://ideone.com/7q32JO