Блог пользователя awoo

Автор awoo, история, 7 лет назад, По-русски
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Разбор задач Educational Codeforces Round 19
  • Проголосовать: нравится
  • +67
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Can't understand C's explanation.

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    For maintaining minimal alphabetic letter in current string $$$s$$$ there's enough to precalc $$$ms_i$$$ — minimal letter for each suffix of $$$s$$$. Minimum on suffix starting from position $$$i$$$: $$$ms_i = min(s_i, ms_{i+1})$$$. This way is faster: just $$$O(n)$$$.

    Before adding to stack a letter at position $$$i$$$, while letter in the top of the stack is not greater than minimum on suffix starting from position i, pop the letter from the stack and add it to the answer.

»
7 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Ввиду того, что в задаче F норок всего 5000, а их вместимость не более 5000, то можно просто заменить их на 25 * 10^6 и решать задачу, что в каждую норку максимум может влезть одна мышь. Это уже более стандартная динамика, dp[i][j]i мышь бежит в норку j при условии, что i-1 бежала максимум в норку j-1. Единственное исключение — то, что не нужно пытаться засунуть каждую мышь в каждую норку, а только в 5000 норок слева или справа от позиции мыши, поэтому вторая размерность динамики будет равна 10000, а не количеству норок. Дополнительно следует хранить соответствие вторых индексов динамики и номеров норок. Чтобы быстро прибавлять ответ с предыдущего слоя, хватит и частичных минимумов. Также, для каждой мыши потребуется найти ближайшую слева норку, например, бинарным поиском. И, возможно, потребуется хранить только два слоя динамики для оптимизации по памяти.

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится +6 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      dropped

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Note, it's order.

        Hint for proof:

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится -13 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

            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)

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Here is another proof: 1/1+1/2+1/3+1/4+1/5+1/6+1/7+..<1/1+1/2+1/2+1/4+1/4+1/4<1+1+1...+1=log n and 1/1+1/2+1/3+1/4+1/5+1/6+1/7+1/8. <1+1/2+1/4+1/4+1/8+1/8+1/8+1/8<1+1/2+1/2...+1/2=log n/2 So 1/1+1/2+...+1/n is O(log n)

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    But the time is worse than using sqrt precalculation..

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Sorry for necropost, but in this case your solution works in O(n sqrt(n)) time:

    Array:
    a[i] = 1, 1 <= i <= n
    
    Queries:
    1   query with k = 1: p = 1
    2 queries with k = 2: p = 1,2
    3 queries with k = 3: p = 1,2,3
    4 queries with k = 4: p = 1,2,3,4
    5 queries with k = 5: p = 1,2,3,4,5
    ...
    sqrt(n) queries with k = sqrt(n): p = 1,2,...,k
    

    Because your solution takes O(n) operations per one block, but this is O(n) memory, u are right

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    hi excuse me but if all queries have different k's then you say if (k != prev) {memset(dp, -1, sizeof(dp));} so you basically fill the dp with -1's in every query but isn't this O(n^2)? could you explain why you don't get TLE? thanks ,and sorry to bothering you :D

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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;
}

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone tell me where am I wrong in this code. It is giving wrong answer for an input. I am not getting why my code is giving wrong output for that input. Printing o before n. http://codeforces.com/contest/797/submission/33380771

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

can anyone can give me some test cases on the question C I am getting WA at test 21?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Someone please explain problem 797F . Can't understand the editorial!!!

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

someone please simulate this case:

acdb

s = acbd, t = '', u =''

s = cbd, t = a, u = ''

s = bd, t = ca, u = '' [first char 'c' was taken and string t was appended]

s = b, t = dca, u = ''

if the last character is to be extracted from t then it is 'a' and it will be in the last position of u which is not the output given in the test case.

i think i am misinterpreting the following lines

"Extract the first character of s and append t with this character.

Extract the last character of t and append u with this character."

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem statement of C is very misleading. At first I could visualize string T nothing more than a queue and sorting seemed impossible.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

problem c at first i had difficulty understanding the question and then with whatever i understood ,i wrote a dp solution but it got WA on TC 17.if anyone has dp solution or can find the error in my code , it will be helpful.96818512 is my submission.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

HI, can anyone help me to provide the time complexity of my solution to problem E,

Here is the link to my submission:- https://codeforces.com/contest/797/submission/100305884

I guess it is n√n,

I have solved for every k individually and for a particular k, i have solved for all different values of p and storing the result for traversed indices for every p.

I think that worst case complexity would be, n + 2*(n/2) + 3* (n/3) + ... x terms s.t. x*(x+1)/2 = q; Because as k increase from 1 to n I can solve for particular k and pparticular p in n/k time, so, if all k are different then it will be, n + n/2+n/3... = nlog(n), and if there are multiple p for same k then it will be (dup, no.of different p for same k), (n/k * min(dup,k)).

»
2 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

In problem C the statement is completely wrong. It should be:

Move1: Extract the first character of s and append this character with t.

Move2: Extract the last character of t and append this character with u.