awoo's blog

By awoo, history, 21 month(s) 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?
»
21 month(s) ago, # |
  Vote: I like it +9 Vote: I do not like it

Copy paste error in tutorial for F

»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

I found problem C difficult in this round.

»
21 month(s) 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:

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    that's just unnecessarily complicated tho

    • »
      »
      »
      21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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<ll> 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<ll> 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";
}
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The time complexity is O(n^2) right? It's accepted?

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    please explain your approach

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
21 month(s) 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 ?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
21 month(s) 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

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any better solution in problem G?

»
21 month(s) 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 .

»
21 month(s) 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)

»
21 month(s) 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?

»
21 month(s) 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?

  • »
    »
    21 month(s) 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.

»
21 month(s) 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

  • »
    »
    21 month(s) 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).
»
20 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.

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

.

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

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

C is a good problem for practising Segment Tree.

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

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

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

    because then maximum weight will not be considered if we take all blue. read problem carefully