### KAN's blog

By KAN, 17 months ago, ,

Problem author: KAN.

Problem author: KAN.

Problem author: pashka.

Problem author: pashka.

Problem author: Umqra.

Problem author: Endagorion.

Problem author: Um_nik.

Problem author: Um_nik.

•
• +74
•

 » 17 months ago, # |   +36 in Div1 D, if O(26*n^2) solutions were intended to pass then time limit is too strict. if only O(n^2) solutions are intended to pass then why did you limit the number of different types to 26?it's really unfair some people pass with O(26*n^2) solution while the others didn't.
•  » » 17 months ago, # ^ |   +43 I must admit this particular issue didn't get the attention it deserved. I didn't expect a lot of O(kn2) solutions to pass, and I also underestimated the effort needed to optimize to O(n2). In an early stage I considered giving the problem with integers instead of latin letters, but it didn't seem quite elegant. Also, with Ω(n) different symbols allowed the solution would require Ω(n2) memory which is a bit large and may lead to additional time expenses and/or optimizations required, especially if you use a slower/less efficient language.As for unfairness, I tend to disagree. If your solution passes the pretests in, say, ~1.5 seconds out of 2, then you know you're in for a sort of gamble and are free to optimize and resubmit (like tourist did). As for the discrepancy between asymptotically identical solutions, well, that can never be completely disposed of. (That said, I don't tend to diminish the oversight on my part.)
 » 17 months ago, # | ← Rev. 3 →   +11 Another solution for B:First we give each hobbit on the pillow. Now we distribute pillows to everyone who is close enough to Frodo, until we start giving pillows to all hobbits, or we do not run out of pillows. Create two variables that one of them would take the number of hobbits who needs pillows from left side, the other — from right. If you have not reached the border, increasing the value of the variable. At each step required Left + right + 1 pillow (for Frodo). If you follow the cycle we still have pillows, then add m / n to the answer. Sorry for my English
•  » » 17 months ago, # ^ |   0 i did the exact same thing...gives me tle on case 6 code
•  » » » 17 months ago, # ^ | ← Rev. 6 →   +1 Your code doesn't implement what Dey suggests. In order to do that with your current code (24051579), you should break the while loop when ptr1 = 1 and ptr2 = n, then add ⌊x / n⌋ to the answer.
•  » » 17 months ago, # ^ |   0 During contest, I also had done exactly the same, only difference was that I didn't break the loop when left = 1 and right = n, that's why I got TLE and I thought that this technique won't work. But your comment help me to get my solution ACCEPTED.Thanks..
 » 17 months ago, # | ← Rev. 2 →   0 Problem D div 1:Can anyone explain in a little bit more details the formula for the number of reachable strings with comp(...) = u? Why does that equation with number of combinations hold?UPD Nevermind, got it
 » 17 months ago, # |   +2 An alternative O(n2) solution for D that isn't too complicated:As pointed out in the editorial, observe that a valid string is any string u such that comp(u) is a subsequence of comp(S), where S is the input string. The general idea is to do a dp by "building" all the valid strings (somewhat similar to the classical edit-distance dp).Define the dp as dpi, j =  number of ways to complete a partially-filled string, where: The partially-filled string has the first i characters determined already The next character we push to the string will correspond to the j-th character in S Then at each dp state (i, j), we can advance to dp(i + 1, k), for some specific values of k. In particular, these values of k are the first occurrence of each letter in the substring of S from [j, end]. This is because: We include each letter to allow us to skip arbitrary parts of comp(S). This maintains the fact that we are a subsequence. We only use the first occurrence of each letter to prevent double-counting. The answer is then the sum of all valid dp0, k. The definition of "valid k" is the same as the one above.A naive implementation of this can run in O(n3). You can optimise this to O(n2) by using a prefix-sum array.Accepted solution: 24045286
 » 17 months ago, # |   0 How to solve problem C if the problem asks for the largest element in the stack after all the operation instead of the top element?
 » 17 months ago, # |   0 Can anyone explain how this formula came in Div2B ((x-1+x-y)y)/2
•  » » 17 months ago, # ^ | ← Rev. 5 →   0 suppose we have y beds on one side of Frodo and Frodo has x pillows (y <= x-1). his neighbor has to have at least x-1 pillows to be satisfied,then the neighbor of his neighbor has to have x-2 pillows to be satisfied and so on... so we calculate the number of pillows :SUM = (x-1) + (x-2) + (x-3) + ... + (x-y+1) + (x-y)SUM = (x-y) + (x-y+1) + ... + (x-3) + (x-2) + (x-1)2 * SUM = (x-1+x-y) + (x-1+x-y) + .... + (x-1+x-y) + (x-1+x-y) ---> SUM = y((x-1+x-y))/2
•  » » » 17 months ago, # ^ |   0 can you explain about this formula came in div2b x*(x-1)/2+y-x+1 too?? thanks..
•  » » » » 17 months ago, # ^ | ← Rev. 2 →   0 @WannabeStronger Sure, so if y > x-1 we should give at least x-1 pillows to Frodo's neighbor, x-2 pillows to the neighbor of his neighbor and so on till we give a hobbit one pillow and then we're done! the number of pillows would be : SUM = (x-1) + (x-2) + (x-3) + ... + 2 + 1SUM = 1 + 2 + ... + (x-3) + (x-2) + (x-1)2 * SUM = x + x + .... + x + x ---> SUM = ((x-1)*x)/2Now everyone is satisfied but still there are some hobbits that don't have any pillows and as mentioned in the question "Each hobbit needs a bed and at least one pillow to sleep". till now, we gave x-1 out of y hobbits at least one pillow so we should give the rest (y-(x-1)) at least one pillow too! so the overall number of pillows would be: ((x-1)*x)/2+y-(x-1)
•  » » 17 months ago, # ^ | ← Rev. 3 →   0 Another formula for the same number:Let tn be the total number of pillows, y ≤ x - 1. As Borna pointed out:tn = (x - 1) + (x - 2) + (x - 3) + ... + (x - (y - 1)) + (x - y)Then, if we rearrange the summands:tn = (x + x + x + ... + x) - (1 + 2 + 3 + ... + (y - 1) + y)
•  » » 17 months ago, # ^ |   0 find sum from (x-y-1) ===> (x-1) =(sum from 1 ==> (x-1) =(x-1)x/2) - (sum from 1 ==> (x-y-1)=(x-y-1)(x-y)/2)= 2yx-y-y^2/2=y(2*x-1-y)/2
 » 17 months ago, # | ← Rev. 2 →   +10 C can also be easily solved with sqrt decomposition. We can create array and store the operations according to their positions. Then we split the whole array into sqrt(N) blocks, and maintain the biggest difference between push() and pop() operations in each block. We only need to change one block after a new query. To find the answer, we can just iterate over the blocks from right to left and find the first block, starting from which the difference is positive.To understand it better, you can have a look at my code: http://codeforces.com/contest/759/submission/24052265
 » 17 months ago, # |   -20 Problem div1 D can be solved without prefix sums or any other stupid optimization in as well. Code
•  » » 17 months ago, # ^ |   0 congrats for the selection of world finals
 » 17 months ago, # |   0 DIV.2 B Shouldn't the question be "n-1 hobbits are planning to spend the night at Frodo's house" rather than "n hobbits" ???
•  » » 17 months ago, # ^ |   +3 Yes, you're right. Perhaps he's a hobbit too!
 » 17 months ago, # |   0 756A — Pavel and barbecue and if bi equals 1 then he reverses it. this word show all skewers reverse or one skewer reverse ? l am misunderstand.
•  » » 17 months ago, # ^ |   0 If b[i] =  = 1 the skewer at position i will reverse (and then move to position p[i]).
 » 17 months ago, # | ← Rev. 2 →   -15 i have a test case for barbeque prob (div2 prob C) 4 2 3 4 2 0 1 0 0i checked many accepted codes everyone is giving ans as 0 , whereas the ans should be 1 i.e 2 3 4 2 should be 2 3 4 1 can anyone tell me why these codes are accepted ?
•  » » 17 months ago, # ^ |   +6 2 3 4 2 is not a permutation
•  » » » 17 months ago, # ^ |   +1 Yup thanks got ur point .
 » 17 months ago, # |   0 Each second Pavel move skewer on position i to position pi  ... Imagine we have 5 skewers: abcde. What happens with a skewer e when we move skewer a to the place where skewer e is located?
•  » » 17 months ago, # ^ | ← Rev. 3 →   0 e would move to a position determined by P.Each second the skewers at every i will move to respective Pi. Since P is a permutation, There will always be only one skewer at any i at any time.
•  » » » 17 months ago, # ^ |   0 e would move to a position determined by P. How is that? If you read statement — Pavel moves skewers (skewers aren't moving by themselves, right?). Each second the skewers at every i will move to respective Pi. There is no such info in the statement. Instead, the statement says that in one second we move only one skewer. So, according to the statement, after we move a to the position of e, we get the following configuration: abcde ⟶ bcdea. Is my reasoning faulted?
•  » » » » 17 months ago, # ^ |   +3 Each second Pavel move skewer on position i to position pi, and if bi equals 1 then he reverses it.Since they didnt mention which 'i' will be moved, I interpreted it as he will move all 'i' to their respective pi in one second.
•  » » » » » 17 months ago, # ^ |   0 Since they didnt mention which 'i' will be moved Can you elaborate a bit — I don't understand this part. he will move all 'i' to their respective pi in one second. How can he move all skewers in one second if it was explicitly said in the problem description that he moves exactly one skewer in one second? Not 2 skewers, not 3 skewers, but exactly 1 skewer.
•  » » » » » » 17 months ago, # ^ |   0 Nevermind, it seems your interpretation is right.Back to the original question, e would be in the same position along with the other skewer since they said it's alright if total time can be >=2n which implies repeated positions are fine.
•  » » » » » » » 17 months ago, # ^ |   0 e would be in the same position along with the other skewer... This is also wrong. Here is why.Let's assume that we allow for several skewers to be on the same place, i.e. we allow the following configuration:■bcde■■■■aThen there is no way for the following sentence to be meaningful: Pavel move skewer on position i to position pi There are now 2 different skewers in the last position and we don't know which one to choose in order to move it to position pi.
•  » » » » » » » » 17 months ago, # ^ |   0 The choice is yours to make. Basically end goal is to move each skewer to all 2n positions. The order you do it in doesn't matter.
•  » » » » » » » » » 17 months ago, # ^ |   0 Now I understand. Thank you! :)
•  » » » » » » » » » 12 months ago, # ^ |   0 In Div2 B editorial "Suppose there are y beds on one side of Frodo" , one side means left side or right side ? Can you please help me to understand
•  » » 17 months ago, # ^ |   0 This also had me a little confused. I ended up assuming that after I moved a to e, I immediately started moving e to it's position and so on for all other skewers.
 » 17 months ago, # |   0 760B why is Y ???
 » 17 months ago, # |   +1 Can someone please give some more hints on Div1 C?
 » 17 months ago, # |   0 can anyone tell me in this test case of "Travel card" problem 10 13 45 46 60 103 115 126 150 256 516Output20 20 10 0 20 0 0 20 20 10why ans at trip starting from 60th minute is 20 why it can't be zero
•  » » 17 months ago, # ^ |   0 it is 0.The first line of input contains integer number n (1 ≤ n ≤ 105) — the number of trips made by passenger. So the first number, 10, it's the number of trips
•  » » » 17 months ago, # ^ |   0 thanx i got it
 » 17 months ago, # | ← Rev. 2 →   0 Can any one please explain analysis to problem E? The above editorial is quite vague. For example, What is the relation/difference between k and pref? What is D? a[pref], a[k], a[n] or a[1]*..*a[n]? "sz is the size of the new layer" -> what is layer? all adjacent ai = 1? What is Di?
•  » » 17 months ago, # ^ |   +18 What is the editorial is trying to show is that the state space is , particularly around 20 times , this is because when you are evaluating dp[i][x], i.e. if you are at ith denomination say D, you must have already summed m%D into your sum, because that can not be added to the sum while processing i..n denomination. So, let S be the sum of all denominations from 1..i, so, for this layer( i.e. denomination) valid values of x are only pD + m%D where p varies from 1...S / D. You can see that sum over this S / D is bounded. Correct me if I am wrong.
 » 17 months ago, # |   0 FOR DIV2 B : Can anyone explain how those two formula came ? : and
 » 17 months ago, # |   0 For Div 1 C, what does the author means when he says "Look at the operations in reverse order"? Is it decreasing p_i or is it the actually the queries we are given in the input, going from bottom to top?
 » 17 months ago, # |   +5 There's a very short algorithm for D using O(n2) time and O(kn) space that I haven't seen mentioned. Let a[i] be the number of strings of length i (using the prefix we have processed so far). Let p[c][i] be the value that a[i] had after the last time that character c occurred. For each character c in the string, we update a with the amounts of new strings that end with the character c, which are exactly the strings that ended with a letter other than c (calculated by p[c][i] - a[i] for each length i) appended with any positive number of copies of c. Then we copy a into p[c]. Code
 » 16 months ago, # | ← Rev. 4 →   0 O(log2m) seems to be a little large for m ≤ 1010000 since m ≤ 1010000 seems to be suitable for O(logm(log2(logm)))
 » 13 months ago, # |   0 Editorial for div1 B please?
•  » » 13 months ago, # ^ |   0 It can be solved using dynamic programming, as we need to find minimum cost for each i th trip, as there are 3 types of tickets so there are 3 ways. We can buy a ticket for single trip and give 20 rubles (To this we will select the minimum possible cost upto (i-1)th trip. We can buy a ticket for 90 minutes and give 50 rubles (For this we can cover 90 minutes before the current trip time. For this we can use binary search to find the index which covers this time.) This case is similar to the 2nd case but here time we can cover is 1440 minutes and cost is 120 rubles. As we have to take the minimum cost, so we will take minimum of all these 3 and hence the required ans will be dp[i] — dp[i-1], as we have to give the difference (a-b).Refer this submission for more clarity. :)
 » 10 months ago, # |   0 Div1C can also be solved in O(mlogm) just using segment tree. (not using lazy propagation)For segment tree, store sum and maximum suffix sum on each node without reversing the operations.Updating query takes O(logm) time.For answering query, make a function find(val, id) which finds the position of rightmost suffix which has suffix sum bigger than 'val' in corresponding node. If right child's maximum suffix sum is bigger than 'val', recursively find answer at right child. Else, recursively find answer at left child, but this time 'val' becomes 'val' — 'right child sum'.For details, look at AC solution — 29482992