Thanks for participating! Despite the round being unrated, we hope you've enjoyed the problemset. We put a lot of effort into this round :prayge:
I want to give huge thanks to Dominater069 and satyam343 for their heavy contributions to the subtasks of G. If you're participating out of competition, we hope you enjoyed attempting these bonus subtasks. Otherwise, we hope you will enjoy upsolving them!
Problem Credits: cry
Analysis: cry
We choose $$$c$$$ between $$$a$$$ and $$$b$$$ $$$(a \leq c \leq b)$$$. The distance is $$$(c - a) + (b - c) = b - a$$$. Note that the distance does not depend on the the position $$$c$$$ at all.
for _ in range(int(input())):
a,b = map(int,input().split())
print(b-a)
Problem Credits: cry
Analysis: cry
Implement the statement. Iterate from $$$n-1$$$ to $$$0$$$ and use the .find() method in std::string in C++ (or .index() in python) to find the '#' character.
import sys
input=lambda:sys.stdin.readline().rstrip()
for i in range(int(input())):
n=int(input())
print(*reversed([input().index("#")+1 for i in range(n)]))
2009C - The Legend of Freya the Frog
Problem Credits: vgoofficial
Analysis: cry
Consider the $$$x$$$ and $$$y$$$ directions separately and calculate the jumps we need in each direction. The number of jumps we need in the $$$x$$$ direction is $$$\lceil \frac{x}{k} \rceil$$$ and similarily $$$\lceil \frac{y}{k} \rceil$$$ in the $$$y$$$ direction. Now let's try to combine them to obtain the total number of jumps. Let's consider the following cases:
$$$\lceil \frac{y}{k} \rceil \geq \lceil \frac{x}{k} \rceil$$$. In this case, there will need to be $$$\lceil \frac{y}{k} \rceil - \lceil \frac{x}{k} \rceil$$$ extra jumps in the $$$y$$$ direction. While Freya performs these extra jumps, she will choose $$$d = 0$$$ for the $$$x$$$ direction. In total, there will need to be $$$2 \cdot \lceil \frac{y}{k} \rceil$$$ jumps.
$$$\lceil \frac{x}{k} \rceil > \lceil \frac{y}{k} \rceil$$$. We can use the same reasoning as the previous case, but there's a catch. Since Freya is initially facing the $$$x$$$ direction, for the last jump, she does not need to jump in the $$$y$$$ direction. In total, there will need to be $$$2 \cdot \lceil \frac{x}{k} \rceil - 1$$$ jumps.
for _ in range(int(input())):
x,y,k = map(int,input().split())
print(max(2*((x+k-1)//k)-1,2*((y+k-1)//k)))
Problem Credits: vgoofficial
Analysis: cry
Initially, the obvious case one might first consider is an upright right triangle (specifically, the triangle with one of its sides parallel to the $$$y$$$-axis). This side can only be made with two points in the form $$$(x, 0)$$$ and $$$(x,1)$$$. We only need to search third point. Turns out, the third point can be any other unused vertex! If the third point has $$$y = 0$$$, then it will be an upright triangle, but if the third point has $$$y = 1$$$, it will simply be upside down.
One of the other case is in the form of $$$(x,0), (x+1,1), (x+2, 0)$$$. Let's see why this is a right triangle. Recall that in right triangle, the sum of the squares of two of the sides must equal to the square of the third side. The length between the first and the second point is $$$\sqrt 2$$$ because it is the diagonal of $$$1$$$ by $$$1$$$ unit block. Similarily, the second and third point also has length $$$\sqrt 2$$$. Obviously, the length between the first and third point is $$$2$$$. Since we have $$$\sqrt 2^2 + \sqrt 2^2 = 2^2$$$, this is certainly a right triangle. Of course, we can flip the $$$y$$$ values of each point and it will still be a valid right triangle, just upside down.
from collections import Counter
for _ in range(int(input())):
n = int(input())
nums = []
for i in range(n):
x,y = map(int,input().split())
nums.append((x,y))
ans = 0
b = Counter(x[0] for x in nums)
check = set(nums)
for i in b:
if b[i]==2: ans += n-2
for p in check:
if (p[0]-1,p[1]^1) in check and (p[0]+1,p[1]^1) in check:
ans +=1
print(ans)
2009E - Klee's SUPER DUPER LARGE Array!!!
Problem Credits: cry
Analysis: cry
We can rewrite $$$x$$$ as $$$|a_1+\dots+a_i-(a_{i+1}+\dots+a_n)|$$$. Essentially, we want to minimize the absolute value difference between the sums of the prefix and the suffix. With absolute value problems. it's always good to consider the positive and negative cases separately. We will consider the prefix greater than the suffix separately with the less than case.
We can use binary search to search for the greatest $$$i$$$ such that $$$a_1 + \dots + a_i \leq a_{i+1} + \dots + a_n$$$. Note that here, the positive difference is minimized. If we move to $$$i+1$$$, then the negative difference is minimized (since the sum of prefix will now be less than the sum of suffix). The answer is the minimum absolute value of both cases.
To evaluate $$$a_1 + \dots + a_i$$$ fast, we can use the sum of arithmetic sequence formula.
from collections import Counter
def val(mid):
val1 = (mid+k-1+k)*mid//2
val2 = (k+n-1+k)*n//2 - val1
return val1,val2
for _ in range(int(input())):
n,k = map(int,input().split())
lo = 1
hi = n
curr = 1
while lo <= hi:
mid = (lo+hi)//2
a,b = val(mid)
if b>a:
curr = mid
lo = mid+1
else:
hi = mid-1
a1,b1 = val(curr)
a2,b2 = val(curr+1)
print(min(b1-a1,a2-b2))
Bonus: Solve in $$$\mathcal{O}(1)$$$.
import sys
input=sys.stdin.readline
from math import floor,sqrt
f=lambda x: (2*x*x + x*(4*k-2) + (n-n*n-2*k*n))//2
t=int(input())
for _ in range(t):
n,k=map(int,input().split())
D=4*k*k + 4*k*(n-1) + (2*n*n-2*n+1)
i=(floor(sqrt(D))-(2*k-1))//2
ans=min(abs(f(i)),abs(f(i+1)))
print(ans)
Problem Credits: cry
Analysis: cry
Let's duplicate the array $$$a$$$ and concatenate it with itself. Now, $$$a$$$ should have length $$$2n$$$ and $$$a_i = a_{i-n}$$$ for all $$$n < i \leq 2n$$$. Now, the $$$j$$$'th element of the $$$i$$$'th rotation is $$$a_{i+j-1}$$$.
It can be shown for any integer $$$x$$$, it belongs in rotation $$$\lfloor \frac{x-1}{n} \rfloor + 1$$$ and at position $$$(x-1) \mod n + 1$$$. Let $$$rl$$$ denote the rotation for $$$l$$$ and $$$rr$$$ denote the rotation for $$$r$$$. If $$$rr - rl > 1$$$, we are adding $$$rr-rl-1$$$ full arrays to our answer. The leftovers is just the suffix of rotation $$$rl$$$ starting at position $$$l$$$ and the prefix of rotation of $$$rr$$$ starting at position $$$r$$$. This can be done with prefix sums. You may need to handle $$$rl=rr$$$ separately.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
int t;
cin >> t;
while (t--) {
ll n, q;
cin >> n >> q;
vector<ll> a(n), ps(1);
for (ll &r : a) {
cin >> r;
ps.push_back(ps.back() + r);
}
for (ll &r : a) {
ps.push_back(ps.back() + r);
}
while (q--) {
ll l, r;
cin >> l >> r;
l--; r--;
ll i = l / n, j = r / n;
l %= n; r %= n;
cout << ps[n] * (j - i + 1) - (ps[i + l] - ps[i]) - (ps[j + n] - ps[j + r + 1]) << "\n";
}
}
}
2009G1 - Yunli's Subarray Queries (easy version)
Problem Credits: cry, vgoofficial
Analysis: vgoofficial
We first make the sequence $$$b_i=a_i-i$$$ for all $$$i$$$. Now, if $$$b_i=b_j$$$, then $$$i$$$ and $$$j$$$ are in correct relative order.
Now, to solve the problem, we precompute the answer for every window of $$$k$$$, and then each query is a lookup. We use a sliding window, maintaining a multiset of frequencies of values of $$$b$$$ in the current window. To move from the window $$$[i\ldots i+k-1]$$$ to $$$i+1 \ldots i+k$$$, we lower the frequency of $$$b_i$$$ by $$$1$$$, and increase the frequency of $$$b_{i+k}$$$ by $$$1$$$.
#include "bits/stdc++.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#define fast ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0)
#define endl '\n'
#define int long long
#define f first
#define mp make_pair
#define s second
using namespace std;
void solve(){
int n, k, q; cin >> n >> k >> q;
int a[n + 1]; for(int i = 1; i <= n; i++) cin >> a[i];
map <int,int> m;
multiset <int> tot;
for(int i = 1; i <= n; i++) tot.insert(0);
for(int i = 1; i < k; i++){
tot.erase(tot.find(m[a[i] - i]));
m[a[i] - i]++;
tot.insert(m[a[i] - i]);
}
int ret[n + 1];
for(int i = k; i <= n; i++){
tot.erase(tot.find(m[a[i] - i]));
m[a[i] - i]++;
tot.insert(m[a[i] - i]);
int p = i - k + 1;
ret[p] = k - *tot.rbegin();
tot.erase(tot.find(m[a[p] - p]));
m[a[p] - p]--;
tot.insert(m[a[p] - p]);
}
while(q--){
int l, r ; cin >> l >> r;
cout << ret[l] << endl;
}
tot.clear();
m.clear();
}
signed main()
{
fast;
int t;
cin >> t;
while(t--){
solve();
}
}
2009G2 - Yunli's Subarray Queries (hard version)
Analysis: Solution 1: vgoofficial, Solution 2: awesomeguy856
First, read the solution to the easy version of the problem to compute the answer for every window of $$$k$$$. Let $$$c_i=f([a_i, ..., a_{i+k-1}])$$$. Now, the problem simplifies to finding
$$$\sum_{j=l}^{r-k+1} ( \min_{i=l}^{j} c_i)$$$
We will answer the queries offline in decreasing order of $$$l$$$. We maintain a lazy segment tree. We have a variable $$$x$$$ sweeping from $$$n-k$$$ to $$$0$$$. As the variable sweeps leftwards, in node $$$i$$$ of the segment tree, we keep track of $$$\min_{j=x}^{i}c_i$$$.
To decrease the value of $$$x$$$, we note that the range $$$[x-1, y]$$$ in the segment tree will be set to $$$c_{x-1}$$$, where $$$y$$$ is the largest value such that $$$c_y>c_{x-1}$$$ but $$$c_{y+1}\leq c_{x-1}$$$ (or $$$y=n-1$$$). To find the $$$y$$$ for each $$$x$$$, we may either walk/binary search in the segment tree, or use a monotonic stack.
#include "bits/stdc++.h"
#define int long long
template <typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
os << "[ ";
for (const auto& elem : vec) {
os << elem << " ";
}
os << "]";
return os;
}
using namespace std;
int getAns(int& k, multiset<int>& ms) { return k - (*ms.rbegin()); }
struct SegTree {
int n;
vector<int> tree, setLazy, begin, end;
void prop(int i) {
if (setLazy[i] != -100) {
setLazy[2 * i + 1] = setLazy[2 * i] = setLazy[i];
tree[2 * i] = tree[2 * i + 1] =
setLazy[i] * (end[2 * i + 1] - begin[2 * i + 1] + 1);
setLazy[i] = -100;
}
}
SegTree(int nn) {
n = 1;
while (n < nn) n *= 2;
tree.resize(2 * n);
setLazy.resize(2 * n, -100);
begin.resize(2 * n);
end.resize(2 * n);
for (int i = n; i < 2 * n; i++) {
begin[i] = end[i] = i - n;
}
for (int i = n - 1; i > 0; i--) {
begin[i] = begin[2 * i];
end[i] = end[2 * i + 1];
}
}
void rangeSet(int i, int amt, int lo, int hi) {
if (i < n) prop(i);
if (begin[i] == lo && end[i] == hi) {
tree[i] = amt * (hi - lo + 1);
setLazy[i] = amt;
return;
}
if (begin[2 * i] <= hi && end[2 * i] >= lo) {
rangeSet(2 * i, amt, lo, min(hi, end[2 * i]));
}
if (begin[2 * i + 1] <= hi && end[2 * i + 1] >= lo) {
rangeSet(2 * i + 1, amt, max(lo, begin[2 * i + 1]), hi);
}
tree[i] = tree[2 * i] + tree[2 * i + 1];
}
int query(int i, int lo, int hi) {
if (i < n) prop(i);
if (begin[i] == lo && end[i] == hi) return tree[i];
int ans = 0;
if (begin[2 * i] <= hi && end[2 * i] >= lo) {
ans += query(2 * i, lo, min(end[2 * i], hi));
}
if (begin[2 * i + 1] <= hi && end[2 * i + 1] >= lo) {
ans += query(2 * i + 1, max(lo, begin[2 * i + 1]), hi);
}
return ans;
}
};
signed main() {
int t;
cin >> t;
while (t--) {
int n, k, q;
cin >> n >> k >> q;
vector<int> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
v[i] = v[i] - i;
}
vector<int> ans(n); // ans[i] is answer from i to i+k-1
map<int, int> mp;
multiset<int> active;
for (int i = 0; i < k; i++) {
if (mp[v[i]] == 0) {
mp[v[i]] = 1;
active.insert(1);
} else {
active.erase(active.find(mp[v[i]]));
mp[v[i]]++;
active.insert(mp[v[i]]);
}
}
ans[0] = getAns(k, active);
for (int i = k; i < n; i++) {
// erase v[i-k]
active.erase(active.find(mp[v[i - k]]));
mp[v[i - k]]--;
if (mp[v[i - k]] != 0) active.insert(mp[v[i - k]]);
if (mp[v[i]] == 0) {
mp[v[i]] = 1;
active.insert(1);
} else {
active.erase(active.find(mp[v[i]]));
mp[v[i]]++;
active.insert(mp[v[i]]);
}
ans[i - k + 1] = getAns(k, active);
}
vector<array<int, 3>> queries(q);
vector<int> an(q);
for (int i = 0; i < q; i++) {
queries[i][2] = i;
cin >> queries[i][0] >> queries[i][1];
queries[i][0]--;
queries[i][1]--;
queries[i][0] *= -1;
}
sort(begin(queries), end(queries));
for (int i = 0; i < q; i++) queries[i][0] *= -1;
SegTree st(n);
st.rangeSet(1, ans[n - k], n - k, n - k);
int cur = n - k;
stack<pair<int, int>> s;
s.push({ans[n - k], n - k});
for (int i = 0; i < q; i++) {
while (cur != queries[i][0]) {
cur--;
int here = cur;
while (s.size() && s.top().first > ans[cur]) {
here = s.top().second;
s.pop();
}
s.push({ans[cur], here});
st.rangeSet(1, ans[cur], cur, here);
}
an[queries[i][2]] =
st.query(1, queries[i][0], queries[i][1] - k + 1);
}
for (auto x : an) cout << x << endl;
}
}
Let $$$p_i$$$ be the smallest value $$$j>i$$$ such that $$$c_j<c_i.$$$ We can calculate these values using a monotonic stack and iterating through $$$c$$$ backwards. If such $$$j$$$ does not exist, then we let $$$p_i=n.$$$ Then $$$f(h,i)=c_i$$$ for all $$$i\le h-k+1<p_i.$$$ Further, $$$f(h,i)=c_{p_i}$$$ for $$$p_i\le h-k+1<p_{p_i},$$$ and so on.
Now, let $$$w(0,i)=i,$$$ and $$$w(h,i)=p_{w(h-1,i)}$$$ for $$$h>0.$$$ To calculate the answer for a query $$$(l,r),$$$ consider the largest value of $$$j$$$ such that $$$w(j,l)\le r.$$$ Then we can take the sum $$$c_{w(j,l)}\cdot(r-w(j,l)+1)+\sum_{i=1}^jc_{w(i-1,l)}\cdot(w(i,l)-w(i-1,l)).$$$
Now it remains to quickly calculate this sum. We can use binary lifting to solve this. Specifically, we create an $$$n\times20$$$ data table where $$$d[i][j]=\sum_{h=1}^{2^j}c_{w(h-1,i)}\cdot(w(h,i)-w(h-1,i)),$$$ if $$$w(2^j,i)$$$ exists, and $$$-1$$$ otherwise. We can precompute this table recursively, as $$$d[i][0]=c_i\cdot(w(1,i)-i)$$$ and $$$d[i][j]=d[i][j-1]+d[w(2^{j-1},i)][j-1].$$$
Then, to answer queries, we iterate $$$j$$$ from $$$19$$$ to $$$0,$$$ and if $$$w(2^j,l)\le r,$$$ we add $$$d[l][j]$$$ to our answer, and set $$$l=w(2^j,l).$$$ At the end, we add $$$c_l\cdot(r-l+1)$$$ to our answer.
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
void solve() {
int n, k, q;
cin >> n >> k >> q;
vector<int> a(n);
for (int &r : a) cin >> r;
vector<int> c(3 * n), v(n);
multiset<int> s;
for (int i = 0; i < k; i++) c[a[i] - i + n - 1]++;
for (int r : c) s.insert(r);
v[k - 1] = k - *s.rbegin();
for (int i = k; i < n; i++) {
int x = a[i] - i + n - 1, y = a[i - k] - i + k + n - 1;
c[x]++;
s.erase(s.find(c[x] - 1));
s.insert(c[x]);
c[y]--;
s.erase(s.find(c[y] + 1));
s.insert(c[y]);
v[i] = k - *s.rbegin();
}
vector<int> l(n, -1);
stack<pii> t;
for (int i = k - 1; i < n; i++) {
while (!t.empty()) {
if (t.top().se <= v[i]) break;
l[t.top().fi] = i;
t.pop();
}
t.push({i, v[i]});
}
vector<vector<pii>> w(n, vector<pii>(20, {-1, -1}));
for (int i = n - 1; i >= k - 1; i--) {
w[i][0].se = l[i];
if (l[i] < 0) {
w[i][0].fi = (n - i) * v[i];
continue;
}
w[i][0].fi = (l[i] - i) * v[i];
for (int j = 1; j < 20; j++) {
if (w[w[i][j - 1].se][j - 1].se < 0) break;
w[i][j].se = w[w[i][j - 1].se][j - 1].se;
w[i][j].fi = w[i][j - 1].fi + w[w[i][j - 1].se][j - 1].fi;
}
}
while (q--) {
int l, r, ans = 0;
cin >> l >> r;
l--;
r--;
l += k - 1;
for (int j = 19; ~j; j--) {
if (w[l][j].se < 0) continue;
if (w[l][j].se > r) continue;
ans += w[l][j].fi;
l = w[l][j].se;
}
cout << ans + v[l] * (r - l + 1) << "\n";
}
}
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) solve();
}
2009G3 - Yunli's Subarray Queries (extreme version)
Analysis: Dominater069
I decided to write the Editorial for this problem in a step-by-step manner. Some of the steps are really short and meant to be used as hints but i decided to have a uniform naming for everything.
Continuing from the easier versions of the problem, we know we need to compute sum of min of subarrays, and answer subarray queries on this. Consider the standard approach of finding sum of min over all subarrays.
Sum of min of all subarrays for a fixed array is a well known problem. Here is how you can solve it, given an array $$$a$$$ of length $$$n$$$.
Let $$$nx_i$$$ denote the smallest integer $$$j (j > i)$$$ such that $$$a_j < a_i$$$ holds, or $$$n + 1$$$ if no such integer exists. Similarly, define $$$pv_i$$$ denote the largest integer $$$j (j < i)$$$ such that $$$a_j \le a_i$$$ holds, or $$$0$$$ if no such integer exists.
The answer is simply $$$\sum_{i = 1}^{n} a_i \cdot (nx_i - i) \cdot (i - pv_i)$$$. Calculating $$$nx_i$$$ and $$$pv_i$$$ can be done with Monotonic Stack.
Given a query $$$(L, R)$$$, divide all indices $$$i$$$ ($$$L \le i \le R$$$) into $$$4$$$ groups depending on the existence of $$$nx_i$$$ and $$$pv_i$$$ within the interval $$$[L, R]$$$, i.e. :
Case $$$1$$$ : $$$L \le pv_i, nx_i \le R$$$
Case $$$2$$$ : $$$pv_i < L, nx_i \le R$$$
Case $$$3$$$ : $$$L \le pv_i, nx_i > R$$$
Case $$$4$$$ : $$$pv_i < L, nx_i > R$$$
Try to calculate the contributions of each of these categories separately.
Case $$$1$$$ can be reduced to rectangle queries. Case $$$4$$$ is simple to handle as there is atmost $$$1$$$ element which satisfies that condition, which (if exists) is the minimum element in the range $$$(L, R)$$$ which can be found using any RMQ data structure like Sparse Table or Segment Tree.
Given a list of $$$n$$$ tuples $$$(l, r, v)$$$ and $$$q$$$ queries $$$(L, R)$$$ you have to add $$$v$$$ to answer of the $$$i$$$-th query if $$$L <= l <= r <= R$$$.
This can be solved in $$$O((n + q) log(n))$$$ using Fenwick Tree and Sweepline.
Iterate from $$$i = n$$$ to $$$i = 1$$$. For every tuple with left end at $$$i$$$ say $$$(i, j, v)$$$, add $$$v$$$ to a range query sum data structure at position $$$j$$$. Then, for every query with left end at $$$i$$$, we can simply query the range sum from $$$i = l$$$ to $$$i = r$$$ to get the required answer.
For every index $$$i$$$ from $$$1$$$ to $$$n$$$, generate a tuple as $$$(pv_i, nx_i, a_i \cdot (i - pv_i) \cdot (nx_i - i)$$$. Then, solve the Rectangle Queries problem with this list of tuples. The answer will be the required contribution of all indices belonging to Case $$$1$$$.
This leaves us with Case $$$2$$$ and $$$3$$$, which are symmetric, so we discuss only case $$$2$$$.
Let us sweepline from $$$i = n$$$ to $$$i = 1$$$, maintaining a Monotonic Stack of elements, popping elements when we find a smaller element, similar to how we find $$$pv_i$$$.
The indices belonging to Case $$$2$$$ are precisely the elements present in the Monotonic Stack (obviously ignore any element $$$> R$$$) when we have swept till $$$i = L$$$, with the possible exception of the minimum in the range $$$[L, R]$$$ (that might belong to Case $$$4$$$).
Let's analyze the contribution of the indices in Case $$$2$$$.
It is $$$a_i \cdot (L - i + 1) \cdot (nx_i - i)$$$.
Take a look at what happens when we go from $$$L$$$ to $$$L - 1$$$, how do all the contributions of elements belonging to Case $$$2$$$ change.
Some elements get popped from the Monotonic Stack because $$$a_{L - 1}$$$. We need to reset the contribution of all these elements to $$$0$$$.
The elements that do not get popped have their contribution increased by exactly $$$(nx_i - i)$$$.
$$$1$$$ element gets added to the Monotonic Stack, which is $$$a_{L - 1}$$$, so we need to initiliatize its contribution to $$$(nx_{L - 1} - (L - 1)).$$$
Resetting and Initiliazing Contribution is simple enough with most data structures, so let us focus on adding $$$(nx_i - i)$$$ to the elements present in the Monotonic Stack.
We can keep a Lazy Segment Tree with $$$2$$$ parameters, $$$sumcon=$$$ sum of all contributions in this segment tree node, and $$$addcon = $$$ sum of $$$(nx_i - i)$$$ of all "non-popped" elements in this node. The lazy tag will denote how many contribution increases I have to do. We can simply do $$$sumcon += lazy * addcon$$$ for the lazy updates.
Then, we can query the range sum from $$$L$$$ to $$$R$$$ to get the sum of contributions of all elements belonging to Case $$$2$$$. Case $$$3$$$ can be solved in a symmetric way. Adding up the answers over Case $$$1$$$, $$$2$$$, $$$3$$$ and $$$4$$$ will give us the required answer.
We need to be quite careful with the Case $$$4$$$ element, as we might double count its contribution in Case $$$2$$$ and $$$3$$$. I handle this in the model solution by querying the sum of contribution in $$$[L, X - 1]$$$ where $$$X$$$ is the largest element present in the monostack which is $$$\le R$$$, and handling $$$X$$$ separately. You can easily note that $$$X$$$ is the only element belonging to Case $$$4$$$ (if any at all).
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pii pair<int,int>
#define piii pair<pii,pii>
#define fi first
#define se second
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
struct segtree {
const static int INF = 1e18, INF2 = 0;
int l, r;
segtree* lc, * rc;
int v = INF, v2=0, v3=0, v4=0;
segtree* getmem();
segtree() : segtree(-1, -1) {};
segtree(int l, int r) : l(l), r(r) {
if (l == r) return;
int m = (l + r) / 2;
lc = getmem(); *lc = segtree(l, m);
rc = getmem(); *rc = segtree(m + 1, r);
}
int op(int a, int b) {
return min(a,b);
}
int op2(int a, int b) {
return a+b;
}
void add(int qi, int qv, int h, int h4=0) {
if (r < qi || l > qi) return;
if (l == r) { if (v==INF) v=qv; v2+=qv, v3+=qv*h; v4+=qv*h4; return;}
lc->add(qi, qv, h, h4); rc->add(qi, qv, h, h4);
v = op(lc->v, rc->v);
v2 = op2(lc->v2, rc->v2);
v3 = op2(lc->v3, rc->v3);
v4 = op2(lc->v4, rc->v4);
}
int qrr(int ql, int qx) {
if (v>=qx||r<ql) return 1e9;
if (l==r) return l;
int k=lc->qrr(ql,qx);
if (k<1e9) return k;
return rc->qrr(ql,qx);
}
int q2(int ql, int qr) {
if (l > qr || r < ql) return INF2;
if (ql <= l && r <= qr) return v2;
return op2(lc->q2(ql, qr), rc->q2(ql, qr));
}
int q3(int ql, int qr) {
if (l > qr || r < ql) return INF2;
if (ql <= l && r <= qr) return v3;
return op2(lc->q3(ql, qr), rc->q3(ql, qr));
}
int q4(int ql, int qr) {
if (l > qr || r < ql) return INF2;
if (ql <= l && r <= qr) return v4;
return op2(lc->q4(ql, qr), rc->q4(ql, qr));
}
};
segtree mem[2000005];int memsz = 0;
segtree* segtree::getmem() { return &mem[memsz++]; }
void solve() {
int n, k, q;
cin >> n >> k >> q;
vector<int> a(n);
for (int &r : a) cin >> r;
vector<int> c(2 * n), v(n);
multiset<int> s;
for (int i = 0; i < k; i++) c[a[i] - i + n - 1]++;
for (int r : c) s.insert(r);
v[k - 1] = k - *s.rbegin();
for (int i = k; i < n; i++) {
int x = a[i] - i + n - 1, y = a[i - k] - i + k + n - 1;
c[x]++;
s.erase(s.find(c[x] - 1));
s.insert(c[x]);
c[y]--;
s.erase(s.find(c[y] + 1));
s.insert(c[y]);
v[i] = k - *s.rbegin();
}
vector<int> ans(q);
vector<vector<pii>> w(n);
segtree co(0, n+2), lb(0, n+2), e(0,n+2),e2(0,n+2);
vector<int> rb(n);
stack<int> t;
for (int i = 0; i < q; i++) {
int l,r; cin >> l >> r;
w[l+k-2].push_back({i,r-1});
}
for (int i = n-1; ~i; i--) {
e.add(i,v[i],i,i*i);
int j=min(n,e.qrr(i,v[i]));
rb[i]=j;
e.add(j-1,-v[i],i,i*i);
e2.add(j,v[i]*(j-i),i);
while (!t.empty()) {
int x=t.top();
if (v[x]<v[i]) break;
t.pop();
co.add(rb[x],v[x]*(rb[x]-x)*(x-i),0);
lb.add(x,v[x]*(x-i),x);
lb.add(rb[x]-1,-v[x]*(x-i),x);
e.add(x,-v[x],x,x*x);
e.add(rb[x]-1,v[x],x,x*x);
e2.add(rb[x],-v[x]*(rb[x]-x),x);
}
t.push(i);
int l=i;
for (auto [p,r]:w[i]) {
int x=e.q2(l,r), y=e.q3(l,r), z=e.q4(l,r);
int f=y*(r+1)-z, g=x*(r+1)-y;
int lx=lb.q2(l,r), ly=lb.q3(l,r);
ans[p]=co.q2(l,r+1)+lx*(r+1)-ly+e2.q3(l,r+1)-e2.q2(l,r+1)*(i-1)+f-g*(i-1);
}
}
for (int r:ans) cout << r << "\n";
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1; cin >> t;
while (t--) solve();
}
Auto comment: topic has been updated by cry (previous revision, new revision, compare).
The G2 problem can also be solved by the MO algorithm. My solution is:https://codeforces.me/contest/2009/submission/279633321
Can you explain your solution in detail
I've just solved it with mo+sqrt decomposition too. here my 279746467
The idea is the following:
get array ans from G1 problem. ans[i] means the min number of operations needed in range [i,i+k).
Now, for a query (l,r), the problem reduces to find min({ans[l]}) + min({ans[l],ans[l+1]}) + min({ans[l],...ans[r-k+1]}). This is range queries and it can be solved with mo+sqrt by dividing ans in buckets and sorting the queries
Your bucket size X = q/sqrt(n) // this is an optimal value, no need to explain here. You can also choose X = sqrt(n) as your bucket size.
Sort queries. Say query1 = l1,r1 and query2 = l2,r2. if l1/X == l2/X, then they are on the same bucket and order by r1 < r2. If on different bucket, return l1/X<l2/X. Save original order of queries before sort it.
Answer queries by getting answer from left sid (it just iterates over a bucket size, X) and for right sid I build on every query of the same bucket a vector to save min values of ans[i] and a suffix sum. Then with the min value from left side make a lowerbound to the vector of min values and find the position from which min value from left side is smaller in fector of min values of right position. Use the suffix sum to add the rest to your answer.
Sorry for large explanation ^-^
Check mo+sqrt here
Thanks for Explanation. I understood your solution
I have solved it using Range Min Query and Next Smallest Element in array
My Submission : 279798999
Time Complexity : O((N+Q)*logK)
It can also be solved using merge-sort tree
Solution using merge-sort tree: https://codeforces.me/contest/2009/submission/279748718
Can you explain the idea, the code is too messy to read
from G1 we precompute the answer for every window of k and store it in a new array (c). now answer for query (l,r) will be sum(j=l, r-k+1) min(i=l,j)ci. now we construc a merge-sort tree that stores values in (l,r). lets say sub-array c is like cl,cl+1,cl+2,cl+3,...,cr. this vector seg[400001] in (i,l,r) stores cl,min(cl,cl+1),min(cl,cl+1,cl+2),...min(cl,cl+1,...cr). now lets say query is (l,r), and we are in a segment (gl,gr), we also maintain an int pre_mn that calculates min in (l,gl-1). answer from this seg would be min(pre_mn,cgl),min(pre_mn,cgl,cgl+1),...min(pre_mn,cgl,...,cgr). now lets calculate sum of this values using binary search and prefix sum by finding the index until where cgl+i is greater than pre_mn, as it will become pre_mn.
ur merge sort tree is storing
cl,min(cl,cl+1),min(cl,cl+1,cl+2),...min(cl,cl+1,...cr).
and we need to query
min( cl , c(l+1) , c(l+2), c(l+2) ... )
how u did that ?
binary search forces
Apart from E which question needed Binary Search?
Nice Div. 3 contest !
maybe Div.2
In problem E i used prefix sum and got MLE bruh...
n<=1e9 binary search will work
its obvious coz you are taking 10^9 memory
binary_search is useful
maxn = 1e9
look at constraints, n,k ~ (10e9), storing that much prefix sums !!!!!
Can we solve D faster than O(n^2) if xi's were real numbers instead of integers ?
It appears I am wrong. Disregard this
actually, no i think there are other cases,
any x and y values that stisfy x*y = 1 here will count :
proof :
a^2 = 1 + x^2 , b^2 = 1 + y^2
and
a^2 + b^2 = (x+y)^2
hence,
2 + x^2 + y^2 = y^2 + x^2 + 2*x*y
or x*y = 1 .
I'm interested in your n^2 solution, is it something to do with circles?
Even easier (use the fact that left difference times right difference has to be equal to onesee prrof) : iterate over each point where y= 0 name it a , now for each point where y= 1 find its x difference from a say it is d now check if there is a point (1/d,1) and the rest is same as D.
In the C problem, there is a neat way to check whether there will be any other case or not.
Following the given explanation, one can see, that if any of the points on the side which contributes 2 points to the triangle are moved, the angle increases, and since we can't get them any closer without falling into Case 1, we can't have any more cases.
Another way that can be used is the fact that the slopes of the two perpendicular lines must give a product of -1.
So, if the points were $$$(x_{1}, 0), (x_{2}, 1), (x_{3}, 0)$$$, then we would have :
$$$(\frac{x_{2} - x_{1}}{1 - 0}) * (\frac{x_{3} - x_{2}}{0 - 1}) = -1$$$
which leads to :
$$$(x_{2} - x_{1})(x_{3} - x_{2}) = 1$$$
And since the differences will always be integers, we have :
$$$x_{1} + 1 = x_{2} = x_{3} - 1$$$
It's a good explanation for showing there is no other cases. I came up with similar idea using geometric properties of the median in a right triangle. Other than triangles with sides in a vertical line $$$(x, 0), (x, 1)$$$, triangles must have sides on a horizontal line. Then the median of the right triangle separate out the two parts $$$(x - t, k) ,(x + t, k)$$$ with the last vertex is $$$(x, k'), k,k'\in \{0,1\}$$$. Then the median of length m calculated as $$$m^2 = 1^2 + t^2\ $$$, thus $$$(m - t)(m + t) = 1$$$, with similar argument $$$m$$$ must be 1. Sides on horizontal line is 2, then $$$t = 1$$$
~~~~~~
~~~~~
why this fails??
if they are equal you should not do -1
yes actually true, but when i removed that eequality then too it was giving wrong.
you should not use doubles as vgoofficial mentioned
We should avoid doubles whenever possible. For ceiling calculation, you may instead use the modulo operator (%) or use (x+k-1)//k
okay <3! thank you!
You should not check for x > y, rather compare the number of steps to complete them.
I'm really happy to unrate b/c I'm really mad because I don't submit my code. :)))))
G2 and G3 are not div4 problems. They should only appear in div2 or div1.
On the contrary, they cannot appear in div2 or div1
They are far too standard for both of them.
They were never meant to be solved by actual participants, A — G1 is the actual div4 round. They are meant to educate higher rated people.
so why have div 4 :/
wdym? why have these "bonus" tasks in div4? or why have div4 at all?
how does it hurt you? Ignore it if you want to. It is not fit for a div2 or div1 clearly, why not have it here incase someone finds it useful?
Because we have an abundance of easy tasks and an abundance of low rated people? D
clearly not div4, admit your mistake instead of making baseless points.
Dominater069 orz thanks for admitting it
i admitted it lol.
Not every task exists has to exist for intended participants.
Authors (and me) wanted to add bonus educational tasks for high rated participants. I really dont understand how the intended audience was affected
I appreciate the extra tasks. G2 is fairly new to me, and G3 was totally new to me. These were good tasks for learning.
Yesterday I was feeling extra confident for some reason so i started from G2 and got destroyed. Luckily it went unrated. So that's how I intended participant got emotional damage LOL. Anyway I'll try to understand editorial.
honestly, based from previous div 4s, i think G3 (or maybe also G2 idk) should be a bonus question that appears in the editorial, as a challenge
although it's probably gonna be dismissed by lots of people, it'll be consistent with other rounds where in the editorial, they mentioned that they thought of harder constraints of the problem but not actually inserting it inside the problemset to make the round somewhat consistent.
Why Div.4 have to educate Master or Grandmaster? I cannot understand.
I think that that an overwhelmingly difficult problem is standard so can't put it in Div.2 doesn't mean that it can plugged in Div.4. I want a good problem must to be placed where a more people can solve it.
It doesnt have to, but isnt it good if it does? Who did it harm smh? Experts who want to be able to AK every div4 round. welp sad for them
Authors tried to do a nice thing by including extra tasks (something which they didnt have to do and still would be paid the same)
except G3 or G2 aren't good problems. Educational? sure. But educational problems should not affect rating.
I hate you so much
I think it's more like "it could've benefited more people in a higher division" rather than "it harmed those people."
While I see your argument, and it may be true that it won't be very good to be in a Div. 1 round, I honestly don't think there would be many solves even if it was in a Div. 2. I agree that standard problems shouldn't heavily affect ratings, but I think the benefits are far bigger to have this problem in a Div. 2 round instead of a Div. 4 round.
See how many of the 'target' people for these problems have actually participated in this round. If you want to attract those 'target' people and educate them, it needs to be rated for them to be motivated. Candidate masters won't expect a Div. 4 round to actually educate them, so there is little reason for them to even register for the contest and read the problem. It's not like having a few official solves ruins the whole authority of the rating system. It's way more important to motivate the fitting people to read and try the problem.
Also, G2 was actually an interesting problem for me. It may involve only a few standard techniques, but I don't think such standardness necessarily made the problem bad.
i agree with you that it would be on the edge of being fine for div2 because its hard enough so affecting only small number of people
But
you cant easily port a problem in between rounds, or decide the division based on one problem
even if it doesnt affect much, i dont see many div2 coordinators who would accept G3 as a d2F (even though it would be somewhat fine imo)
there was a high likelihood that G3 existed on the internet since it is a very natural problem, and indeed it's max variant existed on hackerrank. https://www.hackerrank.com/challenges/little-alexey-and-sum-of-maximums/problem (somebody solved it using this too)
Oh, you think G2 and G3 aren't good problems... Then why they are in contest? Isn't it wierd? Is it OK that not good problems in Div.4?
Then why Educational CodeForces (Div.2) exists? Just do plug all Educational CodeForces problem in Div.3 or Div.4. But there is reason that Educational CodeForces exists.
And why you're saying like that? Nobody said "I want to solve all of them!"
I'm just saying that problem must be its suitable position, so it can teach more people. If you do not think so, then I'm sorry. But I believe every problemsetter and coordinator, tester knows that Div.4 is not for Master or Grandmaster, but for Newbie or Pupil.
From problem solving perspective, it is mostly standard and implementation for me.
From eudcational perspective, it is useful as a problem to teach you the power of sweepline algorithms. There can be educational value in a problem despite it not being a "good" problem.
It's fake educational and has been for a long time.
years before, it used to be unrated and containing actually standard tasks. Now, it's just slightly more standard than average div2, but the name stuck.
This change happened almost solely because they became rated rounds.
But it comes at the cost of affecting people's ratings. Who likes to lose rating to a standard problem? I certainly don't
just to be clear, does "standard" mean a problem that's solvable using ONLY well-known algorithms and methods?
like everything it is a spectrum
A problem is more standard the more well known algorithms and methods as opposed to thinking about the problem.
so something like ratio of well known stuff : thinking needed gives you an idea about how standard a problem is
Without a doubt, this problem cannot appear on Div1, but it is actually fine as Div2F (we definitely had worse and more standard d2F).
The following only applies to unofficial contestants:
the mild complaint I had is that I participated in a div 4 round, expecting div 4 difficulties and “div 4 level resistances” only to find that this is not the case. Div 4 to me had been a “quick and easy AK and funny internet speed test with no verdicts for 10 minutes and so every penalty is worth 25 or more”. In fact, div2/3/4 (and obviously also div1) have distinct feels to it, so I am not so sure in general making it feels like div2, which is what happened when G2 and G3 we’re included.
This only made sense under my belief that this problem can totally be used on D2F as is.
G3 is probably not fine as 2F either, as there is a square root solution which is trivial to think of (no sweepline or monotonic stacks or rectangle queries) but annoying to implement (279798653).
Can you explain it in more details? I fail to see anything sqrt that isn’t a reinterpretation of a rectangle queries, it doesn’t seem like your solution is MO’s based.
it is also worth noting that G3 is also trivial if you have segment tree beats (range chmin, historic sum). Implementation is at least half of the problem.
I have solved it by processing queries offline.
I iterate over the leftbound $$$l$$$ of the query in decreasing order, while maintaining two arrays $$$p$$$ and $$$q$$$ through my square root structure.
When at a certain $$$l$$$, $$$p$$$ and $$$q$$$ are defined in the following manner:
So the answer for any query $$$[l, r]$$$ simply becomes $$$\sum_{i = l + k - 1} ^ {i = r} {q_i}$$$.
To maintain this array, my square root structure needs to be able to perform the following kinds of queries:
which can be done.
Your solution is identical to the intended one (Edit; after a slight more read on the intended solution it may have some subtle differences, nonetheless, it is identical to mine). It is just that you happens to choose to implement it via sqrt structures.This task could be completed by (lazy) segment tree too (no beats). I would say this is just difference in preference and the fact that it is passable by sqrt does not make it easier.
Perhaps, this task is more standard/widely known to be doable by sqrt. In this case, then the task would be more standard than what I initially thought.
why??
me, who on;ly solved A-G1 :(
I agree but I think it would be a better fit for a Div.3. Div.3 contests still contains standard questions
Ye G2 and G3 educate me, I don't know why the problem like this can't appear in div2 or div1, only observe problem can. It would be nice if Codeforces Div 2 mix observe problem and standard problem :)
I can see G2 barely being on the edge of a Div. 3 but G3 is straightforward way too difficult. It's maybe a harder one even for a 2F.
G3 is definitely below d2F level
I think it's more like most of the other 2Fs are too difficult in general, but okay.
if most 2F are more difficult then that’s the 2F difficulty level lmao
You can say the same thing to this: if we keep having these kind of problems in 4G, then this becomes a 4G level problem. However, that would be far from what I'd expect from a 4G, and 2F is kind of such state already.
I agree that G2/3 are beyond div 4 level but I think it’s clear that they’re not intended to be solved by div 4 participants
But they are in a DIV4 contest
It's an extra problem to be upsolved for education value. What harm did putting these questions here do? Did it affect anyone? No. Only 1 trusted user solved G2 and G3.
Maybe my opinion is stupid but when you say a DIV4 contest, I expect a contest that contains problems that a DIV4 participant can solve or upsolve. Similar logic for other divisions. But it is fine. Feel free to put a Div1F in the next DIV4 contest.
How many people in division 2 can solve F you think? What about the old div 4 G about 2-sat? Do you think newbies and pupils have a chance of inventing that on the fly without seeing 2sat before? Almost every final question on each round is far too hard for its division. We only included G2 and G3 because they follow quite naturally from G1, and if is impossible to port questions between rounds.
I never said the past div4 rounds were perfect. Also, I said I expect the target participants to be able to SOLVE or UPSOLVE the problems. So, because every final question on each round is too hard for its division, every round should follow this pattern? Anyway, it is your round, do as you want.
"Also, I said I expect the target participants to be able to SOLVE or UPSOLVE the problems."
Ok? isn't that the purpose of G2 and G3? For div.4 participants to upsolve? Of course, you don't have to upsolve it right now. You can always come back when you're better. The problem doesn't disappear.
I don't see any harm in contests with a harder final problem than its intended division. It gives strong participants of the intended division something to think about for the rest of the contest (instead of doing nothing), and makes more of a competition for higher rated participants.
do you really think that average div 4 users are gonna be able to understand the editorial for G2 and G3 just so that they can upsolve it hours or days after the contest? the point of upsolving a round that is consistent with your division is so that you can get AC on all of the problems by understanding what the editorial said shortly after the round ended. this is why most difficult problem in div 4s is usually around 1700-1900ish (that 2-sat 2100 problem doesn't count), because although most div 4 users cannot come up with the idea during the contest, the authors knew that some (not very small group of) div 4 users will understand the editorial given for the problem so that they can upsolve it immediately (or after some short period of time)
also, "makes more of a competition for higher rated participants" ok but the intended target for this round are pupils lmao
If you can’t understand G2 or G3, you can pretend those problems never existed, and move on. Alternatively, you can note their existence down and return later. It’s up to you.
A-G1 already makes a complete div 4.
so basically G2 or G3 is equivalent as the Ex problem in abc, where sometimes it's so hard it's not even intended for users who partake in abc
I don't know if G3 is really div2. F level. I just brute-forced my G2 solution with a random optimization and it got AC (after the contest). Here's my Submission.
If anyone is interested, try to hack me!
Hacked, brute forcing with a G2 solution would result in $$$O(n)$$$ per query in worst case. Hence, if there are many instances where $$$ind = i + 1$$$, you are not skipping much numbers and therefore TLE.
I also knew that it would give TLE on a case where my array ans[] had consecutively increasing elements. But I was not able to think of such a case.
Not sure how it managed to pass all the pretests.
Btw, thanks for hacking.
Sharing my video of winning the round along with explanations of my solutions: https://www.youtube.com/watch?v=JhL-oPzptlI
Thank you very much for an explanation for G3! Took a long time to implement solution on my own but this was worthy.
E was great !
I tried solving E by interpreting it as a function and using the quadratic equation, but it keeps giving the wrong answer for n = 1000000000, k = 1000000000
I also used the same logic. You probably have to use unsigned long long. I was able to pass the cases using that.
But wouldn't a <= sqrt(D). so, a — sqrt(D) will never be a solution since it is negative why are u checking it ??
was stuck in that for some time, but then used unsigned long long and it worked.. But came to the comments to see that it can be done by using binary search, need to see how they are applying it to the V curve, i mean ternary can work but binary.. no intuition honestly
In the end, I had to use Java, because the delta's value was 999,999,999,940,000,000,001 in the n = 1000000000, k = 1000000000 test case.
Here's my accepted submission: 279807077
For G1: There's a mathematical logic behind "ai — i". Let's say we have a sequence "(C, C + 1, C + 2, C + 3 + ...)". Any 'ith' element ai will be equal to "C + i — L", where 'L' is the starting index of the window. So (ai = C + i — L) => (C — L = ai — i). This (C — L) is a static part, which means we have to find the maximum occuring "ai — i".
You can think of E as an inverted mountain array and look for the minimum point using binary search
I think G1 can be solved by finding the longest increasing subarray for each query in O(logN)
Ans will be (right — left + 1) — longest;
counter example: arr = [1, 4, 9].
f(arr) = 2, while your method returns 0.
Longest *consecutive... Correction
counter example: arr = [1, 10, 3].
f(arr) = 1, while your method returns 2.
counter example arr = [1 2 5 4] here l = 1, r = 4, your answer = 4 — 2 = 2. but answer should be 1
My solution 279640569 of F, is giving correct output as 13 on my local and online compilers but wrong answer as 12 on codeforce's judge for following test case:
1
5 1
4 8 3 2 4
7 10
Can someone explain it?
Use C++ 20 while submitting the code.
why wasnt this AC for the frog and freya question?
compare jumpX and jumpY, not x and y when doing moves--
oh my god how did i miss that....gosh thank u for replying
can somebody explain how they used binary search for E? i found the function to be unimodal and hence i applied ternary search to find the point of minima, i dont get the intuition for binary search (i dont see monotonicity)
There is a V formation, check my solution. To find minima just use formula of summation n there are different cases where mid will lie
Just look for the point where
current_sum > (total_sum)/2
. The correct answer is nearby there. .The entire universe is against me for becoming pupil. Was doin super well today until that announcement appeared, L cry, L servers... MikeMirzayanov I think its time to add a new god damm server.
I miss SlavicG,mesanu,flamestorm ... (╥﹏╥)
Here is a clean(er than the edi) solution to C and a unique solution to D.
For C we can see that
$$$\lceil \frac{x}{k} \rceil$$$ + $$$\lceil \frac{y}{k} \rceil$$$ + $$$|\lceil \frac{y}{k} \rceil-\lceil \frac{x}{k} \rceil|$$$ — ($$$\lceil \frac{x}{k} \rceil$$$ > $$$\lceil \frac{y}{k} \rceil$$$)
This is because note that x goes first, and at some point we will have to use 0 for some turns once already at the coorindate for x or y.
Firstly, lets imagine we do not take more steps for x than we do y, it would go x,y,x,y and continue until we are all done, therefore we do not need to add 1. However if we were to take more steps for x than we do y, it creates a pattern x,y,x,y,x which requires an extra x, ys would simply become 0 after y is reached which is where the absolute value part of the problem comes from. x.
As for D, which I found much more interesting, though do note I misread it and as such overcomplicated it.
There were 2 main cases, 1: The right angle is rotated some multiple of 90 degrees from 0, and 2: The right angle is some (45 + 90x)%360 degrees, I saw the latter as a way to be able to use the x,y -> s,t transform used in geometry. This transform essentially turns x,y coordinates into coordinates of the y intercepts of slope y=x+b and y=-x+b. By doing so, we can create s,t = {x+y, x-y} though a bit of algebra. Using this transform, we have essentially rotated by 45 degrees making the last case trivial (I did not read that it was only 0 or 1 so I had not thought about the x+2 y^1 thing.) After this some basic map spam gives AC, do note that as long as the X is equal we can just add n-2 due to all points being on 0 or 1 on the Y.
If you are wondering the simpler solution to D for case 2 is that it simply has the points x,y x+1,y^1, x+2,y
Here are submissions for both, hope that puts these problems into a bit of a different perspective! C: 279561294 D: 279622363
This contest had quite a few issues with the queue and pages loading, however I still enjoyed the problems and I hope you did too! I would have gotten plus VE if this contest was rated however instead of complaining I had fun solving these problems even if I did overcomplicate D a bit, however it would give insight to a possible harder version of the problem if it was not only 0 and 1 on the Y.
I think this one is simpler 280325230.
Agreed, this method is simpler. 280854175
This was a good round, sad that it got unrated.
thanks for writing, issues not your fault!
I have a different solution for G2. Use a set and a map to get the minimum moves for the window of size k starting from every index. Then use a stack to build a vector to store the index of next smaller number. Then use jumps to next smaller number to compute answer for every range.
Hacked, your solution runs in O(n) per test case. Since in worst case, next_min[i] is just i+1, and you would be just jumping a number at a time.
Nice! Thanks for this!!
Nice Div3 Contest !!!
My code is failing in case of- 1000000 100000 10 givng me answer- 200000 !! Can someone point the mistake ?? Thanks
Because for this case in last iteration the count should be += 1 instead of += 2, because we reached (x, y) by doing the x operation only so why count y operation too.
the
count
after your process is always an even number.Note that at a moment when
(x == 0 && y == 0)
, you should break the loop immediately.Tried that it is giving one less the actual output!! but nvm this solution is only good in smaller testcases + it is a bruteforce solution !!
Moreover I tried this solution earlier , This will give you TLE
Yes i know, it is only good if testcase are small !! Before this contest, I don't know ceil formula of ceil function !!
I loved the HSR and Genshin references. Please do continue naming problems on our favourite characters. Thank you!
I have implemented the same logic as the solution above for 2009D - Satyam and Counting, but keep getting
I cannot see the corresponding input.
Can anyone please tell me what I am missing? https://codeforces.me/contest/2009/submission/279654100
I spotted one mistake but that does not fix the Wrong Answer above. The mistake is that each array should have size
n+1
instead ofn
because each0 <= x <= n
. I also fixed therange
s accordingly. But, as mentioned, the Wrong Answer stays the same.I figured it out. Because of my confusion with the range of
x
, the code decrementsx
. That mapsx=0
tox=-1
, which does not result in an error but in undesired behavior when used as alist
index.We can use binary search to search for the greatest i such that a1+⋯+ai≥ai+1+⋯+an
Isn't the solution for E wrong? If the above statement is the correct solution, the greatest i is just len-1 no?
In problem E's editorial ...
We can use binary search to search for the greatest i such that a1 + ⋯ + ai ≥ ai+1 + ⋯ + an . Note that here, the positive difference is minimized. If we move to i+1 , then the negative difference is minimized (since the sum of prefix will now be less than the sum of suffix). The answer is the minimum absolute value of both cases.
It should be a1 + ⋯ + ai ≤ ai+1 + ⋯ + an because we want to minimize the difference.
cry
(ignore the formatting)
ahh oops, thanks for letting me know
Can't understood editorial solution for G2
G2 can also be solved using sqrt decomposition in $$$O(Q*N/B*log(B))$$$ where $$$B=\sqrt{N}$$$.
For each query, maintain the answer from left to right. If the current minimum is greater than the current block's minimum, we can use a binary search to find where the current block's first minimum is.
Submission: 279662760
Can we use ternary search at the problem E, though we need to find the minimum here?
We can.
Submission: 279662737
yes. It is more intuitive to me.
I have applied ternary search during the contest but got wrong answer. could you help me finding the problem.
Submission: https://codeforces.me/contest/2009/submission/279581586
anyone mind to explain solutions of G3?
i wrote a really long solution as you can see above in the editorial :(
Any specific queries in it?
Can someone suggest a testcase where this will fail for C? It fails on testcase 2.
wrong answer 862nd numbers differ — expected: '2', found: '1'
Cannot compare x and y. You should compare ceil(x/k) and ceil(y/k) instead.
Countercase: x=9, y=8, k=3. Your solution prints 5 but correct answer is 6
thanks for this case!
279728269
can someone pls tell me why is this failing
The solution to A talks about choosing c and then talks about "distance".
The solution to Problem D doesn't even mention (let alone prove/sketch) that the mentioned right-angled triangles are the only ones.
Thats because people who read the editorial for A and people who read editorial to D are different audiences. Obviously more experienced people need less intermediate steps to understand a solution. Look at any div 1 F solution and see how fast paced they are.
I remember the general guidelines is to keep solution to every problem approximately equal lemgth.
What? My objection to A was not that it had too much fluff, but that it makes absolutely no sense.
You can just say that G3 is range sum of history sum(
last 3 problems G123 were actually suitable Div2DEF I think since many red & orange people couldn't solve G23.
As G2/G3 have been discussed above, I’ll just say G1 is absolutely not a div2 D.
you mean too hard to belong div2 D right?
No, I think it’s too easy.
agree, D2C at most
although G2 is definitely harder than my normal encounter of D2D lmao
Why my C wrong? 279562541
this is code of frog jumping problem c of 971 what is wrong with this code ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
include
using namespace std; int main() { int t=0; cin>>t; while(t--){ int x,y,k,ans,d=0; cin>>x>>y>>k; if(x<=y){
if(y%k!=0){ d=d+1;} ans=2*d; } else if(x>y){ d=x/k; if(x%k!=0){d=d+1;} if((d-1)*k>y){ans=2*d-1;} else{ans=2*d;}
} cout<<ans<<endl;
} return 0; ~~~~~~~~~~~~~~~~~~~~~~~~~
Nice div3 so im sad for urt
My submission to problem E was exactly the bonus solution mentioned in the editorial. I spent around 1 hour debugging during the contest but the last sample case was failing. After the contest I submitted the same solution and it passed. I believe there is some precision bug in Apple clang. Can anyone else try this on the last sample test?
** Please ignore the excessive use of long double. I was getting panicked :) **
facing same issue on the last sample
https://codeforces.me/contest/2009/submission/279739052
pls highlight the error in my code
In D, how do we prove that there will be no other cases? Also, can someone share how did they arrive at those 3 points (last case)?
I eventually realized that those 3 points made a right triangle during contest, but it took me a long time.
in all other cases one angle will become obtuse :)
Hi guys I'm new here. When a solution is provided in C++ does that imply that the time constraint for the problem is not achievable using a language like python?
No
Thanks.
firefly queries(f)
can anyone check the error in my code
getting output: wrong answer 247th numbers differ — expected: '4', found: '-165885590936472'
which problem ?
why does this not work for C
Great problems G1,G2,G3! It's nice to have bonus educational problems like these, although I feel like these problems could've also been placed in a div 3 round, since more higher rated participants take part in div 3 rounds than div 4.
kindly explain quadratic eq approach to E
The function that we're minimizing is abs(quadratic). Imagine the graph of a quadratic — on taking absolute value, the part below x-axis goes above x-axis. Now, the minima occurs at one of the roots, because everything else is positive. Graph is symmetric around both roots, so we need to check one of them only.
However, the root may not be an integer. Say, the root of our quadratic is equal to 1.22. You need to check at both 1 and 2 for minima because your range, in this question, is integers only. That is why he takes min(f(i), f(i+1)). At least, this is my understanding of the solution.
I am also trying the quadratic formula method but can't find what I am missing. Can anyone point out what I am doing wrong 279810011
an anyone explain why from here ∑rj=l+k−1f([al,al+1,…,aj]). we can associate to here Let ci=f([ai,...,ai+k−1]). ∑r−k+1j=l(minji=lci)
I mean supposed we caculate the answer for interval [l, l+k] then if we take min(c[l], c[l+1]), it could be smaller than the answer. For example: [l, l+k] is already consecutive, so the answer for it would be k+1, but if we take min(c[l], c[l+1]), it will be only k.
Nevermind. Understood
1 2 2 1 3 2 1 2
Is this a valid test for G1?
Can someone help me with problem E
how is
val1
in the solution equal to(mid+k-1+k)*mid//2 ?
from what I understand
val1
is thesum of integers from k->k+mid
, and for that I did this,this is where I arrive at and cant relate this with how the equation from the solution came
I think I found a mistake on problem D. My intuition is that there exists a Pythagorean Triplet (a, b, c) such that a belongs to triplet (m, n, a), and b also belongs to triplet (x, y, b). It is proven that such triplet exists. For example, (15, 20, 25), where 15 is also a hypotenuse of (9, 12, 15), and 20 is also a hypotenuse of (12, 16, 20). Then I drew these three triangles and got five points: (0,0), (0,12), (25,12), (25,0), and (9,0). It can be shown that there exists 7 right triangles among these 5 points, however, the answer given by the solution is 6. This is because the solution did not count the triangle (15, 20, 25).
I just realized a mistake, I forgot the y value is between 0 and 1.
Dominater069 Test cases of Problem G3 are too weak.
In problem G2 binary lifting solution, what does
w(h, i)
mean?why my solution in G1 wrong :<. my solution did i forgot to reset something?
check mine out, maybe you can figure out what's wrong (the one i submitted during contest)
Hi folks,
I'm trying to solve 971, task D.
for this example
9 1 0 2 0 3 0 4 0 5 0 2 1 7 1 8 1 9 1
I get answer 9, but the task output says it should be 8. Can you confirm if the answer is really 8?
...and if the answer is really 9, how did over 5200 people solved an unsolvable task? Hmmm.... :)
I got it. It is 8 indeed.
G3 binary lifting almost the same as G2.
Why one code is giving TLE other not can anyone explain advance thanks
Both code are same only changes in if codition if (mp.find(a[j]-j)!= mp.end()&&st.count(mp[a[j]-j]) != 0) { st.erase(st.find(mp[a[j]-j])); } other: if (mp[a[j] — j] > 0) { st.erase(st.find(mp[a[j] — j])); }
Can someone please explain problem F? I can't understand the editorial.
Anyone facing issues viewing their submissions? Whenever I click on my submission to check test results I get 403 Forbidden error.
I have an easier way to solve D with an array and 2 for. Here is my submission 279941542
Can anyone kindly tell why this approach is wrong towards E- KLee's super duper large array submission
I am starting from k and ending at n+k-1 as my high. Then for each mid value, i am finding the prefix sum till that and suffix sum and finding absolute difference. Whichever gives us minimum is the answer.
change
if(tillmid<=mid1&&tillmid<=mid2){
cout<<tillmid<<endl;
return;
}
The Solution of E written by the mathematical method is so beautiful. Thoroughly calculate the sum function of |a1+a2+...-an| , then find the zero position for this sum function, awesome math!
In fact, I built a tree to solve G2.
First, just like G1, I worked out the $$$f([a_i,a_{i+1},\cdots,a_{i+k-1}])$$$ for all $$$i$$$ such that $$$1\leqslant i\leqslant n-k+1$$$, then let $$$w_i = f([a_i,a_{i+1},\cdot,a_{i+k-1}])$$$.
Link an edge $$$i \xrightarrow{w_i\times(j-i)} j$$$, such that $$$j$$$ is the minimum that satisfies $$$j > i$$$, $$$w_j < w_i$$$ (if such $$$j$$$ doesn't exist, then let $$$j\leftarrow n-k+2$$$).
It can simply prove that these edges consitute a tree, and the root of tree is $$$n-k+2$$$.
Let $$$dis_i$$$ denote the distance from $$$i$$$ to the root.
When querying $$$[l, r]$$$, we need to do a binary search to find the shallowest $$$p$$$, such that $$$p$$$ is an ancestor of $$$l$$$ and $$$p \leq r-k+1$$$. Therefore, the answer is $$$dis_l - dis_p + w_p \times (r - k + 1 - p + 1)$$$.
This algorithm runs within $$$O(\log^2 n)$$$ time for each query. (if you use the "longest chain separation" to calculate the k-th ancestor within $$$O(1)$$$ time, it can be optimized to $$$O(\log n)$$$)
You can find my code here: https://codeforces.me/contest/2009/submission/279915573.
But now I have difficulties in using the same thought to solve G3.
Please help me. Thanks a lot.
Can someone explain why my submission is giving wrong answer?
Can someone explain the bonus solution of problem E
https://codeforces.me/contest/2009/submission/280117676 can anyone help me with this java code.. why it is wrong?? this is G1
Can anyone state the approach for O(1) solution for E?
can someone explain the lazy segtree solution for G2 in more detail please?
Gif in D singlehandedly lowered the rating by 200pts
Help! with problem C. why if x=8, y=0, k=2 there should be 7 steps and not 8 steps it would take to get from 0,0 to 8,0. please explain....
G2 can also be solved offline without lazy segment tree using prefix sum and binary search
281048790
G2 can be solved online, actually, using just a regular segment tree, prefix sums, and binary search. The idea is to first precalculate the array of $$$c_i$$$ as described by the editorial, then assign each node to handle a range of $$$c_i$$$:
https://codeforces.me/contest/2009/submission/282626136
Can someone please look what might be the issue in my implementation for G1.
https://codeforces.me/contest/2009/submission/281136208
problem C, test 1 : ans = 7 is min
how to do 2009E in C++ please
How do you solve F using bitmask?