### fcspartakm's blog

By fcspartakm, history, 3 years ago,

• +54

 » 3 years ago, # |   +3 In problem D (n + (n - 1) - sum) / 2I think it should be (n + (n - 1) - p) / 2
•  » » 3 years ago, # ^ |   +1 Can you explain me why this formula works?
•  » » » 3 years ago, # ^ |   +1 sorry, I do not understand how it works, I found this after reading other's code.
•  » » » » 3 years ago, # ^ |   0 oo ok) but (n + (n - 1) - sum) / 2 100% not right... becuse its always 0
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 D. Why is there this weird result?2 => 13 => 34 => 6 How is it possible to get 6 pairs?http://codeforces.com/contest/899/submission/33360139UPD: I did it because my last tests were not passed, for examplehttp://codeforces.com/contest/899/submission/33359341
•  » » » » » » 3 years ago, # ^ |   +1 The question asks for the number of pairs such that they produce the maximum number of trailing nines. When n < 5, there exists no pair such that their sum is a number with a trailing nine. Therefore we should print all pairs (as all of them produce the maximum number of trailing nines, which is zero). The number of pairs is simply nC2.
•  » » » » » » » 3 years ago, # ^ |   0 got it, thank you
•  » » » » » » » 3 years ago, # ^ |   0 why not just output -1 or 0 when n<5...
•  » » » » » » » » 3 years ago, # ^ |   0 Refer to Fayaz's comment above or http://codeforces.com/blog/entry/56391?#comment-400974.
•  » » » 3 years ago, # ^ |   0 Yes please. Someone explain D. or atleast how to come up with those ideas and the formulas.
•  » » » » 3 years ago, # ^ | ← Rev. 6 →   +4 The solution for D is fairly simple to come up with.1) Observe that when n < 5, the answer is .2) Observe that when n + (n - 1) is of the form 9....9 the answer is 1.3) In all other cases, we need to iterate through the possible (i + j)'s that produce the maximum number of nines. So, say the maximum number of nines is x. Start at 9...9 (x times) and increment this to 1(9....9) (x times) 2(9....9) (x times) until we reach n + (n - 1). For each of these numbers we need to calculate how many pairs (i, j) sum up to them. Now, when the number is >= n + (n - 1), we need to add (number / 2) to our answer. This is because we can have: (number / 2) + (number / 2), (number / 2 + 1) + (number / 2 - 1) ...so on to sum up to the number. Otherwise if the number < n + (n - 1), we need to add (n - number / 2) to our answer. This is because we can have: (number / 2) + (number / 2), ..., n + (number - n).Here's my submission for reference http://codeforces.com/contest/899/submission/33348429
•  » » » » 3 years ago, # ^ |   0 It can be solved using digit DP. Submission Link Explanation
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 It should be 1 + (n + (n-1) - p)/2
 » 3 years ago, # |   0 Pardon me for a stupid question.In Div2B, the 13th test case is the following: 21 30 31 30 31 31 28 31 30 31 30 31 31 30 31 30 31 31 28 31 30 31and correct output is "YES"Doesn't this show two consecutive leap years? year 1: 31 28 31 30 31 30 31 31 30 31 30 31, next year: 31 28 31 30 31 ... this should not be possible right?
•  » » 3 years ago, # ^ |   +9 A leap year has 29 days.
•  » » » 3 years ago, # ^ |   0 Oh god. I can't believe I made this mistake D: So stupid of me.Thanks though!
•  » » » » 3 years ago, # ^ |   +12 Look at all the people who failed problem B. They all did same mistake as you. It's because of the problem statement, January, 28 or 29 days in February (depending on whether the year is leap or not) , which gives an idea that correspondly leap has 28 days and not leap has 29 days.
•  » » » » » 3 years ago, # ^ |   0 Yeah. :(
 » 3 years ago, # | ← Rev. 2 →   0 I solved C by just making two set and giving element to the smaller sum set in a reverse sorted order.I don't know why this works though. Can anyone help me with proving this method's correctness or tell where it could fail?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 I am trying the same approach and in pretest 5 59998 its failing as i am putting 48950 twice. I am not sure why only that case failing :|EDIT: a lot of other cases are also failing. have to do something else,
•  » » » 3 years ago, # ^ |   0 Try to do it in reverse order, so construct your sets starting with n, then n-1, and so on. This will give you a correct solution.
•  » » 3 years ago, # ^ |   +7 A set of 4 numbers can always be divided into two sets so that their differences is 0. Take n, n-1, n-2, n-3. Set1 contains n, n-3 and Set2 contains n-1, n-2. When dividing a consecutive sequence, you can always start from the last, take a group of 4 consecutive integers, and start dividing like earlier. If you can't take a group of 4 consecutive integers, the sequences left might be: i) 1, which can be assigned to any set. ii) 1, 2 : where 1 can be assigned to one set and 2 can be assigned the other set. iii) 1, 2, 3: where 1 and 2 has to be assigned to one set and 3 has to be assigned to the other set. Your algorithm automatically takes care of the first step. When it assigns n to one set, and n-1 to another, then n-2 becomes assigned to the set containing n-1 and n-3 becomes assigned to the set containing n. Your algorithm also automatically takes care of the 2nd step. A quick thinking will reveal why. Hope you understood! :)
•  » » » 3 years ago, # ^ |   0 Yeah .Thanks !
•  » » » 3 years ago, # ^ |   0 good explanation .
 » 3 years ago, # | ← Rev. 2 →   +1 Can someone please explain solution to problem E. I don't understand the editorial.
•  » » 3 years ago, # ^ |   +3 Understood from others solutions :)
 » 3 years ago, # | ← Rev. 4 →   +3 A much easier solution for C : My solution link... 1. Just take the sum of the numbers= N*(N+1)/2. If sum is even, then logically you can divide it into two equal halves. Keep giving the largest numbers possible till you form half of the sum. 3.If sum is odd, then logically one group will have one more sum than other group(g2). Let G2 sum be x. Keep giving the largest numbers possible to form x
•  » » 3 years ago, # ^ |   0 I have also done with similar approach.
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 I wonder why the writer didn't explain in this way. Are there any cases that this approach doesn't work properly?
•  » » » 6 months ago, # ^ |   0 All of them worked. This solution seems more intuitive to me compared to one in the editorial.
•  » » 3 years ago, # ^ |   0 I used some FOR loops and my code passed all the test cases but I haven't understood how it worked yet, and your approach seems to be the way it works. Would anyone mind suggesting or showing me a proof of correctness? http://codeforces.com/blog/entry/56391?#comment-401004
•  » » 3 years ago, # ^ |   0 can u please explain ur approach
•  » » 4 months ago, # ^ |   0 I did the same way and after reading the editorial I was like boom! Our solution is way more shorter
 » 3 years ago, # |   +3 Can someone explain D? Why we are adding those numbers etc..
 » 3 years ago, # |   0 难得有一次cf这么适合Chinese。。。
•  » » 3 years ago, # ^ |   0 结果差点忘记比赛..晚了几十分钟
 » 3 years ago, # | ← Rev. 3 →   +5 Easier way to solve problem C . The sum of the first N numbers is N * ( N + 1 ) / 2, let's call it tot.If you have a number X less than or equal tot, it is possible to represent it as a sum of first N numbers. ( Iterate from N to 1, and subtract when possible), call that function represent(X). This is very well known.Now .. if tot is even, we can obtain a difference of zero which we obtain by represent(tot/2). If tot is odd, we can obtain a difference of one which we obtain by represent(tot/2).In even case, we get the best possible answer, in the odd case it's easy to see that the best we can obtain is a difference of one, and hence the algorithm is optimal.
 » 3 years ago, # |   0 Another way to solve F is keeping a treap for each character. However, it is overkill in my opinion. But if you have template ready to be copied and pasted, then it should be fastest solution.
 » 3 years ago, # |   0
•  » » 3 years ago, # ^ |   +14 You are using this loop: for(set::iterator re=ya.begin(); re!=ya.end(); re++) if((*(re)+i<48)&&(a[*(re)+i]!=j)) ya.erase(re); As soon as you do ya.erase(re), the iterator re is invalidated (refer to the first line in heading Iterator validity), so you get unexpected behavior, i.e., you shouldn't use re anymore.
•  » » » 3 years ago, # ^ |   0 Thank you so much!
 » 3 years ago, # | ← Rev. 4 →   0 My solution to 899C - Dividing the numbers is the following:We know that for every two consecutive numbers a and b, a-b = 1 if a > b and a-b = -1 if a < b. So if we take the rightmost two consecutive numbers a, b, a > b, and put them in separate groups, we have |group1-group2| = |a-b| = 1; now if we take the next two consecutive number c, d, with c < d, and put c in group1 and d in group2, then |group1-group2| = |(a+c)-(b+d)| = |(a-b)+(c-d)| = |1-1| = 0. If we greedily continue doing this strategy, we would compute two groups that their absolute difference of sums is minimum.To compute the minimum absolute difference we can check in O(1) if we have a pair number of pairs (it means that every number has his pair in the strategy above) or not.
 » 3 years ago, # |   0 In problem D we can use a binary search for counting the number of pairs with a fixed amount on a interval: 33359972
 » 3 years ago, # |   0 Hey anyone got the solution of E by simulating the process using stacks, as i am getting stuck somewhere in this implementation.
 » 3 years ago, # | ← Rev. 2 →   0 Hi guys! Can anybody help me with problem F ?! I tried to solve it using a Multimap and a Fenwick Tree for building the initial positions but I'm getting "Wrong answer" on test 7 :(( Maybe I omit something. Thx in advance!
•  » » 3 years ago, # ^ |   0 I solved it by checking if some char already deleted. If yes, don't update
•  » » » 3 years ago, # ^ |   0 Thank you! I was just deleting characters multiple times. ^^
 » 3 years ago, # |   0 I have a doubt in Problem E. While merging the two nodes, I can see how we are deleting the right and the left element from the second set(called segments), and then inserting the merged set. I don't understand, how can we perform the same operation in the first set(called lens) ?
•  » » 3 years ago, # ^ |   0 we know the position of the beginning of the segment and the length of the segment. so we can just use set.find
•  » » » 3 years ago, # ^ |   0 Got it. Thanks!
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 got it :)
 » 3 years ago, # |   +4 Hey guys! Here are some of my thoughts on problem E this round, using priority queue and linked list! Have a glance! Use of Linked List and Priority Queue in CF Round 452, Problem E
•  » » 3 years ago, # ^ |   0 can you please explain how the merge section and del function is working? I am a beginner and unable to understand it directly from your code.
•  » » » 3 years ago, # ^ |   +1 Yeah. The del function will be called when I need to remove a node.For the merge function, when I remove a node, I need to consider whether the node on the left and the one on the right will merge to a longer sequence. For example, after delete [2,2,2,2] in [3,3,3,1,1,2,2,2,2,1,1], the two sequence [1,1] and [1,1] merge together and become a long sequence, that's what the merge function does.
•  » » » » 3 years ago, # ^ |   0 thanks for your reply :)
 » 3 years ago, # |   +4 In 899F, I didnt understand how would change the current l,r to positions in initial string using segment tree?
•  » » 3 years ago, # ^ |   0 we can use binary search the prefix sum on the segment tree。
•  » » » 3 years ago, # ^ |   +3 Please elaborate a bit more.
•  » » » » 3 years ago, # ^ |   +3 Sure。 We define a sequence a, a_i equals 0 if the ith element of the original sequence has been deleted, otherwise a_i equals 1. If we need to find the current position of the xth element in the original sequence, then it is equivalent to the smallest i that satisfies the sequence sum [i] = x. Because the sum function is incremented, we can use the binary search to find i that satisfies the condition, This i is the current position of the xth element in the original sequence. We can use the segment tree to maintain this sequence a.
•  » » » » » 3 years ago, # ^ |   0 Thanks again.
•  » » 3 years ago, # ^ | ← Rev. 3 →   +3 What does it mean for an item to be in the ith position? It means that before it there are i — 1 items before it.Now assume for each query you have a data structure that tells you for each original index of the string, how many non deleted elements are before it. Now to find index L, you just need to find index i such that there are l — 1 non deleted items before it.Can be done by Binary search + fenwick tree or segment tree.
•  » » » 3 years ago, # ^ |   +3 Got it. Thanks.
 » 3 years ago, # |   0 Hello guys, Happy Coming New Year to everyone! Can somebody help me, why do I keep getting TL7? Thanks in advance. Solution
 » 3 years ago, # | ← Rev. 3 →   0 Hey everyone The editorial for the dividing numbers question is great but have a look at my soluton its easy far.. I uses two pointer approach consider a given n = 111 2 3 4 5 6 7 8 9 10 11now set i = 1 and j = n (i.e 11) now I set the condition in an loop as ::  for (i = 1,j=n; i+2 != j && i<=j; i++,j--)  here the condition i+2!=j handle the odd length value of n and i<=j should be valid in each and every case whether it is odd or even. Formally lets run on this example case:when n = 11 i=1,j=11(Basically I put an variable count1 = 1 + 11 which stores the sum of values in an 1 group and only the values are summed when i is odd no denoting that we are putting the values in an 1 group and side by side we are storing the values of group 1 in an array A using the conditions mentioned in the code) correspondingly when i=2,j=10(count2=2+10 for even i) Now in case when n is even all the manipulations are done inside the loop using the below code . for (i = 1,j=n; i+2 != j && i<=j; i++,j--) { if(n%2==0){//100% ok if(i%2==0&&i+1==j){ if(count2==count1)//extra condition { count1+=i,A[k++]=i,count2+=j; } else {count2+=i+j;} } else if(i%2==0&&i+1!=j){count2+=i+j;} //coding is love and fun else if(i%2!=0&&i+1==j){ if(count2==count1) {A[k++]=i,count1+=i,count2+=j;} else {count2+=i+j;}//extra condition } else if(i%2!=0&&i+1!=j){A[k++]=i,A[k++]=j,count1+=i+j;} } else {//for odd case //for odd lenght both cases for even psotion and odd position if(i%2!=0){A[k++]=i,A[k++]=j,count1+=i+j;} else {count2+=i+j;} } } Now in case when n is odd the manipulations are done till the exit condition is not founded which is i+2!=j (founded in every odd case length n) so it will stops at i = 5 and j = 7 then out of the loop I checks that in case when count1 ! =count2 then how to arrange the remaining numbers on the group 1 and group 2. if(n%2!=0){//this thing is outside the loop if(count2!=count1){ a=(abs((count2+j+i+1)-(count1+i))); b=(abs((count2+i+j)-(count1+i+1))),c=(abs((count2+i+i+1)-(count1+j))); ans=min(min(a,min(b,c)),min(b,min(a,c))); if(ans==a){ count2=count2+j+i+1,count1+=i,A[k++]=i;} else if(ans==b){ count2=count2+j+i,count1+=i+1,A[k++]=i+1;} else if(ans==c){ count2=count2+i+i+1,count1+=j,A[k++]=j;} } else { A[k++]=i,A[k++]=i+1,count1=count1+i+(i+1),count2+=j; } } plzz have a look at the code deeply and plzz try to understand it..and finally  cout<
 » 3 years ago, # |   +3 Problem CCan be solved greedily:Start with putting N on the left pile and N - 1 on the right one. Then by placing N - 2 on the right and N - 3 on the left we got left - right == 0 and we reduce the problem to the one of the size N - 4.At some point we end up with one of four possible problem sizes: 0, 1, 2, 3.In the first case the difference was 0 and it's the best we can do. In the second case we get 1 which is also the best solution because in than case N = 4k + 1 and the sum = N * (N + 1) / 2 = (4k + 1)(2k) is odd. In the third case we end up with two numbers: 1 and 2, the best diff of 1 and 2 is 1 again and again it is optimal since N = 4k + 2 and sum = (2k)(4k + 3) is odd. In the last case we have numbers 1, 2, and 3, we can place them so diff will be 0 which is optimal.The code import sys n = int(sys.stdin.readline()) g = [] ls, rs = 0, 0 for i in xrange(n, 0, -1): if ls <= rs: g.append(i) ls += i else: rs += i print abs(ls - rs) print '{} {}'.format(len(g), ' '.join(map(str, g))) `
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 i have solved it through the editorial way get ACCEPTED VERDICT but i cant figure out why my solution is not working plzz have a look at that it will be very beneficial for me both u and have applied the same thing but u done in mathematical way i done it through observation plzz understand my code link is above :_)
•  » » 3 years ago, # ^ |   0 i understand completely ur code i have done the same thing but in different way but after seeing ur algorithm i detected my mistake thnkss for ur algorithm :)
•  » » » 3 years ago, # ^ |   0 I'm glad it helps! Your welcome! :)
 » 3 years ago, # |   +4 This tutorial is not attached to the contest (I can see only Announcement link from there).
 » 3 years ago, # |   0 Problem F can also be done using sqrt decomposition.
 » 3 years ago, # | ← Rev. 3 →   0 can anyone tell me why there are 11 pairs for n=15 in Div2D problem 1-8 2-7 3-6 4-5 9-10 8-11 7-12 6-13 5-14 4-15
 » 3 years ago, # |   0 Don't you think the editorials should be more elaborate(eg they can include one example).
 » 3 years ago, # |   0 Can anyone please explain why in problem D we are adding P/2 to the answer when P <= n+1 ?
•  » » 3 years ago, # ^ |   0 Because you can take P/2 pairs to form P as sum. Take as example, P = 9 and N+1 something bigger. To form P = 9 as sum of two numbers you can take, 1-8, 2-7, 3-6, 4-5. As you can see if you continue you will take 5-4 which is similar to 4-5. So moving until the middle of P gives you all the pairs and so P/2 occurs.
•  » » » 3 years ago, # ^ |   0 thanks alot i got it now :-)
 » 3 years ago, # |   0 I've been stuck for ages... anyone know what test #33 was on div2E? http://codeforces.com/contest/899/submission/33345602My answer is 1 + the correct answer. :(
 » 3 years ago, # | ← Rev. 3 →   0 Another solution for F :Store the positions of every character in an array of Sets (like the tutorial)...Then after each query we can find the original position which has the Kth order after the previous updates by storing original positions in a Binary Search Tree, such as Treap which I used and delete them from the tree while applying the query. Therefore you can get the range query according to the original positions then you can remove positions from the corresponding set using lower_bound like the Tutorial..(Sorry about my bad English)
 » 3 years ago, # |   0 in C for 5998 the answer should be 0bcoz if n is even then we can always keep all the numbers whose %4 gives 1 or 0 in the first group, while others in the second group. This always give us an absolute difference of 0.plzz correct me if I m wrong?
•  » » 3 years ago, # ^ |   0 sorry I found out my mistake, but could anyone provide a proof for C
•  » » » 3 years ago, # ^ | ← Rev. 5 →   0 Link to a submission based on my proof:36503825Let's consider first when n is even. Suppose that our solution is A = {2, 4, 6, ..., n} and B = {1, 3, 5, .., n - 1}. We see that , and therefore the difference between A and B is exactly . We can reduce this difference to zero or one by swapping elements between A and B.If we swap two elements x and x - 1 from A and B respectively we see that we have decreased the absolute difference by exactly two and, in general, we will only be able to reduce the difference in even amounts. Given that the difference is we need this amount to be even in order to be able to reduce it to zero or, in other words, n must be a multiple of 4. If it is not, we will only be able to reduce it to 1. After performing swaps the difference will reach one of these two values.If n is odd we have A = {2, 4, ..., n - 1}, and B = {1, 3, 5, ..., n} , and these two solutions can be transformed again to vectors that have difference zero or one by swapping x with x + 1 that belong to A and B respectively. The same arguments about being a multiple of 4 hold for the floor of
 » 2 years ago, # | ← Rev. 2 →   0 Жесть я даун
 » 2 months ago, # |   0 I think Binary Search tag is missing in Problem F.
 » 5 days ago, # |   0 Problem E is tagged with flows , i wonder how can we solve this using max flow ?