### gridnevvvit's blog

By gridnevvvit, 8 years ago, translation,

Soon (on October 24, 21:00 MSK) you are lucky to participate in Codeforces Round #275 for both divisions. Pay attention to the round begining time!

Problems have been prepared by team Saratov SU #3 with members: Gridnev Vitaly (gridnevvvit), Danil Sagunov (danilka.pro), Roman Kireev (RoKi).

We want to thank Max Akhmedov (Zlobober) for help with preparation of this round, Maria Belova (Delinur) for translation of statements and Mike Mirzayanov (MikeMirzayanov) for marvelous Codeforces and Polygon systems.

Scoring system:

Div1: 500 1500 1500 2000 2500

Dvi2: 500 1000 1500 2500 2500

UPD:

Contest finished, congratulations for winners!

Div1:

Div2:

• +191

 » 8 years ago, # | ← Rev. 3 →   -113 how to solve the div2 D,please help me
 » 8 years ago, # |   +78 I am really sorry to say but some of your previous contests english translation was quite really bad to understand . If possible please provide explanation of test cases . Hope this time everything will be fine and everyone will enjoy it :)
 » 8 years ago, # |   +2 first round after my 1700+, gl & hf!
•  » » 8 years ago, # ^ |   +7 And I hope that my first Div. 1 round will be on the next contest...
•  » » 8 years ago, # ^ |   0 Same here ;-)
 » 8 years ago, # | ← Rev. 2 →   +110 Sherlock comix in prevous edit.
•  » » 8 years ago, # ^ |   +39 This is probably some hella smart & funny joke, but I just didn't get it.
•  » » » 8 years ago, # ^ |   -10 I'm not sure, but active CF users who watched "Sherlock" should understand the concept (at least).
•  » » » » 8 years ago, # ^ |   +26 Waiting for Sherlock's new season...
•  » » » » » 8 years ago, # ^ |   +2 make sure that better than waiting game of thrones cause everytime who reads books, s\he gives spoiler
•  » » » » » » 8 years ago, # ^ |   +6 Still better than watching Persona 4 before completing it, it completely messed up my wish to grind the exp to just know that Teddie is a actually a person :O.
•  » » 8 years ago, # ^ |   0 Konstantin.Zakharov awesome :D one of the creative comment post i have ever seen here :D
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 Thanks!
•  » » 8 years ago, # ^ |   -12 I wonder what colour Sherlock and Mycroft would have on codeforces, if they were real and were programmers.
•  » » 8 years ago, # ^ |   0 I just hope that the round won't be "boring" :))
 » 8 years ago, # |   +7 Whoa the round is at midnight in my country. Overslept is not an excuse.
•  » » 8 years ago, # ^ |   +9 Sleep is for da weak.
 » 8 years ago, # |   -6 I want to participate in the contest very much!However,it's at 1 a.m in China,we must stay up!
 » 8 years ago, # |   -39 thank you!your problem is hard or easy?your contest has very good problem .!
 » 8 years ago, # | ← Rev. 2 →   +26 Please short explanation for problems.Also explanation of sample tests." THANKS FOR READING
 » 8 years ago, # |   +21 wow I'm so happy there are so many new contests on CF these days. Hopefully this pace won't go down in the future!
 » 8 years ago, # |   +9 If the time is corrected, Some of Chinese Coders may start coding from 1:00 a.m. to 3:00 a.m. and waiting the system test until 3:30 a.m. Then sleep for a while and participate the regional warm-up contest. The next day(Sunday) participate the regional onsite contest for 5 hours. What a Fighting weekend.
•  » » 8 years ago, # ^ |   +12 Definitely no Chinese coders will compete in this round if they are going to participate in ICPC regional just on next day. They just need good rest.
•  » » » 8 years ago, # ^ |   +13 Good night~ wake up at 00:30 a.m.
•  » » » » 8 years ago, # ^ |   0 So admirable！
•  » » » 8 years ago, # ^ | ← Rev. 2 →   +8 Alas, I (Chinese coder) really want to compete in this round, though I will not participate in ICPC regional, just the point is that our dormitory's blackout and my laptop can't afford to complete this competition …… ╮(╯▽╰)╭
 » 8 years ago, # |   0 If only the round beginning time would be advanced to regular 19:30 MSK suitable for most participants.
 » 8 years ago, # |   0 Where do i go to register for the contest. not allowing me to do so
•  » » 8 years ago, # ^ |   0 Wait for a few hours.
•  » » » 8 years ago, # ^ |   -86 you are such a fool and person
•  » » » » 8 years ago, # ^ |   +55 He certainly is a person, no arguing with that :D
•  » » » » 8 years ago, # ^ |   +1 I'm sorry.sepehr103 wrote this comment when I was logged in the PC in the class
 » 8 years ago, # |   +18 Any particular reason for the unusual timing of the round ?
 » 8 years ago, # |   +4 Timing is perfect for me again, thanks ;-) 19:00 CEST, typically it's 17:30 which is too early to be finished at work...
 » 8 years ago, # |   +7 @gridnevvvit Your last round was a DIV2 round and the round you arranged before it was a DIV1 round . so , it's good to see you coming back with a DIV1 round once again :)
 » 8 years ago, # |   -7 Smiling:)
 » 8 years ago, # |   +5 Omg the starting time of the contest is coincides with my sleeping time :))
•  » » 8 years ago, # ^ |   +20 Unfortunately, sleep was delayed because it coincides with codeforces round 275. here is the new time
 » 8 years ago, # | ← Rev. 2 →   +22 There has been a lot of math in recent contests! Hope for something algorithmic! :D
 » 8 years ago, # |   0 First Div. 1 :) Gl & Hf everyone
•  » » 8 years ago, # ^ |   +19 and your first Div1 has no 1000pt problem :D
 » 8 years ago, # | ← Rev. 2 →   +4 I dont understand why this congruency works sometimes :Scoring system will be announced later == Registrations are closed 5 minutes before the round. Why delay it so long as in few minutes before the contest? Why delay it anyways?? Any specific reasons that I dont know of?
•  » » 8 years ago, # ^ |   0 Suspense :D
 » 8 years ago, # |   +1 How to Solve division 2 Problem-:B ?
•  » » 8 years ago, # ^ |   +3 i think with binary search
•  » » 8 years ago, # ^ |   0 i solved it recursively. consider lower bound of allowed numbers to be L. the absolute minimum numbers you need to consider is cnt1+cnt2. so you look at numbers from the range [L,cnt1+cnt2+L-1]. the numbers divisible by both x&y cant be gifted. from the remaining numbers those divisible by x were gifted to second frnd and those divisible by y were gifted to first friend. now the numbers left can be gifted to either friend.After some thinking you can argue that they should be gifted to first friend and if some are left even after that then to the second. the arguement for this is based on the fact that x < y.i am sure you can think of it :). after updating cnt1 and cnt2. apply the process recursively with new lower bound as cnt1+cnt2+L (i.e. upperbound of previous process +1).
•  » » » 8 years ago, # ^ |   +3 I tried a solution like that but it wasn't working for me. I ended up using the fact that for any choice of v, there will be v/x multiples of x, v/y multiples of y and v/(x*y) multiples of both x and y (since x and y are unique primes).You can figure out how many free choices you have left and increment v accordingly.
•  » » » » 8 years ago, # ^ |   0 my solution wasn't accepted, either the logic is faulty or my implementation.
 » 8 years ago, # |   +20 How to solve C DIV1 problem ? . Thanks in advance.
 » 8 years ago, # |   0 How to solve Div-1 A ?
•  » » 8 years ago, # ^ |   +13 The first (n — k) numbers could be 1,2,3 ... (n — k) after which we print n, n — k + 1, n — 1,n — k + 2 .... for the rest of the numbers.
•  » » 8 years ago, # ^ |   +11 First, follow a pattern 1, n, 2, n-1, 3, n-2, ...; do it k-1 times. Than add remaining numbers in the natural order (decreasing or increasing depending on k's parity).
•  » » 8 years ago, # ^ |   0 I printed 1 and then printed p=1+k, then decreased k by 1 and then printed p=p-k and continued the series. Like, if k=3 and and n is anything arbitrary for an instance, I printed 1 4 2 3. Notice the difference in each adjacent values. And in the end I printed all the remaining values less than n.
•  » » 8 years ago, # ^ | ← Rev. 2 →   +6 That one's pretty easy. The task asks you to find some array of length n so that the amount of absolute value of differences of each two consecutive elements is equal to k.I did it that way: Our answer: 1 n 2 n-1 ... n/2 And if we are about to print the (k+1)-th number we just print our latest number (- OR +) 1 which will make it look that way: For example: N = 9, K = 3 1 9 2 3 4 5 6 7 8 And N = 9 K = 4 1 9 2 8 7 6 5 4 3 As you have probably noticed if K mod 2 is equal to 0 then we print our latest number - 1. Else: latest number + 1.Pretty easy solution and easy to write down, work time: O(n)edit: whoops, i think i'm late for a party
•  » » 8 years ago, # ^ | ← Rev. 3 →   +1 Not accepted yet, but I think it will be so... :) With first k elements You just can generate something like this: 1 1+k 2 2+(k-2) 3. Every needed difference will be here, k = |1+k — 1|, k-1 = |2 — 1+k|, k-2 = |2+(k-2) — 2|, k-3 = |3 — 2+(k-2)| ... And now, after that, just write the rest, n — k elements, one by one: 1+k+1 1+k+2 1+k+3 ... n-1 n. Difference between 1+k+1 and previous element is for sure not greater than k since k>=1 and previous element has to be between 2 and 1+k. Sorry for my English :)EDIT: Aldiyar explained similar solution much better in his post, but it wasn't there when I was writing mine, sorry for doubling answer :)
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 for the C div 2 Problem I made the required sequence as -n n-k n-k+(k-1) (n-k)+(k-1)-(k-2)...till k-i equals 1 and then following left over terms would be placed in decreasing order.eg for n=6, k=3; 6 3 5 4 2 1eg for n=15, k=7; 15 8 14 9 13 10 12 11 7 6 5 4 3 2 1
 » 8 years ago, # |   +2 So guys what do you think about the difficulty level of div2 probs?
•  » » 8 years ago, # ^ |   +19 A-As Usual Difficulty. B-Very Much tricky. Perfect Problem who loves math. C seems easier to most of the div2 contestants but I got lots of pain and still not sure if it will pass. D was an awesome problem. No Idea how to solve it. E- I saw factional output — pressed ctlr+F , looked for a word "expected", found it and immateriality closed the tab.
 » 8 years ago, # |   +1 How to solve problem B of div2 ?
•  » » 8 years ago, # ^ |   +2 Binary search
•  » » » 8 years ago, # ^ |   0 can you please explain the some more, i used a different approach and would like to know how to do it with binary search :).
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   +3 All you need to do is to see if a particular N (1..N) can be split into the 2 sets. Let S1 and S2 be the sets for friend 1 (with prime x) and friend 2 (with prime y) respectively We can observe that in a set we can put the multiples of other prime.S1 = {all multiples of y — multiples of x*y} S2 = {all multiples of x — multiples of x*y} The elements that can go in either sets are: Remain = N — multiples of x — multiples of y + multiples of x*ySo just check if using Remain you can satisfy the deficiency in S1 and S2.http://codeforces.com/contest/483/submission/8395374
•  » » » 8 years ago, # ^ |   0 Bad, it is mathematics.
•  » » » » 8 years ago, # ^ |   +6 Relevant profile picture
•  » » » » » 8 years ago, # ^ |   0 thx
 » 8 years ago, # |   +1 How was Div2 B supposed to be solved?
•  » » 8 years ago, # ^ | ← Rev. 2 →   +10 I solved it using segment trees (sadly after the contest). Initially set all the values to 0 and the if a query(L,R,V) comes, update all the values in the range(L,R) with (a[i] = a[i] | V where L <= i <= R).while joining nodes in the segment tree do seg[node] = seg[2*node] & seg[2*node+1] and finally check for each query_range whether the bitwise and (&) of all the values equals to the required value i.e check value(L,R) = V . This got AC .
•  » » » 8 years ago, # ^ |   0 He was asking about Div2 B, not Div1 B :D
•  » » » » 8 years ago, # ^ |   +9 sorry, seems i commit mistakes even after the contest.
•  » » » » » 8 years ago, # ^ |   +3 I wanted to know how to solve Div1 B as well :P So, thanks :)
•  » » 8 years ago, # ^ |   +5 Some people used binary search, I did not. My approach is as follows:1.Set the answer=cn1+cnt2 initially.2.Then you can fulfil the requirements of the first friend by giving the numbers to him which are not acceptable by the second friend and vice versa.3.Let the friend with more requirement of numbers be friend1(cnt1>cnt2).Then you can give the numbers in the range [1,answer] not already given to any of them to friend 1. Then if his requirement is done you can give the remaining numbers to friend 2. If you see that both friend's requirement is done then you can print the answer else you can increment answer by sum of remaining requirements of both friends and repeat from step 2.
•  » » 8 years ago, # ^ |   0 i solved taking a long long a = cnt1+cnt2, & then checking if a — (a)/(x*y)>= cnt1+cnt2; if false, then a+=(cnt1+cnt2-(a-(a)/(x*y))), and so on. becouse the numbers that are multiples of x*y cant be taken as answer in any of the two cases. You have to check in the same way if there are enough numbers int the interval that aren't divisible by x, and the same whith y.
•  » » » 8 years ago, # ^ |   0 Is that working for 3 1 2 3 input? a = 3 + 1 = 4 a - a/6 >= 1 + 3 return 4 but the result is 5 — it was first input from problem statement...
 » 8 years ago, # | ← Rev. 2 →   +24 I think 1 sec for B and C is too strict.
•  » » 8 years ago, # ^ |   +11 Totally agree, especially if you submit in Scala :(
•  » » 8 years ago, # ^ |   +21 In C, it's necessary to kill off O(nm2m) solutions.
•  » » » 8 years ago, # ^ |   +1 But unfortunately some of them have passed:(
•  » » » 8 years ago, # ^ |   -13 it is not necessary, it can be made greedy
•  » » 8 years ago, # ^ |   0 Yes, I got TLE just because of using scanner in Java instead of buffered reader. 2 seconds would have been better
 » 8 years ago, # |   +68 so the author thinks that div1 B as hard as div1 C ?
•  » » 8 years ago, # ^ |   +8 I agree.Let's hope that no source with correct idea will get TLE.It wouldn't be nice...
•  » » » 8 years ago, # ^ |   +26 Yeah.The hope is not enough...I took TLE with my 2^m*n complexity which works much better in practice.If this was the official complexity, than that limit is too small.In the other case, the pretests are not good(nobody took TLE on pretests)
•  » » » » 8 years ago, # ^ |   +8 There are sources which pass the tests and have 2^m*n like mine, so, anyway, the time limit should be bigger for letting the sources which are not optimized at maximum to get AC to...the problems were very nice anyway.
 » 8 years ago, # |   +4 Accepts for C is more than B in DIV2 :D
 » 8 years ago, # |   -50 I dislaked A — div1 very much. f*ck math.
•  » » 8 years ago, # ^ |   +46 no math lol
•  » » » 8 years ago, # ^ |   -33 well, unnatural mathematical constraints.
•  » » 8 years ago, # ^ |   +49 I don't think that's considered math? At least to me it seems like simple logic.
•  » » » 8 years ago, # ^ |   -16
 » 8 years ago, # |   +6 Too fast SysTest . Hope Rating update will also be this fast :D
 » 8 years ago, # | ← Rev. 2 →   +6 I could not optimize C in time. Unfortunately it works 1.2 secs at worst case :(UPD: Thank god, codeforces faster then my pc. :D
•  » » 8 years ago, # ^ | ← Rev. 2 →   +15 You can use Custom invocation to see how long it would take on their servers.
 » 8 years ago, # |   +13 Not sure if I'm stupid or just bad at constant optimization — is a 50*20*2^20 solution supposed to pass for div 1 C?
•  » » 8 years ago, # ^ |   +3 My 50*2^20 got TLE, so I'm guessing no.
•  » » 8 years ago, # ^ |   +3 If so then 1s TL is not enough for such tight constraints.
 » 8 years ago, # |   0 Bye Bye div1 :(
 » 8 years ago, # |   +59 In what world are B and C the same difficulty? :DI'm curious what the hell did the author think
•  » » 8 years ago, # ^ |   0 Maybe it was meant to work in 50*20*2^20 =(
•  » » » 8 years ago, # ^ | ← Rev. 3 →   0 We did not notice, that idea of solution with working time O(len·2len) (len = length of strings) is too hard.
•  » » » 8 years ago, # ^ |   +10 Well then 1s is a horrible time limit. And even so, I think the problem is still harder.
•  » » 8 years ago, # ^ |   0 You maybe mean "C and D".
•  » » » 8 years ago, # ^ |   +3 No, I meant that the author gave 1500 for both B and C while the results show their complexity to be slightly different
•  » » » » 8 years ago, # ^ |   0 In general, it's hard to evaluate problem difficulty once you know the solution (especially if you wrote it and tried a few variants).Hmm, but there are three authors... Typically, getting a couple of others to test a problem gives you a good idea about the difficulty...
•  » » » » » 8 years ago, # ^ |   0 True that it is hard, but except the three authors there is usually a tester/helper (I guess Zlobober in this case) who should detect such miscalculations.I'm really curious of the solution, maybe it does look simple once you know it.
•  » » » » » » 8 years ago, # ^ |   0 Actually I found a way to improve my 50*20*2^20 solution to 20*2^20 fairly easily, but the explanation would be pretty long. The solution is that if X is a set of questions, then DP[X] is the average of DP[X|(1<
•  » » » 8 years ago, # ^ |   +3 No, B and C. They were worth the same number of points, and the actual gap in difference is dramatical.
•  » » » » 8 years ago, # ^ |   0 Οhh sorry. Misunderstooding :D.
•  » » 8 years ago, # ^ |   +7 Not only that .This is the condition in DIV2 ->
•  » » » 8 years ago, # ^ |   0 Yep, serious mistakes in complexity predictions. I guess it would've been really good to use dynamic scoring if the authors weren't too sure .
 » 8 years ago, # |   +3 Good bye Yellow!
 » 8 years ago, # |   0 Wow, a lot of systest fails and hacks in C. I'm wondering if most of the failed submissions mixed up string length and n somewhere.
•  » » 8 years ago, # ^ |   0 WA22 is the case n = 1. My solution printed 1 while the answer is clearly 0. I saw lots of solutions which failed this test.
•  » » » 8 years ago, # ^ |   0 Ok, this seems like a problem with a high probability for cheap mistakes. Not that I'm complaining. It is the only reason why I got such an unprecedentedly good (for me) result.
 » 8 years ago, # |   0 This contest was some difficult then other contests! Are someone explain solution of div 2 B problem??? please explain! (sorry for bad english !)
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 Binary search the answer..... to check whether we can distribute the presents between the friends using a certain v, we can use inclusion-exclusion. this might help : there are exactly n/p numbers between 1 to n which are divisible by p.hope it helps.
 » 8 years ago, # |   0 8387870 Why my submission is skipped ?
•  » » 8 years ago, # ^ |   0 Only the last "Passed pretests" submit is counted.
•  » » » 8 years ago, # ^ |   0 it was the only submission .
•  » » » » 8 years ago, # ^ |   0 wasn't! 8387870 and 8393488
•  » » 8 years ago, # ^ |   0 because you cheated it
•  » » » 8 years ago, # ^ |   0 No i didn't cheat
 » 8 years ago, # |   0 What was the expected time complexity for problem C?
•  » » 8 years ago, # ^ |   0 I had O(N * 2 ^ string length)
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 O(L*2^L) as mentioned in a comment above. Turns out the idea behind such solution is way harder than authors thought. I think O(N * 2^L) also passes, but most of the solutions were something like O(N*L*2^L) and failed.L — string length
 » 8 years ago, # |   0 I had tried to use unsigned long long and cin>> in D2B problem, but on my system it was wrong, signed long long works properly. Anybody knows why it may be?
 » 8 years ago, # |   0 Testcases in div1 C seem to use CRLF line feeds (not LF). I think it is unusual in Codeforces.
 » 8 years ago, # |   0 Can any one please explain how to solve Div-1 B ?
•  » » 8 years ago, # ^ |   0 interesting for me too, after ends I wrote O(2*m*n), so TL.
•  » » 8 years ago, # ^ |   +5 I used segment tree to find possible answer and another segment tree to check that answer is correct.
•  » » 8 years ago, # ^ |   +3 Segment tree with updates on segments. 8393603
•  » » » 8 years ago, # ^ |   +5 ohh, i think like adamant , feeling proud of myself :P
•  » » 8 years ago, # ^ |   +9 For each constraint ... We iterate over the bits of q ... if the ith bit is turned on ... then it means that all elements in the range (l,r) have this bit turned on as well ... else if the ith bit is turned off ... then it means that at least one element in the range(l,r) has this bit turned off.So for all the turned on bits ... We turn on this bit on all the elements in range(l,r)After that for the turned off bits ... We check that the range(l,r) contains at least one position where this bit is turned off.We can use either segment tree or cumulative sum and binary search to implement this idea.
•  » » » 8 years ago, # ^ |   0 WoW! Amazing!
•  » » » 8 years ago, # ^ |   0 Can you please explain this statement — "We iterate over the bits of q". What is q here?
•  » » » » 8 years ago, # ^ |   0 The same q in the input description.The value for each interval
 » 8 years ago, # |   0 Can anyone please tell me why WA at test case 24 for problem c div 2 . code i handle the condition k == 1 then print ( i + 1) . whats going wrong here .
•  » » 8 years ago, # ^ |   +3 you used sync_with_stdio(false) and printf together , which will do unexpected thing
•  » » » 8 years ago, # ^ |   0 ThanQ moinul.shaon :)
 » 8 years ago, # |   0 Rating has been updated.. time to press F5!
•  » » 8 years ago, # ^ |   +48 anyone who saw your comment must be already refreshed his/her browser.
 » 8 years ago, # | ← Rev. 2 →   +1 So night before yesterday I got 4 hours sleep, I did 6 hours of exams yesterday and got < 4 hours sleep before this contest.I went from 12th in last contest to 517th in this one.Damn.
 » 8 years ago, # |   +9 Spent whole contest trying to code D, and only now realized the solution is deceptively simple: note that the number of ways to color a subtree is the product of the number of ways to color each of its children, plus the same product for the reverse order. Or it would be, if it weren't for double-counting.Turns out that the combinations that will be double-counted are the ones in which every painted subtree has an even number of painted vertices, or every painted subtree has an odd number of painted vertices and the number of painted children is odd.
 » 8 years ago, # | ← Rev. 2 →   +1 Great Contest!! Finally above 1700Btw, can anyone help me out with this http://codeforces.com/contest/483/submission/8393197Problem D,div2I tested it one ideone as well but it is giving runtime error there too.I basically used bitwise range tree to solve the problem.Please help
 » 8 years ago, # |   +16 Looking at number of TL's on C i realize how small is amount of coders who check their solutions in custom invocation before submit:)
 » 8 years ago, # |   0 Can anyone help me with my code for Div1-B?I saw some solutions very similar to mine, but I am not finding any bug or seeing why my approach does not work.Thanks.
•  » » 8 years ago, # ^ |   +1 SOLVED
 » 8 years ago, # | ← Rev. 2 →   -15 First 4 minutes of contest: how I do programming and solving problems, screencast. [EDIT: now not private]
•  » » 8 years ago, # ^ |   0 Video is private.
 » 8 years ago, # |   0 In Div 2 B, I didn't do binary search but derived a direct O(1) formula based answer and it passed. Here is my code : code. Is my solution correct or were the testcases weak??
•  » » 8 years ago, # ^ |   +15 10 7 3 5your solution output — 17right answer — 18
•  » » » 8 years ago, # ^ |   0 Testcases are weak.
 » 8 years ago, # |   0 can someone tell me how to solve div2 D????
•  » » 8 years ago, # ^ |   0
•  » » 8 years ago, # ^ |   0 Segment tree,I guess.
 » 8 years ago, # |   0 where is the editorial of the round ?
 » 8 years ago, # | ← Rev. 2 →   0 When editorial going to be published? In addition, very surprised to see that Division 2 B problem was much harder than C problem (by statistic)
 » 8 years ago, # |   +6 Problem --> Interesting Array (CF Round 275): Div.1/B or Div.2/DTourist's code : http://ideone.com/c5dTmYIn this problem, for every set bit in query, we set the corresponding bit for all the numbers in the given range. I can't understand how he's doing that by:s[from[k]][j]++; s[to[k] + 1][j]--;Also, for calculating the number of set bits for a given bit position, for a given range of numbers, he's made some sort of cumulative array. Please explain its construction:bal += s[i][j]; a[i][j] = (bal > 0); sum[i + 1][j] = sum[i][j] + a[i][j];
•  » » 8 years ago, # ^ | ← Rev. 3 →   +10 I will try to explain by posing a different problem:Given m queries of the form a, b, p; Add p to each element between arr[a] to arr[b]; Length of the array is n.Trivial solution will do it in O(m * n);To optimize, what you can do is, add p to arr[b]. And add -p to arr[a-1];Those two units of information is enough to let you know that you want to add p from arr[a] to arr[b].Keep on doing that for all m such queries.Finally, do, something like: arr[n-1] += arr[n]; arr[n-2] += arr[n-1]; arr[n-3] += arr[n-2]; ... ... arr[2] += arr[3]; arr[1] += arr[2]; arr[0] += arr[1]; So, just one final loop like above can add p to all elements between arr[a] to arr[b] for all such m queries.Complexity is: O(m + n)Try it on paper.
•  » » » 8 years ago, # ^ |   0 Thank you so much for you explanation!
 » 8 years ago, # |   -20 became red :D
 » 8 years ago, # |   +18 What's wrong with the editorial ? i can't see it now, but some days ago i can reading it.
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 translating maybe. the last time I saw the solution of two last problems were written in Russian
 » 8 years ago, # |   +2 Why is the tutorial not accessible now? It was accessible a few days back..!!
•  » » 8 years ago, # ^ |   0 You can read the editorial in the google's web cache : http://webcache.googleusercontent.com/search?q=cache:vSOKoA-5IqwJ:codeforces.com/blog/entry/14417+&cd=1&hl=es-419&ct=clnk&client=iceweasel-a
•  » » » 8 years ago, # ^ |   0 Thank you so much..!! :D
 » 8 years ago, # |   0 Only solved A，but rating +13.
 » 8 years ago, # | ← Rev. 2 →   0 Why am I getting TLE in problem B(div 1)? My complexity is 32*nlogn*3 which is approximately 6*10^7, that I think should pass in 1 sec. My code is here
•  » » 8 years ago, # ^ |   0 Factor of luck
 » 4 years ago, # |   0 There is a wrong comment in a comment in a problem 1 Wrong comment: In the first sample pair (2, 4) is not coprime and pairs (2, 3) and (3, 4) are. correct comment: In the first sample pair (2, 4) is not coprime and pairs (2, 3) and (3, 4) are comprim.