awoo's blog

Educational Codeforces Round 19 Editorial
By awoo, history, 4 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 (47)
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Can't understand C's explanation.

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

    True.. it should have been like: Extract the first character of s and append this character with t. Extract the last character of t and append this character with u.

    rather then://this don't make any sense to me, append t/u with character? t and u are empty! 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
»
4 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
  • »
    »
    4 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
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
4 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
  • »
    »
    4 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
    • »
      »
      »
      4 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
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      dropped

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

        Note, it's order.

        Hint for proof:

        → Reply
        • »
          »
          »
          »
          »
          4 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
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            click

            → Reply
          • »
            »
            »
            »
            »
            »
            4 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
            • »
              »
              »
              »
              »
              »
              »
              4 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
        • »
          »
          »
          »
          »
          20 months 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
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But the time is worse than using sqrt precalculation..

    → Reply
  • »
    »
    4 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
  • »
    »
    3 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
  • »
    »
    3 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
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please explain Problem c editorial

→ Reply
»
4 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
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Fixed, thanks.

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

      Help me please, I don't know what is wrong with my code I am getting the wrong answer for test-case 17 of the question Minimal String (question C), here is my solution link. https://ideone.com/mc0zjt

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

        can you give me some test cases I am getting WA at test 21?

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

→ Reply
»
4 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
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Someone help me please getting the wrong answer. what is wrong with my code? here is my ideone link to my code https://ideone.com/mc0zjt

→ Reply
»
4 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
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why i am getting WA on test Case 16 in problem no C? Here is my submission 35083720.Anyone please help.

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

    can you give me some test cases I am getting WA at test 21?

    → Reply
»
3 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
  • »
    »
    3 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
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow dude, thanks for that test case. I was forgetting like half the problem. Thanks.

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

      no bro it didn't work for me

      → Reply
    • »
      »
      »
      13 months 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
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes same i have given 2 days to the ques

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

Why am I getting a runtime error when I run the following code ?

http://codeforces.com/contest/797/submission/50471261

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

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

→ Reply
»
20 months 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
»
14 months 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
»
8 months 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
  • »
    »
    7 months 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
»
7 months 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
»
5 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it 
these are two potential test cases for 797C Minimal string 
anybody stuck can try their code with these cases 
gitbash - abhstig
zpqazab - aabzqpz
→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we talk more about A? How to reduce to size k?

→ Reply