awoo's blog

Educational Codeforces Round 19 Editorial
By awoo, history, 6 years 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

Comments Comments (33)
| Write comment?
»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Can't understand C's explanation.

→ Reply
»
6 years ago, # |
  Vote: I like it +29 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years 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 ?

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

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

    → Reply
»
6 years 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

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 5   Vote: I like it +6 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years 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.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      dropped

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

        Note, it's order.

        Hint for proof:

        → Reply
        • »
          »
          »
          »
          »
          6 years 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.

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

            click

            → Reply
          • »
            »
            »
            »
            »
            »
            6 years 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)

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

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

              → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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)

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

    But the time is worse than using sqrt precalculation..

    → Reply
  • »
    »
    6 years 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.

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
6 years 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.

→ Reply
»
6 years 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;
}
→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    test this maybe it would help :D

    input: czzbaz output should be: abzzcz

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah mate, really helpful test case. After testing with this one got AC

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    try this test case: eeddcbeeec
    correct ans is: bcceeeddee while your code gives: bceeecddee

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
14 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply