awoo's blog

By awoo, history, 12 months ago, In English

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
Solution (adedalic)

1795F - Blocking Chips

Idea: BledDest

Tutorial
Solution (awoo)

1795G - Removal Sequences

Idea: BledDest

Tutorial
Solution (awoo)
  • Vote: I like it
  • +121
  • Vote: I do not like it

| Write comment?
»
12 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Copy paste error in tutorial for F

»
12 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I found problem C difficult in this round.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I try problem C using segment tree and got AC.

here is the idea:

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    that's just unnecessarily complicated tho

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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   Vote: I like it +2 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, I think you are correct. Let me fix it real quick.

»
12 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

Is there any better solution in problem G?

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help to explain why the answer is n*(n+1)/2 — reachable pairs in problem G?

  • »
    »
    12 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Oh, I've already understood, never mind ^_^. Btw, really elegant solution.

»
12 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it +26 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

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<i such that aj−i aj−j ≤ ai−i. Note that...

Correct me if I am wrong.

»
12 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it -8 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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