Can't understand C's explanation.

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

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

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

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.

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

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.me/contest/797/submission/33380771

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

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

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."

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

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.

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.me/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)).

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.

Great play on E :))

Great play on E :)