### awoo's blog

By awoo, history, 12 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?
 » 12 months ago, # |   +9 Copy paste error in tutorial for F
•  » » 12 months ago, # ^ |   +7 Whoops, how did that happen. Fixed.
•  » » 12 months ago, # ^ |   +13 I like your profile picture
 » 12 months ago, # |   +5 I found problem C difficult in this round.
 » 12 months ago, # |   0 I try problem C using segment tree and got AC.here is the idea:
•  » » 12 months ago, # ^ |   +8 that's just unnecessarily complicated tho
•  » » » 12 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.
 » 12 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 ?
•  » » 12 months ago, # ^ |   0 Yeah, I think you are correct. Let me fix it real quick.
 » 12 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
 » 12 months ago, # |   0 Is there any better solution in problem G?
 » 12 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 .
 » 12 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)
•  » » 12 months ago, # ^ |   0 Nevermind. Can't apply bitwise or on bool array.
 » 12 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?
 » 12 months ago, # |   0 Can someone help to explain why the answer is n*(n+1)/2 — reachable pairs in problem G?
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 Oh, I've already understood, never mind ^_^. Btw, really elegant solution.
 » 12 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
•  » » 12 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).
 » 12 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
»
12 months ago, # |
Rev. 2   0

Hey for problem B why are we doing max l and min r.

I think that l == r only work when l == r == k. So we can do just this

# include

using namespace std;

int main() { int t; cin >> t; while (t--) { int n, k; int ls = 0, rs = 0; cin >> n >> k; int L = 0, R = 55; while (n--) { int l, r; cin >> l >> r; if(l == k) ls = 1; if(r == k) rs = 1; } cout << (ls == 1 && rs == 1 ? "YES\n" : "NO\n"); } }

When I was working for a solution I thought it should have atleast one segement that end with k and one should start with k. This solution works.

By the way I want to know the intuition of max(l) and min(r)

»
12 months ago, # |
-8

1795B — IDEAL POINT

# include <bits/stdc++.h>

using namespace std;

void solve(){ int n,k; cin>>n>>k; vector<pair<int,int>> v_in; for(int i=0;i<n;i++){ int a, b; cin>>a>>b; if(k==a && k==b){ cout<<"YES\n"; return; } pair<int,int> p(a,b); if(k==a || k==b) v_in.push_back(p); } if(v_in.size()==0 || v_in.size()==1){ cout<<"NO\n"; return; } sort(v_in.begin(),v_in.end()); if(v_in[0].first==v_in[v_in.size()-1].first){ cout<<"NO\n"; return; }else{ cout<<"YES\n"; return; } }

int main(){ int t; cin>>t; while(t--) solve(); return 0; }

what's wrong with this solution?

 » 3 months ago, # | ← Rev. 2 →   0 .
»
3 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))