### awoo's blog

By awoo, history, 6 years ago, translation,  Tutorial of Educational Codeforces Round 19 Comments (33)
| Write comment?
 » 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: If all queries have the same k, time complexity will be O(n) 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 approachImplementation: 26497630
•  » » 6 years ago, # ^ | ← Rev. 5 →   (1/2 + 1/3 + 1/4 + ... + 1/n) = O(logn)
•  » » » Oh yes you're right, it's logn. I got confused about it. Thanks.
•  » » » 6 years ago, # ^ | ← Rev. 3 →   dropped
•  » » » » Note, it's order. Hint for proof: •  » » » » » 6 years ago, # ^ | ← Rev. 3 →   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.
•  » » » » » »
•  » » » » » » 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.
•  » » 4 years ago, # ^ | ← Rev. 2 →   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
•  » » 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
 » 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? #include using namespace std; int main() { int n; cin>>n; vector v; for(int i=0;i>t; v.push_back(t); } vector sum(n); for(int i=0;i
•  » » 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
 » 4 years ago, # | ← Rev. 3 →   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 :Dinput: 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!!!
 » 3 years ago, # | ← Rev. 2 →   someone please simulate this case:acdbs = 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.
•  » » 2 years ago, # ^ | ← Rev. 2 →   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/100305884I 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)).
 » 14 months ago, # | ← Rev. 3 →   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.