GlebsHP's blog

By GlebsHP, history, 10 months ago, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it  
  • +70
  • Vote: I do not like it  

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

Auto comment: topic has been updated by GlebsHP (previous revision, new revision, compare).

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

In the problem C I used a map to store previous queries to pass on the 100th test case. It worked, lol

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

    and main program?Are you using the is_sorted() function in stl?

    upd:sorry I'm bit naive

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

      No, actually I precomputed the answer as said in the problem explanation.But my algorithm runs on O(k*m), Because it checks every column, it's pretty easy to repeat queries just to slow it down. Só I used a map to store previous queries. Here is a link: 24986527.

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

        you are so clever.

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

        I saw your solution, the key here is using "pref" dynamic programming, not the map. No need to store the previous queries, I can pass all test without map and faster two times yours. 25166547

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

          What I meant was that I didn't need to quite do what the editorial said and it worked. Later I did what the editorial explained.

          cheers

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

        nice....haha...

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

    Seems distinct queries are very needed

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

    i saw ur comment and did the same thing :)

»
10 months ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

There may be a mistake in prob E's solution.

ans[i] += opt[i].height; should be ans[i] += r[i].height;

opt.back() should be opt.top()

Is it right?

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

for problem E can't we use modified longest increasing sub-sequence in O(nlgn) ?

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

    i did something similar to LIS, but in the end it's not so far from the solution proposed above

    #include <cstdio>
    #include <algorithm>
    #include <set>
    using namespace std;
    int II(){int n;scanf("%d",&n);return n;}
    void II(int n){printf("%d\n",n);}
    typedef long long ll;
    void LL(ll n){printf("%lld\n",n);}
    typedef pair<int,ll> il;
    
    struct ring_t {
      int inner,outer,height;
      bool operator<(ring_t b)
      {
        if(b.outer==outer)return inner>b.inner;
        return outer>b.outer;
      }
    };
    
    #define MAXN 100000
    
    ring_t V[MAXN]; ring_t *vend=V;
    
    int main()
    {
      int N=II();
      set<il> dp;
      while(N--)*vend++={II(),II(),II()};
      ll H=0;
      sort(V,vend);
      for(ring_t *x=V;x<vend;x++)
      {
        //printf("adding %d,%d,%d",x->inner,x->outer,x->height);
        ll myH=0;
        {
          auto it=dp.lower_bound({x->outer,-1});
          if(it!=dp.begin())
          {
            it--;
            myH=it->second;
          }
        }
        myH+=x->height;
        H=max(H,myH);
        {
          auto r=dp.insert({x->inner,myH});
          if(r.second)
          {
            auto it=r.first;
            auto prv=it;prv++;
            while(prv!=dp.end()&&it->second>=prv->second)
            {
              dp.erase(prv);
              prv=it;prv++;
            }
          }
        }
        //for(auto y:dp)printf("[%d|%d] ",y.first,y.second);putchar(10);
      }
      LL(H);
    }
    
    
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Should the dynamic programming recursion be ans(i) = maxj < i, bj > aians(j) + hi instead of what you wrote?

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

I think there is a mistake in 777C. It's supposed to be "such that the table is not decreasing in COLUMN j" right? Thanks for the editorial!

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

In problem C, should be a[i, j] <= a[i + 1, j] instead of a[i, j] < a[i + 1, j].

»
9 months ago, # |
  Vote: I like it +19 Vote: I do not like it

When CF round #403 begins?

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

I see that there is a binary search tag for problem C. Did anyone solve this problem using binary search? Please enlighten me on how to use binary search for this problem.

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

    If you just store the indexes which are greater than the next number in an adjacency list for each column. Then for each query you could apply binary search within that range and see if no such element exists even for one column, then Yes. But there seems to be some kind of optimization that I have missed. Plus, the approach is way slower than that in the editorial. This might help

    Please let me know if I'm wrong.

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

I am unable to understand the tutorial for problem C. Can anybody please explain the tutorial in a more easy way. I am new to DP. Thank you.

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

Here are two submissions for problem D.

26348627

26348633

These two submissions contain exactly the same code. Yet, I didn't use the same compiler. The first one got TLE, and the second one got Accepted. I would be thankful if anybody could explain me why.

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E (777E - Hanoi Factory):
Could someone please explain the second approach described in the tutorial?

I'm failing to understand how/why it should work with stack.

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

    If someone could provide a link to a complete solution which uses the approach, it could possibly help as well.

  • »
    »
    30 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was able to understand an approach behind this submission: 33027274.
    It is also stack-based,
    although I'm not sure it uses the same idea
    (because I'm still not sure I understand the tutorial's idea).