Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon) 1
#include <bits/stdc++.h>
using namespace std;
int main() {
auto ok = [](string s) {
for (int i = 1; i < (int)s.size(); ++i)
if (s[i - 1] == s[i]) return false;
return true;
};
int t;
cin >> t;
while (t--) {
int n, m;
string s, t;
cin >> n >> m >> s >> t;
bool f = false;
for (int x = 0; x < 2; ++x) {
string cs = s, ct = t;
for (int i = 0; i < n; ++i) {
f |= ok(cs) && ok(ct);
ct.push_back(cs.back());
cs.pop_back();
}
swap(n, m);
swap(s, t);
}
cout << (f ? "YES\n" : "NO\n");
}
}
Solution (Neon) 2
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, m;
string s, t;
cin >> n >> m >> s >> t;
reverse(t.begin(), t.end());
s += t;
int cnt = 0;
for (int i = 1; i < n + m; ++i) cnt += s[i - 1] == s[i];
cout << (cnt <= 1 ? "YES\n" : "NO\n");
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
int L = 0, R = 55;
while (n--) {
int l, r;
cin >> l >> r;
if (l <= k && k <= r)
L = max(L, l), R = min(R, r);
}
cout << (L == R ? "YES\n" : "NO\n");
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
using li = long long;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<li> a(n), b(n);
for (auto& x : a) cin >> x;
for (auto& x : b) cin >> x;
vector<li> sum(n + 1);
for (int i = 0; i < n; ++i) sum[i + 1] = sum[i] + b[i];
vector<li> cnt(n + 1), add(n + 1);
for (int i = 0; i < n; ++i) {
int j = upper_bound(sum.begin(), sum.end(), a[i] + sum[i]) - sum.begin() - 1;
cnt[i] += 1;
cnt[j] -= 1;
add[j] += a[i] - sum[j] + sum[i];
}
for (int i = 0; i < n; ++i) {
cout << cnt[i] * b[i] + add[i] << ' ';
cnt[i + 1] += cnt[i];
}
cout << '\n';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int add(int x, int y)
{
return ((x + y) % MOD + MOD) % MOD;
}
int mul(int x, int y)
{
return x * 1ll * y % MOD;
}
int binpow(int x, int y)
{
int z = 1;
while(y)
{
if(y % 2 == 1) z = mul(z, x);
x = mul(x, x);
y /= 2;
}
return z;
}
int inv(int x)
{
return binpow(x, MOD - 2);
}
int divide(int x, int y)
{
return mul(x, inv(y));
}
int main()
{
int n;
cin >> n;
int ans = 1;
for(int i = 1; i <= n / 6; i++)
ans = mul(ans, divide(i + n / 6, i));
for(int i = 0; i < n / 3; i++)
{
vector<int> a(3);
for(int j = 0; j < 3; j++)
cin >> a[j];
int mn = *min_element(a.begin(), a.end());
int cnt_min = count(a.begin(), a.end(), mn);
ans = mul(ans, cnt_min);
}
cout << ans << endl;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (adedalic)
import java.util.*
fun main() {
repeat(readln().toInt()) {
val n = readln().toInt()
var h = readln().split(' ').map { it.toInt() }
val d = Array(2) { LongArray(n) { 0 } }
for (tp in 0..1) {
val s = Stack<Pair<Int, Int>>()
for (i in h.indices) {
while (s.isNotEmpty() && s.peek().first > h[i] - i)
s.pop()
var j = maxOf(-1, i - h[i])
if (s.isNotEmpty())
j = maxOf(j, s.peek().second)
val len = (i - j).toLong()
d[tp][i] = len * h[i] - len * (len - 1) / 2
if (j >= 0 && len < h[i])
d[tp][i] += d[tp][j]
s.push(Pair(h[i] - i, i))
}
h = h.reversed()
}
d[1] = d[1].reversedArray()
var ans = 1e18.toLong()
val sum = h.fold(0L) { total, it -> total + it }
for (i in h.indices) {
val cur = sum - d[0][i] - d[1][i] + 2 * h[i]
ans = minOf(ans, cur)
}
println(ans)
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
vector<vector<int>> g;
vector<int> req;
vector<char> used;
vector<int> d;
bool dfs(int v, int p = -1){
d[v] = 0;
for (int u : g[v]) if (u != p){
if (!dfs(u, v)) return false;
if (!used[u]) d[v] = max(d[v], d[u] + 1);
}
if (req[v] == 0 || d[v] >= req[v]) return true;
if (p == -1 || used[p]) return false;
used[p] = true;
req[p] = req[v] - 1;
return true;
}
int main(){
int t;
scanf("%d", &t);
while (t--){
int n;
scanf("%d", &n);
g.assign(n, {});
d.resize(n);
forn(i, n - 1){
int v, u;
scanf("%d%d", &v, &u);
--v, --u;
g[v].push_back(u);
g[u].push_back(v);
}
int k;
scanf("%d", &k);
vector<int> a(k);
forn(i, k){
scanf("%d", &a[i]);
--a[i];
}
int l = 1, r = n;
int res = 0;
while (l <= r){
int m = (l + r) / 2;
used.assign(n, 0);
req.assign(n, 0);
forn(i, k){
used[a[i]] = true;
req[a[i]] = m / k + (i < m % k);
}
if (dfs(0)){
res = m;
l = m + 1;
}
else{
r = m - 1;
}
}
printf("%d\n", res);
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
typedef unsigned long long uli;
int main(){
int t;
scanf("%d", &t);
while (t--){
int n, m;
scanf("%d%d", &n, &m);
vector<int> a(n);
forn(i, n) scanf("%d", &a[i]);
vector<vector<int>> g(n);
forn(i, m){
int v, u;
scanf("%d%d", &v, &u);
--v, --u;
g[v].push_back(u);
g[u].push_back(v);
}
vector<char> rem(n);
vector<int> d(n);
forn(i, n) d[i] = g[i].size();
queue<int> q;
forn(i, n) if (a[i] == d[i]) q.push(i);
vector<pair<int, int>> ord;
while (!q.empty()){
int v = q.front();
q.pop();
rem[v] = true;
for (int u : g[v]) if (!rem[u]){
--d[u];
ord.push_back({v, u});
if (d[u] == a[u])
q.push(u);
}
}
reverse(ord.begin(), ord.end());
vector<uli> mask(n);
long long ans = n * 1ll * (n + 1) / 2;
for (int l = 0; l < n; l += 64){
int r = min(n, l + 64);
for (int i = l; i < r; ++i)
mask[i] = 1ull << (i - l);
for (const pair<int, int> &it : ord)
mask[it.first] |= mask[it.second];
forn(i, n){
ans -= __builtin_popcountll(mask[i]);
mask[i] = 0;
}
}
printf("%lld\n", ans);
}
}
Copy paste error in tutorial for F
Whoops, how did that happen. Fixed.
I like your profile picture
I found problem C difficult in this round.
I try problem C using segment tree and got AC.
here is the idea:
https://codeforces.net/contest/1795/submission/193897667
that's just unnecessarily complicated tho
Not really.
If you need to update and query a range, segment tree is intuitive. Adding a number and querying the sum in a range has is one the most common forms of segment trees. Also, you don't need to type a segment tree. It's just a copy-paste.
My approach for problem C
The time complexity is O(n^2) right? It's accepted?
It's O(Nlog(N))
erase takes O(logN) at the worst case (erase all elements that became 0)
c += s.size() * x;
take the value x from all elements in the set that will not become zero after we take x (greater than x)please explain your approach
The array "a" stores some values ** consider a[0] this value will be reduced by all values in b -> b[0:n[ a[1] will be reduced by all values in b -> b[1:n[
consider b[1] b[1] will reduce values in a[1] and a[0]
so when you take b[i] which is x in my solution add it to variable "val" which store sum of values of b until i (I'm sure that val will reduce all previous "a" values with its value) so for each element in the set, when an element becomes zero that's mean I can't reduce it any more so I should remove it from the set but other elements in the set that when I reduce it by x, It won't be zero (c+= x*size). I'm very bad at explanation so if you don't understand tell me.
BledDest i guess, there is a typo in a problem C editorial
" Now you want to find the largest j such that pref[ j-1 ]−pref[ i ] ≤ a[ i ]. Rewrite it as pref[ j-1 ] ≤ a[ i ] + pref[ i ] "
it should be pref[ j ] not pref[ j-1 ] because here pref[ j ] = b[ 0 ] + b[ 1 ] + b[ 2 ].......b[ j-1 ] any comment ?
Yeah, I think you are correct. Let me fix it real quick.
I got enlightenment guys,
the technique which is know as difference array technique by commoners has actually a fancy name : DELTA ENCODING
Is there any better solution in problem G?
maybe the difficulty gap between D&E was bigger than before (, that's probably because C was difficult and D was easier than usual .
G's compression trick is truly beautiful. Still I wonder is a n*n bool matrix works too?(Once I test it out I'll post the result below this comment)
Nevermind. Can't apply bitwise or on bool array.
In tutorial of E, why would the explosion series stop when $$$h_{p - i} \le h_{p} - i$$$ Doesn't this mean the explosion can proceed more left?
Can someone help to explain why the answer is n*(n+1)/2 — reachable pairs in problem G?
Oh, I've already understood, never mind ^_^. Btw, really elegant solution.
For G, Java don't have the function __builtin_popcountll and the same algorithm gets TLE at case 22(I compared the code with mine and the main parts are essentialy the same). Is there a java code that got accepted? Or should I just throw Java into a trash can and start using c++? And here's the code which got TLE at case 22. I even improved the edges iteration parts QAQ 194239334
Computing the number of bits set to 1 naively is too slow. Here are some ways to improve it if your language of choice doesn't support that function:
In the 9th paragraph of the tutorial of E, shouldn't this be corrected like this?
Correct me if I am wrong.
.
Problem C
include<bits/stdc++.h>
using namespace std;
define int long long
int binary_search(int i,vectora,vectorpref,int s) { int l=i; int r=a.size()-1; int ans=-1; while(l<=r) { int mid=(l+r)/2; if(pref[mid]-s<=a[i]) { ans=mid; l=mid+1; } else { r=mid-1; } } return ans; } void solve() { int n; cin>>n; vectora(n),b(n); for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++) cin>>b[i]; vectorpref(n); int sum=0; for(int i=0;i<n;i++) { sum+=b[i]; pref[i]=sum; } int i=0; vectorind(n+1,0); vectorans(n+1,0); while(i<n) { int s=i>0?pref[i-1]:0; //cout<<s<<endl; int t=binary_search(i,a,pref,s); //cout<<t<<endl; if(t!=-1) { ind[t+1]--; ans[t+1]+=a[i]-pref[t]+s; } else { ind[i]--; ans[i]+=a[i]; } i++; } sum=0; for(int i=0;i<n;i++) { sum+=ind[i]; ind[i]=i+1+sum; // cout<<ind[i]<<" "<<sum<<endl; } // cout<<endl; for(int i=0;i<n;i++) { ans[i]=ind[i]*b[i]+ans[i]; } for(int i=0;i<n;i++) cout<<ans[i]<<" "; cout<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); int t; cin>>t; for(int i=0;i<t;i++) solve(); } why I am getting TLE even though my solution being o(nlog(n))
C is a good problem for practising Segment Tree.
IN PROBLEM D: can anyone say why we are not considering pairing a triple with same color? Because "So, for each triple of vertices, there will be either one red vertex and two blue ones, or two red ones and one blue" from editorial. or why can't BBB RRB RRB RRB give maximum weight for sure in any case??
because then maximum weight will not be considered if we take all blue. read problem carefully