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.com/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.