Problem Credits: cry
Analysis: cry
If $$$n$$$ is a multiple of $$$4$$$, then you can have $$$\frac{n}{4}$$$ cows. Otherwise, you must have at least one chicken, so you can have $$$\frac{n-2}{4}$$$ cows and $$$1$$$ chicken.
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int tc;
cin >> tc;
while (tc--){
int n;
cin >> n;
cout << (n + 2) / 4 << "\n";
}
}
Problem Credits: sum
Analysis: cry
Let's define every $$$k$$$ by $$$k$$$ block of cells by its value in the top left corner, since all cells in the block must have the same value. So, we can just print out the value of the cell in every $$$k$$$'th row and every $$$k$$$'th column.
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int tc;
cin >> tc;
while (tc--){
int n, k;
cin >> n >> k;
char A[n][n];
for (auto &row : A)
for (char &c : row)
cin >> c;
for (int i = 0; i < n; i += k){
for (int j = 0; j < n; j += k){
cout << A[i][j];
}
cout << "\n";
}
}
}
Problem Credits: cry
Analysis: cry
For two strings to be the same after sorting, they must have the same occurrences of every possible lowercase letter. To answer the query for a range $$$[l, r]$$$, we must ensure that after the operations, $$$cnt_c = cnt2_c$$$ must where $$$cnt_c$$$ is the number of times character $$$c$$$ occurs in the range for $$$a$$$ and $$$cnt2_c$$$ is defined similarly for $$$b$$$. Both $$$cnt_c$$$ and $$$cnt2_c$$$ can be obtained by doing prefix sums for character $$$c$$$ specifically. Note that since there are only $$$26$$$ possible $$$c$$$, you can afford to create $$$26$$$ length $$$n$$$ prefix sum arrays.
In one operation, you can replace one occurrence of a character $$$c$$$ with another character $$$c2$$$. Essentially, you are subtracting one from $$$cnt_c$$$ and adding one to $$$cnt_{c2}$$$. Obviously, you must choose $$$c$$$ and $$$c2$$$ such that $$$cnt_c > cnt2_c$$$ and $$$cnt_{c2} < cnt2_{c2}$$$. So, we only have to focus on $$$c$$$ or $$$c2$$$ since one decreasing will automatically lead to the other increase. The answer is just the sum of $$$cnt_c - cnt2_c$$$ if $$$cnt_c > cnt2_c$$$ over all possible lowercase characters $$$c$$$.
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n, q;
cin >> n >> q;
vector<vector<int>> pre1(n + 1, vector<int>(26, 0));
vector<vector<int>> pre2(n + 1, vector<int>(26, 0));
for (int i = 1; i <= n; i++){
char c;
cin >> c;
pre1[i][c - 'a']++;
for (int j = 0; j < 26; j++)
pre1[i][j] += pre1[i - 1][j];
}
for (int i = 1; i <= n; i++){
char c;
cin >> c;
pre2[i][c - 'a']++;
for (int j = 0; j < 26; j++)
pre2[i][j] += pre2[i - 1][j];
}
while (q--){
int l, r;
cin >> l >> r;
int dif = 0;
for (int c = 0; c < 26; c++){
int v1 = pre1[r][c] - pre1[l - 1][c];
int v2 = pre2[r][c] - pre2[l - 1][c];
dif += abs(v1 - v2);
}
cout << dif / 2 << "\n";
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int tc;
cin >> tc;
while (tc--)
solve();
}
Problem Credits: sum
Analysis: cry
There are several solutions to this problem, The easiest way is to just fix either $$$a$$$, $$$b$$$ or $$$c$$$. Let's fix $$$a$$$. Since $$$ab + ac + bc \leq n$$$, we know at the minimum, $$$ab \leq n$$$. Divide on both sides to get $$$b \leq \frac{n}{a}$$$. When $$$a = 1$$$, there are $$$n$$$ choices for $$$b$$$. When $$$a = 2$$$, there are $$$\frac{n}{2}$$$ choices for $$$b$$$. So in total, there are $$$n + \frac{n}{2} + \frac{n}{3} + ... + \frac{n}{n}$$$ total choices for $$$b$$$. This is just the harmonic series, so over all possible $$$a$$$, there are about $$$n \log n$$$ choices for $$$b$$$. Therefore, we can afford to loop through both $$$a$$$ and $$$b$$$.
Now that we have $$$a$$$ and $$$b$$$, all that's left is to solve for $$$c$$$. Let's solve for $$$c$$$ in both equations. In the first equation, we can factor $$$c$$$ out to obtain $$$ab + c(a+b) \leq n$$$. So, $$$c \leq \frac{n-ab}{a+b}$$$. In the second equation, $$$c \leq x - a - b$$$. Since we want the $$$c$$$ to satisfy both inequalities, we must choose the stricter one. So, the number of possible $$$c$$$ is $$$\min(\frac{n-ab}{a+b},x-a-b)$$$.
The answer is the sum of number of possible $$$c$$$ over all possible $$$a$$$ and $$$b$$$.
#include <bits/stdc++.h>
using namespace std;
int main(){
int tc;
cin >> tc;
while (tc--){
int n, x;
cin >> n >> x;
long long ans = 0;
for (int a = 1; a <= min(n, x); a++){
for (int b = 1; a * b <= n and a + b <= x; b++){
int highestC = min((n - a * b) / (a + b), x - (a + b));
ans += highestC;
}
}
cout << ans << "\n";
}
}
Problem Credits: cry
Analysis: cry
How can we efficiently check if a range contains the same amount of zeroes and ones? Let's create an array $$$a$$$ where $$$a_i = -1$$$ if $$$s_i = 0$$$ and $$$a_i = 1$$$ if $$$s_i = 1$$$. Let's denote $$$p$$$ as the prefix sum array of $$$a$$$. We want the contribution of $$$-1$$$ by the zeroes to cancel out with the ones, so if $$$p_r - p_{l-1} = 0$$$, then the range $$$[l, r]$$$ contain equal amounts of zeroes and ones. We can rephrase the problem as the following: for each subrange $$$[l, r]$$$, count the number of pairs $$$(x,y)$$$ such that $$$p_{x-1} = p_y$$$.
Let's fix $$$p_{x-1}$$$ and keep track of all potential $$$y$$$ such that $$$y > x$$$ and $$$p_{x-1} = p_{y}$$$. How many subarrays will cover $$$[x, y]$$$? Well, we have $$$x+1$$$ options as $$$l$$$ and $$$n-y+1$$$ options as $$$r$$$, so the range $$$[x,y]$$$ contributes to $$$(x+1) \cdot (n-y+1)$$$ subarrays. We just need to calculate this expression for all potential $$$y$$$ now. Let's denote the all possible $$$y$$$ as $$$y_1, y_2, ... y_k$$$. We are asked to find the sum of $$$(x+1) \cdot (n-y_1+1) + (x+1) \cdot (n-y_2+1) + \dots + (x+1) \cdot (n-y_k+1)$$$. Let's factor $$$(x+1)$$$ out, and we have $$$(x+1) \cdot ((n-y_1+1)+(n-y_2+1)+\dots+(n-y_k+1))$$$. Since, the second part of the expression is just the sum of all $$$(n-y_i+1)$$$, we can first precalculate that sum and since $$$y > x$$$, subtract as we sweep from left to right.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;
template<ll M>
struct modint {
static ll _pow(ll n, ll k) {
ll r = 1;
for (; k > 0; k >>= 1, n = (n*n)%M)
if (k&1) r = (r*n)%M;
return r;
}
ll v; modint(ll n = 0) : v(n%M) { v += (M&(0-(v<0))); }
friend string to_string(const modint n) { return to_string(n.v); }
friend istream& operator>>(istream& i, modint& n) { return i >> n.v; }
friend ostream& operator<<(ostream& o, const modint n) { return o << n.v; }
template<typename T> explicit operator T() { return T(v); }
friend bool operator==(const modint n, const modint m) { return n.v == m.v; }
friend bool operator!=(const modint n, const modint m) { return n.v != m.v; }
friend bool operator<(const modint n, const modint m) { return n.v < m.v; }
friend bool operator<=(const modint n, const modint m) { return n.v <= m.v; }
friend bool operator>(const modint n, const modint m) { return n.v > m.v; }
friend bool operator>=(const modint n, const modint m) { return n.v >= m.v; }
modint& operator+=(const modint n) { v += n.v; v -= (M&(0-(v>=M))); return *this; }
modint& operator-=(const modint n) { v -= n.v; v += (M&(0-(v<0))); return *this; }
modint& operator*=(const modint n) { v = (v*n.v)%M; return *this; }
modint& operator/=(const modint n) { v = (v*_pow(n.v, M-2))%M; return *this; }
friend modint operator+(const modint n, const modint m) { return modint(n) += m; }
friend modint operator-(const modint n, const modint m) { return modint(n) -= m; }
friend modint operator*(const modint n, const modint m) { return modint(n) *= m; }
friend modint operator/(const modint n, const modint m) { return modint(n) /= m; }
modint& operator++() { return *this += 1; }
modint& operator--() { return *this -= 1; }
modint operator++(int) { modint t = *this; return *this += 1, t; }
modint operator--(int) { modint t = *this; return *this -= 1, t; }
modint operator+() { return *this; }
modint operator-() { return modint(0) -= *this; }
modint pow(const ll k) const {
return k < 0 ? _pow(v, M-1-(-k%(M-1))) : _pow(v, k);
}
modint inv() const { return _pow(v, M-2); }
};
using mint = modint<int(MOD)>;
int main(){
int t; cin >> t;
while(t--){
string s; cin >> s;
int n = s.size();
vector<int> p(n+1);
for(int i = 1; i <= n; i++){
p[i] = p[i-1] + (s[i-1] == '0' ? -1 : 1);
}
vector<vector<ll>> sums(2 * n + 1);
for(int i = 0; i <= n; i++){
sums[p[i] + n].push_back(i);
}
mint ans = 0;
for(auto& v: sums){
int N = v.size();
vector<ll> j_sum(N+1);
for(int i = N - 1; i >= 0; i--){
j_sum[i] = j_sum[i+1] + v[i];
}
for(int i = 0; i < N - 1; i++){
ll left = N - i - 1;
ans += v[i] * n * left;
ans -= v[i] * j_sum[i+1];
ans += v[i] * left;
ans += n * left;
ans -= j_sum[i+1];
ans += left;
}
}
cout << ans << "\n";
}
}
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MOD = 1e9 + 7;
void solve(){
string S;
cin >> S;
int n = S.size();
S = " " + S;
vector<int> P(n + 1, 0);
for (int i = 1; i <= n; i++){
P[i] = (S[i] == '1' ? 1 : -1) + P[i - 1];
}
map<int, ll> cnt;
ll ans = 0;
for (int i = 0; i <= n; i++){
ans = (ans + (n - i + 1) * cnt[P[i]]) % MOD;
cnt[P[i]] = (cnt[P[i]] + (i + 1)) % MOD;
}
cout << ans << "\n";
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int tc;
cin >> tc;
while (tc--)
solve();
}
Problem Credits: sum
Analysis: cry
Let's first solve the problem in $$$\mathcal{O}(k)$$$. One possible solution is to loop through each operation and take the largest $$$a_i$$$ each time, and set $$$a_i = \max(0, a_i - b_i)$$$. This can be done with a set or a priority queue.
With that in mind, let's binary search for the largest $$$x$$$ such that every value we add to our score has been greater or equal to $$$x$$$ for all $$$k$$$ operations. Define $$$f(x)$$$ as the number of operations required for every $$$a_i$$$ to be less than $$$x$$$. Specifically, $$$f(x) = \sum_{i=1}^n \lceil \frac{a_i-x}{b_i} \rceil$$$. We are searching for the smallest $$$x$$$ such that $$$f(x) \leq k$$$. Once we've found $$$x$$$, we can subtract $$$f(x)$$$ from $$$k$$$. Note that now, $$$k$$$ must be less than to $$$n$$$ (otherwise we can another operation on all $$$a_i$$$). So, it suffices to run the slow solution for these remaining operations (as long as $$$a_i > 0$$$). Alternatively, we can notice that the remaining operations will all add $$$x-1$$$ to our answer (assuming $$$x > 0$$$).
To obtain the sum of all $$$a_i$$$ we collected when calculating $$$f(x)$$$, we can use the arithmetic sequence sum formula. For each $$$i$$$, the number of terms in the sequence is $$$t = \lceil \frac{a_i-x}{b_i} \rceil$$$. The first term of the sequence is $$$f = a_i - b_i \cdot (t-1)$$$. The last term is $$$a_i$$$. Using the formula, we can add $$$\frac{t}{2}(f+a_i)$$$ to the answer.
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
vector<int> a(n), b(n);
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> b[i];
int ok = 0, ng = 1e9+1;
while (ng - ok > 1) {
int mid = (ok + ng) / 2;
long long sum = 0;
for (int i = 0; i < n; i++) {
if (a[i] >= mid)
sum += (a[i] - mid) / b[i] + 1;
}
if (sum >= k) ok = mid;
else ng = mid;
}
long long ans = 0;
int s = 0;
for (int i = 0; i < n; i++) {
if (a[i] >= ok) {
int m = (a[i] - ok) / b[i] + 1;
ans += 1LL * m * a[i] - 1LL * m * (m - 1) / 2 * b[i];
s += m;
}
}
ans -= 1LL * ok * (s - k);
cout << ans << "\n";
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
int n, k;
cin >> n >> k;
vector<int> A(n), B(n);
for (int &i : A)
cin >> i;
for (int &i : B)
cin >> i;
auto getInfo = [&](int cutoff){
ll ops = 0;
ll sum = 0;
for (int i = 0; i < n; i++){
ll a = A[i];
ll b = B[i];
if (cutoff > a)
continue;
// a - uses * b >= cutoff
ll uses = (a - cutoff) / b;
sum += (uses + 1) * a - b * uses * (uses + 1) / 2;
ops += uses + 1;
sum = min(sum, 2 * (ll)1e18);
}
return make_pair(sum, ops);
};
int L = 0, H = 1e9 + 5;
while (L < H){
int M = (L + H) / 2;
getInfo(M).second <= k ? H = M : L = M + 1;
}
auto [ans, opsUse] = getInfo(L);
cout << ans + (k - opsUse) * max(L - 1, 0) << "\n";
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int tc;
cin >> tc;
while (tc--)
solve();
}
Problem Credits: cry
Analysis: cry, awesomeguy856
There are two configurations to satisfy every friendship $$$(a, b)$$$: activate all the roads from $$$a \rightarrow a+1 \rightarrow \dots \rightarrow b$$$ or $$$b \leftarrow \dots \leftarrow n \leftarrow 1 \leftarrow \dots \leftarrow a$$$. Let's fix a road we deactivate. Say it goes from $$$i \rightarrow i+1$$$. Observe that the configuration for all friendships is fixed to one of the two cases. For example, if $$$a \leq i < b$$$, then we must use the second configuration.
We can try fixing every road and taking the minimum of number of roads. This can be done with sweep line. Once we reach $$$i = a$$$ for any friendship, we toggle to the second configuration. Once we reach $$$b$$$, we toggle back to the first. We can track maintained roads by performing a range addition on a lazy propagated segment tree for each point covered by the current configuration. The number of roads required is $$$n$$$ minus the number of occurrences of zeroes in the segment tree, which can be tracked with Counting Minimums in a Segment Tree.
#include <bits/stdc++.h>
using namespace std;
class LazySegmentTree {
struct Node {
int min_val;
int count;
int lazy;
};
std::vector<Node> tree;
int n;
void buildTree(int v, int tl, int tr) {
if (tl == tr) {
tree[v] = {0, 1, 0};
} else {
int tm = (tl + tr) / 2;
buildTree(v*2, tl, tm);
buildTree(v*2+1, tm+1, tr);
merge(v);
}
}
void apply(int v, int tl, int tr, int val) {
tree[v].min_val += val;
tree[v].lazy += val;
}
void push(int v, int tl, int tr) {
if (tree[v].lazy != 0) {
int tm = (tl + tr) / 2;
apply(v*2, tl, tm, tree[v].lazy);
apply(v*2+1, tm+1, tr, tree[v].lazy);
tree[v].lazy = 0;
}
}
void merge(int v) {
if (tree[v*2].min_val < tree[v*2+1].min_val) {
tree[v].min_val = tree[v*2].min_val;
tree[v].count = tree[v*2].count;
} else if (tree[v*2].min_val > tree[v*2+1].min_val) {
tree[v].min_val = tree[v*2+1].min_val;
tree[v].count = tree[v*2+1].count;
} else {
tree[v].min_val = tree[v*2].min_val;
tree[v].count = tree[v*2].count + tree[v*2+1].count;
}
}
void updateRange(int v, int tl, int tr, int l, int r, int addend) {
if (l > r) return;
if (l == tl && r == tr) {
apply(v, tl, tr, addend);
} else {
push(v, tl, tr);
int tm = (tl + tr) / 2;
updateRange(v*2, tl, tm, l, std::min(r, tm), addend);
updateRange(v*2+1, tm+1, tr, std::max(l, tm+1), r, addend);
merge(v);
}
}
std::pair<int, int> queryRange(int v, int tl, int tr, int l, int r) {
if (l > r) return {INT_MAX, 0};
if (l <= tl && tr <= r) {
return {tree[v].min_val, tree[v].count};
}
push(v, tl, tr);
int tm = (tl + tr) / 2;
auto left = queryRange(v*2, tl, tm, l, std::min(r, tm));
auto right = queryRange(v*2+1, tm+1, tr, std::max(l, tm+1), r);
if (left.first < right.first) {
return left;
} else if (left.first > right.first) {
return right;
} else {
return {left.first, left.second + right.second};
}
}
public:
LazySegmentTree(int _n) {
n = _n;
tree.resize(4*n);
buildTree(1, 0, n-1);
}
void updateRange(int l, int r, int addend) {
updateRange(1, 0, n-1, l, r, addend);
}
std::pair<int, int> queryRange(int l, int r) {
return queryRange(1, 0, n-1, l, r);
}
int get_maintained(){
pair<int, int> res = queryRange(0, n-1);
assert(res.first == 0);
return n - res.second;
};
};
void solve() {
int n, m; cin >> n >> m;
vector<pair<int, int>> p(m);
for(int i = 0; i < m; i++){
cin >> p[i].first >> p[i].second;
p[i].first--; p[i].second--;
}
LazySegmentTree st(n);
for(pair<int, int> i: p){
st.updateRange(i.first, i.second - 1, 1);
}
int ans = st.get_maintained();
vector<vector<int>> start(n), end(n);
for(int i = 0; i < m; i++){
start[p[i].first].push_back(i);
end[p[i].second].push_back(i);
}
for(int i = 0; i < n; i++){
for(int j: start[i]){
st.updateRange(p[j].first, p[j].second - 1, -1);
st.updateRange(p[j].second, n - 1, 1);
st.updateRange(0, p[j].first - 1, 1);
}
for(int j: end[i]){
st.updateRange(p[j].second, n - 1, -1);
st.updateRange(0, p[j].first - 1, -1);
st.updateRange(p[j].first, p[j].second - 1, 1);
}
ans = min(ans, st.get_maintained());
}
cout << ans << "\n";
}
signed main() {
int t = 1;
cin >> t;
for(int test = 1; test <= t; test++){
solve();
}
}
/* /\_/\
* (= ._.)
* / > \>
*/
Consider the $$$n$$$-gon formed by the houses, with each road becoming an edge of the polygon. We draw diagonals between houses if they are friends. Let each diagonal arbitrarily "cover" one side of the polygon, where every road contained within one section split by the diagonal is covered by the diagonal.
We claim that two roads can both be deleted if and only if they are covered by the same set of diagonals. First, this is equivalent to saying that when we draw a line between these two roads, they do not intersect any of our drawn diagonals. (This is since if any diagonal covers one road and not another, then they must be on opposite sides of the diagonal, so drawing a line between the two roads must intersect that diagonal. The converse also holds.)
Now note that if two roads are on opposite sides of a diagonal, they cannot both be deleted, as then there is no path along maintained roads that connects the two endpoints of the diagonals, or the two houses that are friends.
So it suffices to count the most frequent set of covered diagonals over all roads.
We can represent a diagonal cover for some road using a xor hashing, where each diagonal is assigned a random number, and the roads that are covered by that diagonal are xor'd by this number.
By using $$$64$$$-bit integers, the probability of collision is negligible, as each 64-bit integer has equal probability of representing a unique set of diagonals, and we have at most $$$n$$$ represented sets.
For each pair of friends, we want to xor all values in a range by some random number. This can be done with a prefix xor array in $$$\mathcal{O}(1)$$$ per pair of friends. Counting the most frequent value at the end will take $$$\mathcal{O}(n \log n)$$$ time if a map is used or $$$\mathcal{O}(n)$$$ if an unordered map is used. In all, this solution runs in $$$\mathcal{O}(n \log n + m)$$$ or $$$\mathcal{O}(n + m)$$$ time.
#include <bits/stdc++.h>
#define int long long
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int n,m,a,b,k,t;
void solve() {
cin >> n >> m;
vector<int> v(n);
while (m--) {
k=rng(); cin >> a >> b;
v[a-1]^=k;
v[b-1]^=k;
}
map<int,int> c;
for (int r:v) m=max(m,c[a^=r]++);
cout << n-m-1 << "\n";
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> t;
while (t--) solve();
}
cry orz
Couldn't solve D. RIP my brute force skill.
orz
orz
orz kill me i cant do F
orz I also.
i almost finished on it but then time was up, man what a mess ive done
also i was 30' late for the contest so screw me >:(((
Oh and I thought when I was seeing the standings As this was not rated for you. You found it too much of a hassle to code XD
It was math skills ig
orz
Same here
D seemed really hard. I couldn't do it either. E was nice, though.
awesomeguy856 orz
omeganot orz
what is 'orz'?
its a slang expression used to show admiration or respect for someone's skills, It originated from an emoticon representing a person bowing down in respect.
It looks like a men keening down,to showbadmiration to someone
Badmiration. You just discovered a new word.
its always hard to spell word on cellphone
yuka pls dont hit me
Same as 'sto'
is awesomeguy856 a guy?
no
After reading problem F You realize that nuclear bombs take so much time to bomb!
sadly this is not the case in palestine!
You think that's funny to say, you dumfuk?
This is because all of 1,000 nuclear bombs are false and Sparkle-sama only want to fool you, haha.
orz
G reminds me of this JOISC problem
I created video editorial for G: Penacony
thnx
They have the same setting, but the JOISC problem is much harder
In problem F: We are searching for the largest x such that f(x)≤k
Won't we reach infinity by doing that?
$$$x$$$ can't be larger then maximum element of array a.
fixed
My solution for problem F:
let's find the minimum number
X
, whereX
is the smallest number that all numbers in arraya
can be less or equal than using at mostk
operations.then, you calculate the answer for making all the numbers in
a
less thanX
, and maintain valuesk
anda[i]
for eachi
.After all you will be left with
k
operations, so you add to the answer :number_in_a_equal_X * k
link to my solution
isn't that the same solution as mentioned in the editorial?
oh, ohk i get it, you sped up the last part of solution by doing
number_in_a_equal_X * k
. That's good.Amazing xor-hashing solution for G, love it!
great contest, really fun problems. i wish i managed to solve E on time as well but oh well
Can anybody tell why this solution for C is getting MLE?
Submission
You use map. Try replacing it with arrays and you'll be fine.
yeah I also used a hashmap, but why would arrays be faster? I thought Hmaps had O(1) look up. Unless I'm misunderstanding smth
STL Map has O(nlgn)
Oh I use Python, is the python dict also O(nlogn)?
please can anyone explain why my code works or if it can get hacked please hack it : ), i will be so happy (https://mirror.codeforces.com/contest/1996/submission/272827778)
I think it can't be hacked because worst case I found O(2 * 10^9) , and it's fast enough for your code to pass because the operations sums and multiply aren't that heavy.
If in the same code we replace int by long long, it gives tle on the first test case itself. Why is this the case?
Arithmetic of long long (64 bits) is slower than int (32 bits)
Can anyone explain how this code works? I don't understand it. Also, can you provide some sources that explain how it works? Thanks! 272756177
brother can u explain my code please : )
cry sum Is there a penalty on unsuccessful hacking attempt?
no
Thank you for the editorial ! There is just a little typo in the explanation of problem E. You wrote in the line before the last one $$$(x+1) \cdot ((n-y_1+1) + (n-y_2+2) + ... + (n-y_k+1))$$$. It shouldn't be $$$n-y_2+2$$$ but $$$n-y_2+1$$$
thanks sir
Solved ABCD, hope to become pupil
Congrats!
thx
O(n) solution of D :
wlog assume a <= b <= c
claim : atleast a, b <= √n
proof : if b > √n, b * c >= b * b > n which proves the claim so iterate on a and b till √n and count the permutations, this can be done in many ways
submission
Why will the "remaining operations will all add (x — 1)" in the solution for F?
We know that there must be at least one element that is x-1, because otherwise it's clearly not the smallest x. Then, if there are less (x-1)'s than there are operations left, you could perform operations on those elements, and thus this not the smallest x. But if there were more (x-1)'s than operations left, then the they would all be (x-1).
Let us note that $$$f(x - 1) - f(x)$$$ will mean how many element can start from $$$x - 1$$$ [check the last paragraph], because an increase in count between consecutive arguments can only occur if the smaller one is having some elements start for that argument,
If x is the smallest value for which our $$$f(x)$$$ is $$$\leq k$$$, means $$$f(x - 1) > k$$$. This means that $$$f(x - 1) - f(x)$$$ number of elements have started from $$$x - 1$$$. We have $$$k - f(x) < f(x - 1) - f(x)$$$. Therefore the number of elements which will start from $$$x - 1$$$ is larger than the leftover operations.
By elements starting from a number, I mean lets say $$$a_i$$$ = 7 and $$$b_i$$$ = 4, and $$$x$$$ = 4, then the AP of elements we can pull from this index is 7. Hence this element "starts from" 7. Also, within this example, consider what happens when $$$x$$$ = 3 (instead of 4), the AP of elements we pull is 7, 3. There is an increase in count from 1 to pulling 2 elements, and this change occurred because an element started from 3, (this 3 will not be pulled from this index if our $$$x$$$ is 4, but it will be ready to be pulled from the leftover operations).
DIV 3 — C
Easiest python implementation using 26 cross n array:
272842563
can anyone please explain me the editorial of Problem D "Since ab+ac+bc≤n , we know at the minimum, ab≤n . " or is their any other approach please share
The constraint ab + ac + bc ≤ n implies that individually, each pairwise product should also be less than or equal to n . Thus, we know that:
ab ≤ n , ac ≤ n , bc ≤ n
Okay thank you
Did some people really did 4th one with brute force??
yes
Why I'm Getting TLE 272870887 (problem C).
switching to PyPy 3-64 fixed.
Great contest :) Hope to regain pupil title.
My math ain't mathing for D :( . What a mathy math
Anyone tried G with greedy then use segment tree? Like sort or pair by ascending order of min(b-a, n+a-b), assume a<b, then tried to input range [a,b] or [b,n],[1,a] to find which one is minimum. I do not know whether is works, as I tried sometimes but fail
Would a Randomizing Approach work for G? If you choose which edge to be deleted first there will be only one path which makes it clear which edges to remove after. Would randomly choosing the first edge to be deleted solve the problem (Assuming you only randomly choose from valid edges to be removed)? Too lazy to try coding it.
no, consider the case where every adjacent points are friends except the two. in optimal answer only 2 of the edges can be removed so 2/n probability to choose right one
I was actually thinking of only having the option to remove the edge from points that are not actually friends because it can be proven that either the answer is 1 or at some point you'd remove an edge from points that are not friends, I guess there must be a case that makes it fail but not on the top of my mind.
That was my idea during the contest and it worked. However, I tried all possible edges to remove, not just by random.
in D, it is mentioned in the problem statement that the triplet (a, b, c) are positive numbers, i.e., > 0.
Given
ab+bc+ca <= n
, at minimum,ab+b+a <= n
should be true, sincec>=1
Which impliesb <= (n-a)/(a+1)
, instead ofn/a
as mentioned in the editorial.When I apply these constraints, I get WA on test 2 for an unknown test case. Can someone please explain where I am going wrong ???
272880275 or 272880139
Ooh yes, I get it. I wrote
b+1 < x
instead ofb+a < x
, changing it fixes everything. Thank you so much bhaiya !!Can someone please explain why in problem 1996F - Bomb we need to add exactly (v*(k-all_ops)). In tutorials they just go through it and they don't even explain. I always trying to understand by myself till i'm done but its first time when im asking help(i watched all possible tutorials). My code 272878301 .
I dont understand why we can do it on all values in array, because we always doing ceil and at the end its always <= BS value. So we can do it only on values that are exactly BS value. I mean how do we know that we have exactly (k-all_ops) values with value=v.
I guess there are \textbf{at least} $$$k - all ops$$$ values $$$=v$$$
Like the other guy said, there would be at least k-allops values of v, because otherwise you could use the remaining operations to eliminate v and reach a smaller value in binary search
Check my comment
When we choose a value of x, the total count is less than k. However, when the threshold is set to x-1, the total count exceeds k. So, whenever I choose x, the total count is less than k. Other options always result in (x-1) every time because when we have b=1; b=(a[i]-x)/b[i]+1; we noticed that when we use (x-1), we always get (x-1) every time.
Thank you guys. I guess yesterday was not the day for thinking because i woke up and instantly understood it.
We have function $$$f$$$ . And it gives us number of operations we need to do to get all numbers in array $$$a_{i}<=value$$$ . To do this we need to do binary search to find $$$value$$$ that need $$$f(x)<=k$$$ . Let's say answer to binary search is $$$x$$$ so number before is $$$x-1$$$ . We can see that number of operations that needed to get all numbers $$$<=x$$$ is $$$f(x)$$$ and for $$$<=x-1$$$ it's $$$f(x-1)$$$ . So we can check delta and get how many numbers are exactly $$$x$$$. So the answer will be $$$Min(f(x-1) - f(x)$$$ ,$$$k-f(x))$$$. As we know that $$$k-f(x)$$$ will be less than $$$f(x-1)-f(x)$$$ because $$$k<=f(x-1)$$$ so $$$MaxAdd = (k-f(x))*x$$$.
very very nice explanation <3, I had the same struggle understanding the tutorial
Anyone know any problems similar to D? If so can you recommend. Thanks in advance!
Why is this code not working?
为什么这段代码不起作用?
Почему этот код не работает?
このコードが機能しないのはなぜですか?
272886072
First, don't use
endl
except the case which the problem is interactive problem(you will recieve an unknown verdict when you don't use 'cout.flush()' or sth like that, andendl
will automatically performcout.flush()
). It is very slow.Second, you are outputing too much '\n'(ASCII 10)s. So even you switch it to '\n', you will still recieve a WA verdict.
原来可以写中文的吗(雾)
Yeah, true, but please communicate in ENGLISH.
非常难
笑点解析
orz
gou jiao
我也觉得
Now i can't solve D just because i was thinking too complex... That's funny while I can solve E
Problem A is I think available on USACO guide or somewhere because I have solved same question with same problem statement.
F is equivalent to aliens' trick (A.K.A. wqs's binary search algorithm), for the functions mapping k (the number of operations) to answer (the maximum of sum selected by k operations) is convex.
Problem D provides an O(n) solution where no two numbers in a,b, or c are simultaneously greater than the square root of n, so the two square roots traverse a,b, find c, and then remove the duplicates.
HSR reference in the questions. Am I the only one?
nah ur not the only one :)
For problem G there is an interesting property that if two edges (e.g. $$$(a,b)$$$ and $$$(c,d)$$$) cut with each other, they must connect to each other $$$(a,b,c,d)$$$. So finally we will reach a partition of a circle (here I indicate a partition of a circle means that there do not exist two edges which cut with each other in two complete maps of point sets), and we can find the answer quickly by some simple method.
The problem is how to find the partition of the circle. First, we sort the edges, and then we need to perform a stack of sets which indicates that all the points in a set needs to be connected. We can easily find whether an edge cuts an edge of a set. To lower the time complexity, you will find if we pile the stack by the time we build it, if the edge cuts with one set, all the sets which on the top of this set must cut with this edge. Then just merge the sets by size. The total time complexity is $$$O(n \log n)$$$.
I must mention that I haven't implement this, but I think it is an interesting approach of this problem.
I am not sure if i not getting right what you are saying or your statement is false
here's example for n=15, and 3 edges(1-4,3-6,5-15) according to your statement it should be connected by(1-3-4-5-6-15) but that would not be optimal solution(it should be 15-1-3-4-5-6).
correct me if i am wrong.
It's my bad not make it clear that I mean the points in a set means they should be connected by one path.
In your example, for the edges $$$1-4, 3-6, 5-15$$$, they cut with each other, so they must be connected in a path. Both path $$$1-3-4-5-6-15$$$ and $$$15-1-3-4-5-6$$$ let them connected.
If you still don't understand, you can see that if $$$(a,b)$$$ and $$$(c,d)$$$ cuts, we can add $$$(a,c)$$$, $$$(a,d)$$$, $$$(b,c)$$$, $$$(b,d)$$$ four edges and this does not change the answer, and that is what I mean "they must connect to each other". $$$(a,b,c,d)$$$ can be connected in many ways, like $$$a-b-c-d$$$ or $$$c-d-a-b$$$, but they must be connect by one path.
can anyone help why is this TLE ? problem 1996F - Bomb
I literally cannot imagine edge case, feels like it should work logically
the idea is basically take the max of a[i] until it becomes smaller than second largest a[i] (if it exists)
Your code will TLE in the case like this:
Where $$$n \ge 2$$$, and $$$k$$$ is sth very large.
We have to compress these steps use binary search, then the rest "useful" operation will be at most $$$n$$$.
My thought process for C and D for newbies like me...
C
:)
a hint could have been that it was mentioned only small latin chars
D
;
Didn't understand G's train of thought
Here is the explantion of the solution with segment tree.
So first we have a cycle of $$$N$$$ nodes.
Then, it is obvious that when we force to delete an edge, this cycle will become a chain which can be assumed to be an array.
And we just enumerate the edge we force to delete, then use sth fast to calculate the answer of the unique way to maintain the roads.
And to do this, a segment tree is enough.
I get it, because in the worst case there is a road that doesn't need to be repaired, so it's a matter of enumerating the roads that don't need to be repaired and then using the line segment tree to maintain the rest of the information
In problem F, I want to use slow solution for these remaining operations but get TLE on test 10. May I ask if there is any problem with this code?(https://mirror.codeforces.com/contest/1996/submission/272913613)
your sort in while,it maybe get O(n*nlogn)
your vector "v" assign max value only, multiset or priority_queue useful maybe
272919030
Get it, I mistakenly think that sort can be faster if I only change one of its elements, thanks for your patient assistance!
did anyone write the code for problem C in python. Mine is getting TLE
Code:
u used same i,perhaps because of that ? i usually don't code in python, so is it allowed in python ?
在G题里面,为什么这样的维护道路方案是有效的? 我觉得sort道路长度的顺序应该也是可以的感觉
聪明的你,再想想
我不到啊orz
Problem E: why we have x+1 options as l? I think l should be in a range from 1 to x, then it's x , not x+1
You might forgot the extra option $$$0$$$.
OK
Can anyone tell me how in F. How we came to know that all the remaining operation will add x-1 to the answer
this and above
D was such a head crusher
I am new and i was only able to solve A and B i solved C and F but until i wrote code time was up! Any tips how should i get better?
bro, it was just your first contest , practice more , upsolve after each contest and start learning basics like binary search , prefix sums etc, you will definetaly improve
what is upsolve??
upsolve is basically solving those questions which you were not able to do during the contest, by using any help or looking at others solutions and looking at tutorials , its a great way to improve your cp skills
ok bro thnx
I have no idea how I'm getting a TLE from B. It was initially accepted, but it just got a TLE during the system testing phase. My solution looks similar to the one in the editorial, is there anything that I'm missing?
My submission
Bruteforces
Thanks!
Great tutorial and problem idea for G
D can also be done in a sort of O(n) complexity .
my approach was to deal with any 2 or more are equal in a separate case and all three distinct in a second case
well any 2 or more equal can easily be thought of in O(n) but for all three distinct without loss of generality
let's consider a>b>c
this means ab> c*c , bc > c*c and ac > c*c .
thus 3 * c*c < ab+bc+ac <= n
thus c can take a maximum value till sqrt(n/3) thus we can iterate over it's possible values in o(sqrt(n))
note : one must check if x is less than this sqrt(n) to get a faster code
now having fixed c let's think of b
ab > b*b , ac > bc thus , b*b + 2bc < n
now for each value of c we get an upper bound of b that can be calculated to be of the order of O(sqrt(n)) having fixed any 2 it's easy to calculate the number of possibilites for a
now since we are nesting 2 loops over O(sqrt(n)) the overall complexity would be O(sqrt(n) *sqrt(n))ie O(n)
My implementation : 272824868
why i get wrong answer at test 4 ? 272990203
I am encountering the same problem 273748512 . have you found the solution to it yet?
yes i did not use modular multiplucation and also ans=(ans+k)%mod is different from ans+=k%Mod the last is not correct
There is an error in problem D's editorial i.e there should not be equality in a*b<=n and (a+b)<=x, although it also gets accepted but still this is logically incorrect since a,b,c are all positive numbers
Can someone please explain the difference in use case between the two binary search code?:
VS
I can't understand the thinking of G
It's too hard for me
Was G a standard problem? Could anyone share the standard problem or resource to learn about the idea if it was?
TY in advance.
There's a subroutine used in G which is standard and recently appeared in Atcoder ABC343F : Second Largest Query. I talk more about the idea in this video
It took me 3 video explations for me to understand it, but yours finally made me snapped on the logic of the solution. Thanks a lot!
In Problem F, why is it necessary that if any remaining operations, all those operations add x-1 to the final score? The condition for binary search was to add all scores as long as a[i] >= x, it may be possible that for an a[i] the final value remaining after all those operations is x-1 or x-2 or x-3... What am I missing here?
Problem D is such a low quality problem. I got hacked with verdict TLE but after the system testing I submitted same hacked code and got accepted . I was ranked 444(official) before hacked and finished at 2k+ after hacked . And lost my opportunity to be expert.
All solutions at 19xx/2000ms? No, not a chance that the problem had a bad TL. You were having a suboptimal solution.
$$$\mathcal{O}(n \log^2 n)$$$ time complexity is a very gray zone at $$$n \le 10^6$$$, and in most cases it should have been TLE'd long ago. It was only that this problem involved mostly basic arithmetics and virtually zero memory accesses that the constant factor tipped into your favor (partially).
If I get TLE instantly in my first submission then maybe I could find an optimal solution. Which may guide me to Expert. Actually I am stucked in 1593 max. for a long time. That's why it hurts me a lot
Can anyone explain why when subtracting $$$f(x)$$$ from $$$k$$$, $$$k < n$$$ ?
In problem C, why do we have x + 1 options as 'l' for covering subarray [x, y]. As the array is indexed from 1 shouldn't it be x options?
F is similar to ABC216E.
The ABC problem is a version of $$$b_i=1$$$.
it's so hard
In problem f, how can it be proved that all excess operations over k (s-k) were done with the obtained ok (mid) of the binary search? Specifically how to prove the line, ans -= 1LL * ok * (s — k)
its difficult to understand D
E is a good problem
Can someone pls elaborate this? Not able to grasp this:
So, it suffices to run the slow solution for these remaining operations (as long as ai>0 ). Alternatively, we can notice that the remaining operations will all add x−1 to our answer (assuming x>0 ).
Suppose f(x)<=k where x is the smallest number, then f(x-1)>k. Now why this is happening,you will be able to see that some value will be equal to x-1 and that will increase f(x-1). Now we have some extra move k-f(x) and for all this extra move we will find some x-1 to add in our final solution.
Problem F was nice.
How long have you played Honkai: Star Rail? ww