### awoo's blog

By awoo, history, 16 months ago,

1795A - Two Towers

Idea: BledDest

Tutorial
Solution (Neon) 1
Solution (Neon) 2

1795B - Ideal Point

Idea: BledDest

Tutorial
Solution (Neon)

1795C - Tea Tasting

Idea: BledDest

Tutorial
Solution (Neon)

1795D - Triangle Coloring

Idea: BledDest

Tutorial
Solution (BledDest)

1795E - Explosions?

Idea: BledDest

Tutorial

1795F - Blocking Chips

Idea: BledDest

Tutorial
Solution (awoo)

1795G - Removal Sequences

Idea: BledDest

Tutorial
Solution (awoo)
• +121

| Write comment?
 » 16 months ago, # |   +9 Copy paste error in tutorial for F
•  » » 16 months ago, # ^ |   +7 Whoops, how did that happen. Fixed.
•  » » 16 months ago, # ^ |   +13 I like your profile picture
 » 16 months ago, # |   +5 I found problem C difficult in this round.
 » 16 months ago, # |   0 I try problem C using segment tree and got AC.here is the idea:
•  » » 16 months ago, # ^ |   +8 that's just unnecessarily complicated tho
•  » » » 16 months ago, # ^ |   0 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.
 » 16 months ago, # |   0 My approach for problem C void solve() { ll n, x; cin >> n; ll a[n]; for (ll i = 0; i < n; i++) { cin >> a[i]; } multiset s; ll val = 0; for (ll i = 0; i < n; i++) { cin >> x; ll mn = min(x, a[i]), c = 0; s.insert(a[i] + val); auto it = s.begin(); vector toBeRemoved; while (1) { if (it == s.end()) break; if (*it - val <= x) { c += *it - val; toBeRemoved.push_back(*it); } else { break; } it++; } for (auto e : toBeRemoved) s.erase(e); val += x; c += s.size() * x; // c += mn; a[i] -= mn; cout << c << " "; } cout << "\n"; } 
•  » » 16 months ago, # ^ |   0 The time complexity is O(n^2) right? It's accepted?
•  » » » 16 months ago, # ^ |   0 It's O(Nlog(N)) for (auto e : toBeRemoved) s.erase(e); 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)
•  » » 16 months ago, # ^ |   0 please explain your approach
•  » » » 16 months ago, # ^ |   0 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.
 » 16 months ago, # | ← Rev. 4 →   +2 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 ?
•  » » 16 months ago, # ^ |   0 Yeah, I think you are correct. Let me fix it real quick.
 » 16 months ago, # |   +11 I got enlightenment guys, the technique which is know as difference array technique by commoners has actually a fancy name : DELTA ENCODING
 » 16 months ago, # |   0 Is there any better solution in problem G?
 » 16 months ago, # |   0 maybe the difficulty gap between D&E was bigger than before (, that's probably because C was difficult and D was easier than usual .
 » 16 months ago, # |   0 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)
•  » » 16 months ago, # ^ |   0 Nevermind. Can't apply bitwise or on bool array.
 » 16 months ago, # | ← Rev. 2 →   0 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?
 » 16 months ago, # |   0 Can someone help to explain why the answer is n*(n+1)/2 — reachable pairs in problem G?
•  » » 16 months ago, # ^ | ← Rev. 2 →   0 Oh, I've already understood, never mind ^_^. Btw, really elegant solution.
 » 16 months ago, # | ← Rev. 2 →   0 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
•  » » 16 months ago, # ^ |   +26 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: precalculate the number of bits set to 1 in all integers up to some number $2^k-1$. Let's say that $k = 16$. Then you can calculate the number of bits set to 1 in a 64-bit number in much fewer actions if you divide the number into blocks of $k$ bits (for $k = 16$, you need only $4$ blocks). use something like a bitset (although if you use it, it might be better to deal with larger number of bits, not 64).
 » 16 months ago, # |   0 In the 9th paragraph of the tutorial of E, shouldn't this be corrected like this? The last question is finding for each i the closest j
 » 7 months ago, # | ← Rev. 2 →   0 .
»
7 months ago, # |
0

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))

 » 3 months ago, # |   0 C is a good problem for practising Segment Tree.
 » 4 weeks ago, # | ← Rev. 2 →   0 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??
•  » » 12 days ago, # ^ |   0 because then maximum weight will not be considered if we take all blue. read problem carefully