### awoo's blog

By awoo, history, 3 years ago, translation,

• +46

 » 3 years ago, # | ← Rev. 2 →   +56 I'll try to explain my idea on F, because I couldn't get the editorial (I'm pretty sure they aren't same solution) and wanted to write mine. Let's get any subsequence. For every occurence of s in that subsequence of F(x), we'll increase the answer by 1. Instead, for every possible occurence we can increase the answer by number of subsequences that have that substring in it. Let's consider a subsequence i1, i2...., in (indices of F(x)) such that if we concatenate the characters at such index, we would obtain s. It means that in every following subsequence we should update the answer by 1. For any j that is equal to some ik, it must contain it. For any j that isn't equal to some ik but i1 < j < in, it can't contain it. For any j < i1 or j > in, it can contain it, so we have 2 possibilities. So, for every set of indices (called i) we can increase the answer by 2i1 - 1 + n - in and we can obtain the answer. Let's create a function f(l, r, x) which is equal to answer when we are search for s[l..r] in F(x). (Not exactly but we'll come to that later.) F(x) is equal to F(x - 1)F(x - 2) so, that substring could be in F(x - 1), F(x - 2) or divided in both. If it's in F(x - 1), it means that we should calculate the number of ways and get the answer. Here's the key point, if r equals to n it means that we won't get anything from right so we should multiply it by 2|(F(x - 2)|. Since 2x * 2y = 2x + y in the end we will get the each occurence multiplied by 2n - in. When we will handle the l = 1 cases, similarly, we will get the answer.
•  » » 3 years ago, # ^ |   0 I've seen your code. There's "ret = add(ret, mul(f(l, k, x — 1), f(k + 1, r, x — 2)));". Why can they be simply multiplied? I think that f(l,k,x-1) may contain some subsequence like ...l,t... , and so to f(k+1,r,x-2). ...l,t... concatenate ...t+1,r... is ...l,t......t+1,r..., but not ...l,t,t+1,r... . How are those .... between l,t and t+1,r considered?
•  » » » 3 years ago, # ^ |   0 OK I got it. "which is equal to answer when we are search for s[l..r] in F(x)", This value depends on whether l==1 or r==n. If l==1 and r==n, it represent ...l,r... ; If l==1 and r1 and r==n, it represent l,r... ; If l>1 and r
•  » » » » 3 years ago, # ^ |   +2 Can you explain me better? I don't understand you.
•  » » 3 years ago, # ^ |   0 Wow, it is so clear! Thanks a lot, I understand the problem!
 » 3 years ago, # |   0 I'm most probably missing something obvious, but why would greedy not work on Problem 946D ?Like In O(mn) time, create an n*2 array greedy[day][i] where if there's still atleast one 1 in the ith string, then let greedy[i][0] denotes the number of hours that would reduce if you skip the first class in day i, and let greedy[i][1] denote the number of hours that would reduce if you skip the last class in day i (these two have same values if on that day, we have only one class), and if day i has no class, then set greedy[i][0] = greedy[i][1] =  - ∞Then initialize an heap with those n*2 elements in time. Then at each step, I pick the largest element from the heap in time, say it's greedy[j][1], and I change the last 1 in day i to 0, and update greedy[j][0] and greedy[j][1] in the heap. I stop when I have picked k elements.
•  » » 3 years ago, # ^ |   +14 The greedy approach fails (for example) whenever there are equal options at the beggining and at the end but some side is better somehow.Imagine: k = 3 Case 1 : 1110000111111111111 Case 2 : 1111111111110000111Removing the first 1 reduces the time in 1 on both sides, but only one of them leads to the best solution (greedy approach won't know which). That's why you should do dp.
•  » » » 3 years ago, # ^ |   0 I am very stupid to miss such a silly counterexample. Thanks !
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 nice case
 » 3 years ago, # |   0 I have a question about 946D. The problem statement was not clear to me. 2 6 2 010010 111100 For above example, I thought answer is 3. But, Passed code's answer is 4. It means skipped lessons is based on day, not week.So, I felt very difficult to this problem^^ Thanks
 » 3 years ago, # | ← Rev. 2 →   0 Can anyone plz explain the idea of this code http://codeforces.com/contest/946/submission/36016439 ? It's Problem F. I can't grasp the DP transition in this code clearly. As far as I studied, I guess it maybe use some math to simplify the transition. Can anyone help plz?
•  » » 3 years ago, # ^ |   0 I appreciate this simple transition very much, so I want to make clear of it.
•  » » 3 years ago, # ^ |   0 OK I got the idea. It's just a way by including the information of 2^length into the dp arrays. It's a very clever method, and I appreciate this very much!
 » 3 years ago, # |   0 Can anyone explain why on local machine I get correct answer but on server not? http://codeforces.com/contest/946/submission/36021632
•  » » 3 years ago, # ^ |   0 got it.
 » 3 years ago, # |   +28 Problem G can be solved with similar method as in the editorial, but without using segment tree. Let's calc dp[cnt][len] — minimum element ending sequence with cnt bad elements with length len. Calculating is similar to finding longest increasing sequence : for 1 bad element we use binary search for x-i+1, for 0 x-i.
 » 3 years ago, # |   0 can anyone explain me solution E?
 » 3 years ago, # |   0 Can someone explain in Problem B why using '%' gets AC and subtraction gets TLE?!
•  » » 3 years ago, # ^ |   0 a = 1018 , b = 1, you subtracted 1018/2 times
•  » » 3 years ago, # ^ |   +8 Imagine test 10^18 1, you make 5*10^17 subtractions but just one division. You can find proof of Euclid's algorithm with division complexity (it's O(log n)) and apply it here.
•  » » » 3 years ago, # ^ |   +3 How to solve problem E? I am not able to get the approach through editorial.
•  » » » » 3 years ago, # ^ |   0 Can you specify what part you don't understand?
•  » » » » » 3 years ago, # ^ |   0 the implementation part-4th paragraph in editorial
•  » » » » » » 3 years ago, # ^ |   +3 I can share my implementation with you, hope it helps.
•  » » » » » » » 3 years ago, # ^ |   0 Thanks
•  » » » » » » » 3 years ago, # ^ |   0 Thanks, this was very useful!
 » 3 years ago, # |   0 Does n^3 solution work where n = 500. Wont it be of order of 10^8, I left the D question for the same reason. I used to think order 10^7 is borderline for time limit of 2 seconds!!
•  » » 3 years ago, # ^ |   +1 10^7 is like the limit for python or some other slow lang. You can assume it to be about 2-4 * 10^8 for C++.
•  » » » 3 years ago, # ^ |   0 Ohh, alright thanks.By the way thats for 2 seconds, so if time limit is one second then i should expect 10^7 operations right ?
•  » » » » 3 years ago, # ^ |   +5 10^8
 » 3 years ago, # | ← Rev. 2 →   +1 Problem G -I didn't use rollback. I have used only 1 segment tree with range query and point updates.SolutionBrief Idea -LNDS — Longest Non-decreasing SubsequenceA[i] = A[i] — i for every 'i'For every index 'i', we want the length of LNDS ending at 'i-1', say E[i-1], and the length of LNDS from [i+1, n] whose 1st element is greater than A[i-1], say S[i+1]. We can easily calculate S[i+1] using segment tree. Calculation of E[i-1] is trivial. Final answer would minimum of n — 1 — E[i-1] — S[i+1]. Complexity — O(N*logN)
•  » » 3 years ago, # ^ |   0 For problem G, there's a very concise code. http://codeforces.com/contest/946/submission/36058677Using DP to manipulate the LIS arrays, I find there IS an optimal structure for them.
 » 3 years ago, # |   0 Can someone explain me the solution of C written in the editorial ?
•  » » 3 years ago, # ^ |   0 Have a char variable C which is intitially equal to 'a'.You need to check if there exists a subsequence of the English Alphabet in the given string. So iterate through the string fully, for each iteration check if the current character of string is not greater than C and increment C. So in the end, if your C value is not equal to 'z', then it means you don't have a subsequence of the English Alphabet. Hope this helps :)
•  » » » 3 years ago, # ^ |   0 For question C, I understand how this: aacceeggiikkmmooqqssuuwwyy becomes: abcdefghijklmnopqrstuvwxyzHowever, I do not understand why the check is only if the current character is not greater than variable C. I do not understand why this: aada becomes: abdc Why does the final character become c from a? The impression I got from the question is that a character can only move to the next character in the alphabet (a -> b, f -> g etc). Given this it seems that the final character could only become b. If that makes sense, anyone got any ideas what i've missed?
•  » » » » 3 months ago, # ^ | ← Rev. 6 →   0 aada-> abda -> abdb -> abdc (coz can use as much moves as needed)
 » 3 years ago, # |   0 Does hacking in educational rounds give you points?
•  » » 3 years ago, # ^ |   0 No , It does not
 » 3 years ago, # | ← Rev. 2 →   0 nice editorial
 » 3 years ago, # | ← Rev. 2 →   0 Can anyone explain why I (and some other people) get WA 16 in D problem? My code is here: 36048111. I coded the solution as in the editorial.
•  » » 3 years ago, # ^ |   0 Got it.
•  » » 2 years ago, # ^ |   0 Iam getting wa in 16 too,what was the error?
 » 3 years ago, # |   0 It shows tutorial not available
 » 3 years ago, # |   0 For problem E,i think the DFS algorithm is much easier.You can see my code. :)
 » 3 years ago, # | ← Rev. 2 →   0 For problem G, there's a very concise code. http://codeforces.com/contest/946/submission/36058677Using DP to manipulate the LIS arrays, I find there IS an optimal structure for them.
 » 3 years ago, # |   0 What does 'length(cur)' mean in Problem D?
•  » » 3 years ago, # ^ |   0 for lenghthcur in (0,k): // dp transition
•  » » » 3 years ago, # ^ |   0 OK, thank you ;)
 » 3 years ago, # | ← Rev. 3 →   0 For problem D: I tried solving it using a priority queue ( pq ). It's top is the day that if I skip a lesson in it, it will result in the maximum time saving...Say we got these strings in the pq:a: 100011011 --> saves 4 units of time if I skip a lessonb: 100101111 --> saves 3 units of time if I skip a lessonc: 010000111 --> saves 5 units of time if I skip a lessonThe pq top is c as it will result it will help to maximize time saving, hence minimizing the time spent at school..What's wrong with this approach??You can check my submissions..
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 And in case of a tie like this:1110111 --> saves 1 unit of time if I skip a lesson1111011 --> saves 1 unit of time if I skip a lessonIt'll choose the second string as it has a 0 nearer to 1 so in the second skipped lesson the string becomes: 1111000 but if it chooses the first string, it will become: 1110100 hence less time saving. That's how my pq works.. what's wrong ?
•  » » » 3 years ago, # ^ |   0 Got it. This will break the pq sorting criteria.. 1100011 0110110 
 » 3 years ago, # |   0 Can someone elaborate D some more? How should I calc this mn[i][j]? What should i put in mn[i][j] if I can't achieve j lessons in i-th day?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 losmi247, my solution uses an array that I call opt[i][j], wich is the minimun amount of hours you have to spend in the i-th day if you kick off exactly j classes that day. That is the mn[i][j]. This can be done greedly by taking the best prefix and suffix of lessons of that day such len(prefix)+len(suffix)==j. Then you can do dp[i][j] = min(dp[i][j], dp[i-1][j-k] + opt[i][k]);PD: if the number of lessons you going to skip the i-th day is greater or equal than the number of lessons you have to attend that day opt[i][j] should be 0
•  » » » 3 years ago, # ^ |   0 I can't thank you enough for this, thank you very much
 » 3 years ago, # |   0 can anyone please help me in understanding 946D timetable really i will appreciate the effort. I have no idea what is going on..please please from scratch
 » 3 years ago, # |   0 Please explain me problem F. Considering test 1:- 2 4 11 Judge answer is 14. But, I thought of problem as creating fibonacci string of 4 that is F(4) which is equal to 10110, then finding cost that is number of time string s that is 11 (entered by user) contained in F(4).So, my answer comes out to be 1(int) as 11(string) is contained only one time is F(4) i.e. 10110(string).Please, someone explain me. This is driving me crazy for days.
•  » » 3 years ago, # ^ |   0 You misunderstand the problem description. "calculate the sum of costs of all subsequences of the string F(x)"
•  » » » 3 years ago, # ^ |   0 Yeah, I see . But can you explain me using 1st test case. I'll appreciate your efforts.
•  » » » » 3 years ago, # ^ |   0 All subsequences of "10110" include 2^5=32 strings: 1, 0, 1, 1, 0, 10, 11, 11, 10...Maybe you need to check the definition of subsequence in wikipedia.
 » 3 years ago, # |   0 Can someone explain why my solution for problem c is getting TLE[submission:36266766]
•  » » 3 years ago, # ^ |   0 Got selected I use C# method to convert char array to string. C# is taking more time then usual dont know why
•  » » » 3 years ago, # ^ |   0 ans += s[i].ToString() give |s|^2, use StringBuilder instead
 » 3 years ago, # |   0 Can someone point me to problems similar to Problem D : Timetable ? I usually get stuck at such problems which involve preprocessing before beginning DP.
•  » » 13 months ago, # ^ |   0 So basically we'll have to do two DPs. One to create mn[i][j] which gives the minimum number of hours Ivan has to attend college on the ith day, and by skipping j lectures. (Note that the terminology for mn is different in the tutorial). The other one is dp[i][j] which gives the minimum number of hours Ivan has to attend college till the ith day and by skipping j lectures in total.Pretty similar DPs aren't they.One another thing to create is vector dp[n], in which day[i][j] will store the position of the jth lecture on the ith day. Now recursions:Firstly to calculate mn[i][j], we need to remove exactly $j$ lectures. Now removing a lecture from the midst wouldn't actually bring us any result as the total time Ivan stays in college matters. So, we'll target the lectures at the front and the lectures at the end. In total we have to delete $j$ lectures, so let's say we delete $l$ lectures from the front, then obviously we'll delete $r = j-l$ lectures from the end.So we need the hours Ivan stays in college in the given scenario. We can find this by day[i][total-r-1]-day[i][l]+1 (since we're using 0-indexing here). This simply means that we've deleted $r$ lectures from the right and $l$ lectures from the left, so the remaining lectures' hours are simply the difference of the first and last lectures remaining.Now to calculate dp[i][j]. Again my recursion is different than that of the tutorial. We here need to remove $j$ lectures in total, in the first $i$ days. The remaining hours make up dp[i][j]. So how is dp[i][j] made up from the already calculated dp[i-1]?Let's see.We had not seen the values for the ith day yet. That is dp[i-1] doesn't consider the ith day. So different values of ith day will be used with dp[i-1].So if I use delete two lectures of the ith day, I'll have mn[i][2] hours. This will go with dp[i-1][j-2] which means that we deleted $j-2$ lectures for the starting $i-1$ days. We used this to remove a total of $j$ lectures and consider $i$ starting days.So we can make this a loop: $dp[i][j] = \min_{t=0}^{j}(dp[i-1][j-t]+mn[i][t])$I will leave some initialisation details for you to fill, but this is mainly how this works.Here is my submission.
 » 3 years ago, # |   0 Problem F:I wonder if my solution works ? If not, please explain and give example(s). Thanks in advance :DFor each step i, I store 2 strings pre and suf that is the prefix and suffix of F[i]. Each string's length is smaller than the length of the given string s. With this, at each step I can string match to find new occurences that appears due to the concatenation of F[i] and F[i — 1]. In addition, I notice that F[i]'s pre = F[i — 1]'s pre and F[i]'s suf = F[i — 2]'s suf.
 » 2 years ago, # |   0 Hey awoo ,could you please elaborate the explanation of the following line of 946Ddp[i + 1][j + lengthcur] with dp[i][j] + mn[i][lengthcur]. Thanks,in advance.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Consider it the other way, say you are at day i and have skipped j lectures, this means that over the past i — 1 days you must have skipped "at max j lectures". So dp[i][j] is the min over all (k <= j) the value (dp[i -1][k] + mn[i][j — k]) (i.e. you have to skip j — k lectures on day i which can be obtd from the preprocessed array)You can refer this for the implementation
 » 22 months ago, # |   0 Can E be solved using binary search, by finding the least significant position which can be reduced by 1, so that its possible to construct a maximal number which is a palindrome ?