### PikMike's blog

By PikMike, history, 2 years ago, translation, ,

• +67

 » 2 years ago, # |   +2 Can't understand C's explanation.
•  » » 2 months ago, # ^ |   0 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.
 » 2 years ago, # |   +29 Alternately F can be solved with Divide and Conquer Optimisation as well.
•  » » 2 years ago, # ^ |   0 I seem to get TLE with Divide and Conquer Optimization , was any pruning required to pass the time limit ?
•  » » 2 years ago, # ^ |   0 It's Complexity O(n^2logn)?
 » 2 years ago, # |   +1 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
•  » » 2 years ago, # ^ | ← Rev. 5 →   +6 (1/2 + 1/3 + 1/4 + ... + 1/n) = O(logn)
•  » » » 2 years ago, # ^ |   0 Oh yes you're right, it's logn. I got confused about it. Thanks.
•  » » » 2 years ago, # ^ | ← Rev. 3 →   0 dropped
•  » » » » 2 years ago, # ^ |   0 Note, it's order. Hint for proof:
•  » » » » » 2 years ago, # ^ | ← Rev. 3 →   -13 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.
•  » » » » » » 2 years ago, # ^ |   0
•  » » » » » » 2 years ago, # ^ |   +3 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)
•  » » » » » » » 2 years ago, # ^ |   0 Thank you, I thought log always means log2 in informatics, not ln.
•  » » 2 years ago, # ^ |   0 But the time is worse than using sqrt precalculation..
•  » » 2 years ago, # ^ |   0 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.
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 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
•  » » 9 months ago, # ^ |   0 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
 » 2 years ago, # |   0 can anyone please explain Problem c editorial
 » 2 years ago, # |   0 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.
•  » » 2 years ago, # ^ |   +3 Fixed, thanks.
•  » » » 19 months ago, # ^ |   0 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
•  » » » » 9 months ago, # ^ |   0 can you give me some test cases I am getting WA at test 21?
 » 2 years ago, # |   0 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'.
 » 2 years ago, # |   0 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
•  » » 11 months ago, # ^ |   0 Here is the DP solution in case you need it still.http://codeforces.com/contest/797/submission/41646680
 » 19 months ago, # | ← Rev. 2 →   0 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
 » 19 months ago, # |   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.com/contest/797/submission/33380771
 » 17 months ago, # |   0 Why i am getting WA on test Case 16 in problem no C? Here is my submission 35083720.Anyone please help.
•  » » 9 months ago, # ^ |   0 can you give me some test cases I am getting WA at test 21?
 » 9 months ago, # | ← Rev. 3 →   0 can anyone can give me some test cases on the question C I am getting WA at test 21?
•  » » 9 months ago, # ^ |   0 test this maybe it would help :Dinput: czzbaz output should be: abzzcz
•  » » » 5 months ago, # ^ |   0 Wow dude, thanks for that test case. I was forgetting like half the problem. Thanks.
 » 5 months ago, # | ← Rev. 3 →   0 Why am I getting a runtime error when I run the following code ?http://codeforces.com/contest/797/submission/50471261
 » 4 months ago, # |   0 Someone please explain problem 797F . Can't understand the editorial!!!