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
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!
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
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)
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
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
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 minimum selected are both 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?
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.
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
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
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?