Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

# | User | Rating |
---|---|---|

1 | tourist | 3803 |

2 | Benq | 3783 |

3 | Radewoosh | 3602 |

4 | Um_nik | 3541 |

5 | fantasy | 3526 |

6 | maroonrk | 3504 |

7 | ko_osaga | 3500 |

8 | jiangly | 3465 |

9 | orzdevinwang | 3460 |

10 | cnnfls_csy | 3427 |

# | User | Contrib. |
---|---|---|

1 | awoo | 180 |

2 | -is-this-fft- | 177 |

3 | nor | 169 |

4 | Um_nik | 168 |

5 | SecondThread | 164 |

6 | maroonrk | 163 |

7 | adamant | 161 |

8 | kostka | 160 |

9 | YouKn0wWho | 158 |

10 | tourist | 153 |

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of Educational Codeforces Round 19

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/05/2023 17:14:29 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Can't understand C's explanation.

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

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

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

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: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(1/2 + 1/3 + 1/4 + ... + 1/n) = O(logn)

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

dropped

Note, it's order.

Hint for proof:

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

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

click

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)

Thank you, I thought

`log`

always means`log2`

in informatics, not`ln`

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

But the time is worse than using sqrt precalculation..

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.Sorry for necropost, but in this case your solution works in

`O(n sqrt(n))`

time:Because your solution takes

O(n) operations per one block, but this isO(n) memory, u are righthi 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

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.

Fixed, thanks.

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

Here is the DP solution in case you need it still.

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

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

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

test this maybe it would help :D

input: czzbaz output should be: abzzcz

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

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 cat first i had difficulty understanding the question and then with whatever i understood ,i wrote adp solutionbut it gotWA on TC 17.if anyone has dp solution or can find the error in my code , it will be helpful.96818512 is my submission.try this test case: eeddcbeeec

correct ans is: bcceeeddee while your code gives: bceeecddee

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

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.