PikMike's blog

By PikMike, history, 7 months ago, translation, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it  
  • +67
  • Vote: I do not like it  

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

Can't understand C's explanation.

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

Alternately F can be solved with Divide and Conquer Optimisation as well.

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

    I seem to get TLE with Divide and Conquer Optimization , was any pruning required to pass the time limit ?

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

    It's Complexity O(n^2logn)?

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

Problem E can also be solved offline with an O(n) memory complexity, by sorting the queries w.r.t k and solving all queries with the same k together using dynamic programming.

Intuitions about the time complexity:

  1. If all queries have the same k, time complexity will be O(n)
  2. If all queries have different k (from 1 to 1e5), then first query will do n/2 iterations, second one n/3 iterations and so on. Overall complexity will be n * (1/2 + 1/3 + ... + 1/100000) = constant

I don't know exactly how to calculate a generalized upper bound for the time complexity, but I had the intuition that it would fit in time using this approach

Implementation: 26497630

  • »
    »
    7 months ago, # ^ |
    Rev. 5   Vote: I like it +6 Vote: I do not like it

    (1/2 + 1/3 + 1/4 + ... + 1/n) = O(logn)

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

      Oh yes you're right, it's logn. I got confused about it. Thanks.

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

      dropped

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

        Note, it's order.

        Hint for proof:

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
          Rev. 3   Vote: I like it -13 Vote: I do not like it

          I didn't learn integrals in school yet. But I could see that your formula is not correct:

          n = 1
          1/1 = log2(1)
          1 = 0 ?
          
          n = 2
          1/1 + 1/2 = log2(2)
          1.5 = 1 ?
          
          n = 3
          1/1 + 1/2 + 1/3 = log2(3)
          1.833 = 1.585 ?
          
          n = 10^5
          1/1 + 1/2 + ... + 1/10^5 = log2(10^5)
          12.090 = 16.609 ?
          

          Seems that functions are crossing and lying nearby but not equal.

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

            Actually, it's not . And you can see that the difference between (a.k.a harmonic number) and go smaller as n go bigger. It will eventually equal 0 when n big enough. Furthermore, is smaller than and as we can ignore constant, we can say it's O(logn)

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

              Thank you, I thought log always means log2 in informatics, not ln.

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

    But the time is worse than using sqrt precalculation..

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

    Look, if all k will be different your code will make this Q times: memset(dp, -1, sizeof(dp)); It is optimized of course but making your complexity bigger.

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

can anyone please explain Problem c editorial

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

I understand that this contest is quite old but 797C - Minimal string has a typo and says "lexigraphically" instead of "lexicographically". I'm not sure if this is correct way to report typos but don't see any other.

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

In Problem C's solution, instead of — 'any letter left in string s' in

"Pop letters from the top of stack and push them to answer while they are less or equal than any letter left in string s."

It should be --- 'while they are less or equal than all the letters left in string s'.

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

Can anyone give me a DP solution for Problem B? Why is this approach wrong?

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin>>n;
    vector<int> v;
    for(int i=0;i<n;i++)
    {
        int t;
        cin>>t;
        v.push_back(t);
    }
    vector<int> sum(n);
    for(int i=0;i<n;i++)
    {
        sum[i] = v[i];
    }
    int m = INT_MIN;
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<i;j++)//all subsequences ending at index 'i'.
        {
            if(sum[i] < sum[j] + v[i]) //check if appending v[i] to the longest-sum-seq. ending at j gives a better sum.
            {
                sum[i] = sum[j] + v[i];
                if(sum[i]%2!=0) m = max(m,sum[i]);
            }
        }
    }
    printf("%d\n",m);
    return 0;
}