### malcolm's blog

By malcolm, 7 years ago, translation,

Hey there!

Today at 19.30, Moscow time there will be Codeforces Round #319 and it's strongly disadvised to skip it.

I'm the author of this round, my name is Dima Gorbunov and it's my first round on Codeforces. I really hope you're going to like it and everyone will find a satisfying problem. In order to increase the probability of finding that task, please read all of the problem statements.

As usual, I'd like to thank Zlobober for his invaluable help and his special sense of humour, sankear for coding additional solutions, Delinur for the English statements and MikeMirzayanov for amazing systems Codeforces and Polygon.

You're going to have two hours to solve 5 problems. Good luck!

UPD. The scores in first division are 500-1250-1250-2000-2750.

In second division — 500-1250-1500-2250-2250,

UPD2. Because of large size tests for some of the problems, system testing will be slow (it's possible that it will take several hours). Thanks for your patience!

UPD3. English editorial is also accessible.

UPD4. Winners!

Div1:

1). Marcin_smu

2). mnbvmar

Div2:

1). latisel

2). wrong_order

3). ntitry826

A special respect to al13n for correct solution of Div1.E during the contest!

• +302

 » 7 years ago, # |   +14 Registered with bells on :)
•  » » 7 years ago, # ^ |   -6 the man in your pic look very depressed.make me crie evrytiem ;_;
•  » » » 7 years ago, # ^ |   0 He is a well-known poet in Egypt.. called Ahmed Shawky :)
•  » » » » 7 years ago, # ^ |   +11 Anyway this pic is much more better and possitive=)
 » 7 years ago, # |   -36 If it can be postponed for 24 hours, that will much better. Friday is not weekend. Go to school or go to work prevent us from getting up late, even though we participate in Codeforces Contest in the evening.
•  » » 7 years ago, # ^ |   +26 Please do NOT postpone it.
•  » » » 7 years ago, # ^ |   +3 Of course it won't be postponed. I just complain about the time for me~ However, I am curious for the reason why you disagree with postpone?
•  » » » » 7 years ago, # ^ |   +32 What about the fact that after moving it 24 hours forward it will clash with TC SRM?
•  » » » » » 7 years ago, # ^ |   +10 Oh......What a busy weekend!
•  » » » » » 7 years ago, # ^ |   +16 I want to start doing TopCoder, but its awful interface discourages me as soon as I open the site. And its applet isn't that good too.
•  » » » » » » 7 years ago, # ^ |   +17 You shouldn't worry about interface, but rather the problems. In general, topcoder problems have better english and more clear explanations, and the challenge phase is a rather interesting element.
•  » » » » » » » 7 years ago, # ^ |   0 Do u know any tutorial about playing Topcoder? I have tried several times but still dunno how to start.
•  » » » » » » » » 7 years ago, # ^ |   0 Have you tried reading the official guide? It is a bit outdated but still conveys the idea.
•  » » » » 7 years ago, # ^ |   +34 Oh I have mentally prepared myself for this evening. :P
•  » » 7 years ago, # ^ |   +3 for me and a lot of contestants Friday is weekend :)
•  » » » 7 years ago, # ^ |   +8 Why? Don't you need to go to school or work on Friday?
•  » » » » 7 years ago, # ^ |   +39 In Egypt our weekend is (Friday & Saturday) not (Saturday & Sunday) :)
•  » » » » » 7 years ago, # ^ |   0 Improved My GK! :)
•  » » » » 7 years ago, # ^ |   +4 In Muslim countries weekend is Friday
•  » » 7 years ago, # ^ |   +2 Usually I tend to miss lectures that has CF rounds conflicting with them.It certainly feels different and the rush is better :D
 » 7 years ago, # |   -14 Thank you for contest, I think in this contest will be interesting and a lot of hacks. Sorry for my poor english
•  » » 7 years ago, # ^ |   +13 Why do you think that there will be a lot of hacks?
•  » » » 7 years ago, # ^ |   +20 I like hacks , they save u getting system test failed.
•  » » » » 7 years ago, # ^ |   +9 I didn't say that I don't like hacks. I just wonder why he is in this thought..
•  » » 7 years ago, # ^ |   +3 this contest had more system test failed than hacks.. :(
 » 7 years ago, # |   +1 Will the problems be sorted in an ascending order of difficulty?
•  » » 7 years ago, # ^ |   0 the statement in the post: "In order to increase the probability of finding that task, please read all of the problem statements" means alot
•  » » » 7 years ago, # ^ |   +3 I think it doesn't, since "that task" refers to "everyone will find a satisfying problem". The question wasn't if the problems will be sorted in ascending order of satisfying-ness.
 » 7 years ago, # |   +1 weekend or not weekend ,i hope contest will be running.Because it is div2 round and it will happen after a long time.
 » 7 years ago, # |   0 Thanks for this holding this CF round and hope everyone can get good score!
 » 7 years ago, # |   +2 I hope the problems will be short and to the point. Not with long stories.
•  » » 7 years ago, # ^ |   -23 But I hope The problems will be short and the point. Not with long stories.
•  » » 7 years ago, # ^ |   +13 But I hope the problems will be short and intersting, Not with direct statement "please calculate something"
 » 7 years ago, # |   -30 Wish me positive contribution :P
 » 7 years ago, # |   0 looking forward for your first set of problems :D
 » 7 years ago, # |   -8 Hope that more contests will be scheduled at 11:00 instead of 11:30
 » 7 years ago, # |   +49 Time to lose red!
•  » » 7 years ago, # ^ |   +3 who know maybe time to get new max :)
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 Do you have any pointers on how to get out of green zone?
•  » » » 7 years ago, # ^ |   +30 Increase your rating to 1500+ :D
•  » » » » 7 years ago, # ^ |   +41 Or probably decrease it to 1200- :D
•  » » » » » 7 years ago, # ^ |   +9 No thanks EKGMA :p
•  » » » 7 years ago, # ^ | ← Rev. 3 →   +14 If you are heavily color-blind like me then you already look red!
•  » » » 7 years ago, # ^ |   0 you have to solve at least A and B to stay at the blue zone.Along with those, solve C and your chances to be purple are pretty high.
•  » » » » 7 years ago, # ^ |   0 I hate A,B. And I suck at C,D. Its a viscious trap.
•  » » » 7 years ago, # ^ |   0 You did it :D Congrats.
•  » » » » 7 years ago, # ^ |   0 Thanks! It feels good to see the progress as a color change.
•  » » 7 years ago, # ^ |   +1 Yay, I was right! :(
•  » » » 7 years ago, # ^ |   0 Hah, it seems we rise and fall together. If only C had 3-4 seconds instead of 2...
•  » » » » 7 years ago, # ^ | ← Rev. 3 →   0 I hope you never again use c++ streams, your C passes in under 1 second using printf...http://codeforces.com/contest/576/submission/12963316
•  » » » » » 7 years ago, # ^ |   0 NOOOOOOOOO
•  » » 7 years ago, # ^ |   0 Or time to lose bottom yellow, after this revolution. :P
 » 7 years ago, # |   0 hope understand from first time read :3
 » 7 years ago, # | ← Rev. 3 →   +25 Did you notice that registration finishes as time contest starts not 5mins before... P.S No That was an error I think? When I looked both times were same..
•  » » 7 years ago, # ^ |   +2 Not anymore =(
 » 7 years ago, # |   0 Thanks to author!contest was great,how to solve "Modulo Sum"?
•  » » 7 years ago, # ^ |   0 Seconded! How to solve Modulo Sum. ?A proof of solution will also be nice :).Hate this contest.
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 I used set, but might TLE. Saved all possible modulo remainders for each element, basically.
•  » » » 7 years ago, # ^ |   0 That's not enough. You need to combine each remainder with each remainder to get new remainders.
•  » » » » 7 years ago, # ^ |   0 Yeah that's what I did. Instead of iterating over a 10^3 array, I used set, that's all. But sets have a huge constant associated with them, which is what is making me nervous.
•  » » » » » 7 years ago, # ^ |   0 And you can also combine the remainder with itself certain number of times. I cannot view the solutions yet, but I'd like to see how you solved that.
•  » » » » » » 7 years ago, # ^ |   0 "And you can also combine the remainder with itself certain number of times." why?
•  » » » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 For example,3 31 1 1
•  » » » » » » » » 7 years ago, # ^ |   0 There was given sample test6 65 5 5 5 5 5So obviously, he must have considered that.
•  » » » » » » 7 years ago, # ^ |   0 Actually, you can't sum one number more than once, the only strange thing was that after n, the subsecuence could continue in 1, but without repeating any number.
•  » » » » » » » 7 years ago, # ^ |   0 its actually coin-change. treat the remainders as the coin that you have, how many numbers can you make. check through these numbers to see which are divisible by m. and you are done.
•  » » » » » » » » 7 years ago, # ^ |   0 NO, is not like that, because is a subsecuence, not a subset, a subsecuence is of continuous numbers.
•  » » » » » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 It didn't have to be a contagious subsequence. One of the examples had a non-contagious solution: 4 6 3 1 1 3  YES 
•  » » » » » » » » » 7 years ago, # ^ |   0 Yes, but I thought It could be circular, so, after the final 3, continues the first one.
•  » » » » » » » » » 7 years ago, # ^ |   0 contagious=transferrable, like diseases contiguous=one after another
•  » » » » » » » » 7 years ago, # ^ |   +1 At least that is what I thought, but now I see my answer received a WA in the 39 tests
•  » » 7 years ago, # ^ |   0 I solved with recursion with memorization
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 I think there's no way it's impossible if N >= M. My not-very-rigorous-but-you-get-it proof:Imagine you're doing a simple dynamic programming solution, with the elements sorted in ascending order first. If a number's multiples "circled back" all the way to 0 (this might mean going around the modulo space several times), we're done. So assume that didn't happen yet. If we can prove this means we'll always get at least one possible new modulo value when adding each number, it's proven. So take a new number X. There are 3 possibilities: This number already occurred. It can't have circled back, so by adding it to the last iteration, we get a new value. It's a multiple of a previously occurring number. Since that number hasn't circled back, we can get several new values just like we did in the first case (from the last few iterations). It's a relative prime to all that occurred before. Obviously, X%M hasn't occurred before, so that's a new value.
•  » » » 7 years ago, # ^ |   -8 i found this during the contest http://math.stackexchange.com/questions/699857/proof-subsequence-of-n-integers-is-divisible-by-nif you understand the proof please explain it here in plain english. thanks.
•  » » » » 7 years ago, # ^ |   0 this is a different problem. for this subsequence, it doesnt have to be contiguous, whereas the link that you have shown seems to talk about subsequence in contiguous form.
•  » » » » » 7 years ago, # ^ |   0 But if there is a contiguous subsequence, then there definitely is a not necessarily contiguous one. I fail to see how this is not relevant.
•  » » » » 7 years ago, # ^ | ← Rev. 3 →   0 Appears I was right, yay! :D Anyway, what I posted above is a plain English proof of this statement. But I guess the one given on Math SE is simpler, so I'll explain that one as well:Let's assume M == N. I'll only use N in the proof.Let's define the series R_1, R_2 .. R_n like this: R_k is the remainder of the sum of the first k elements, that is, (a_1 + a_2 + .. + a_k) % N. If for some k we have R_k == 0, take that subsequence and we're done.Otherwise, there are N numbers in the R series. They can have N-1 possible values (since none of them was 0). This means there are two equal numbers in R, so there are two prefix sums in the original series whose remainder by N is the same. Let's say R_i == R_j, and i < j. This means that adding a_(i+1), a_(i+2), ... and a_j to R_i didn't change its remainder by N. So the subsequence a_(i+1) + a_(i+2) + ... + a_j has a remainder of 0 by N.This also showed that there must be a CONTAGIOUS subsequence that satisfies this.EDIT: ffao managed to explain this proof much simpler than I did, look at his explanation if you don't get it :)
•  » » » » » 7 years ago, # ^ |   0 thanks for this. btw it's CONTIGUOUS not CONTAGIOUS. :)
•  » » » 7 years ago, # ^ |   0 not-very-rigorous-but-you-get-it proof is good for me :)
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +2 The (easier, I guess?) rigorous proof:Let the sum of the first i elements modulo m be S[i]. There are m different possible values of S[i]. If we find S[i] such that S[i] = 0, we're done. So suppose none of them is zero. By the pigeonhole principle, at least two of S[1], S[2], ..., S[m] must be equal, say S[x] = S[y]. But then a[x+1] + ... + a[y] = S[y] — S[x] is divisible by m!So it's always possible if n >= m.
•  » » » » 7 years ago, # ^ |   0 Thanks GrandMaster ffaoFor the case of n < m, can i add dummy values of 0 so that n >= m and then argue that if we can't find S[x] and S[y] then it was not possible with the initial sequence ?
•  » » » » » 7 years ago, # ^ |   0 Adding dummy values of 0 is not a valid modification as it changes the answer to the problem. That happens because you can always select your newly added 0 as the divisible by m subsequence, which will make it always possible.
 » 7 years ago, # |   +95 What is happening? Why the contest is still running when everybody stopped and there was even a window with information that coding phase has finished?
•  » » 7 years ago, # ^ |   +5 I haven't seen any notification about extending the round and a lot of people too. Was it a bug or there was no notification at all? Nevertheless, I think that the submissions after the original time should not count...
•  » » 7 years ago, # ^ |   +18 The system gone to total gc on 1:23 :( We are working to reduce memory consumption and prevent such situations.We increased contest duration while backed was restarting. Unfortunately, we were unable to send notifications.Right now our highest priority task to fix it. Sorry to inconvenience.
•  » » » 7 years ago, # ^ |   0 No problem, I understand, but I was a bit surprised. Thanks for quick reaction!
•  » » » 7 years ago, # ^ |   +16 People had started discussing the problems too.
 » 7 years ago, # |   +23 Was the round extended? Cause I did'nt get any notifications.
 » 7 years ago, # |   -7 Seriously, no adding minutes for the round? And system is not available last 5 minutes of contest.
 » 7 years ago, # |   +35 Are you going to cancel submits after 2:00?Btw. I lost 5-6 minutes not knowing that round goes on. And I found a bug 10 seconds after the final end. I hope it wouldn't get AC — http://ideone.com/6DVME8
•  » » 7 years ago, # ^ |   +7 Well, at least your contest went without any problems :)
•  » » » 7 years ago, # ^ |   +8 clarification: I'm not ranting. More like crying or something :D
•  » » 7 years ago, # ^ |   +3
 » 7 years ago, # |   0 Thanks for the contest! Nice problems :) How did you solve Modulo Sum?
 » 7 years ago, # | ← Rev. 2 →   +20 I hacked 2 C-div1 problems with carefully written cases to solutions close to what I believe is the correct answer (somehow partitioning the space in chunks of size 1000xsth and move around them properly).However, if they are partitioning them in chunks of something different but close to 1000, my test cases probably won't work because their structure is completely messed up,since they are meant against partitions of 1000 (could have been 1001, nothing special in 1000).Can you come up with a way of creating a challenge that doesn't assume a particular number with which partitioning space? There should exist some of those in system testing, but I cannot come up with them.
•  » » 7 years ago, # ^ |   +3 PS: the system test probably didn't have them because one of the programs I hacked got accepted just by changing the partition number from 1000 to 1500.
 » 7 years ago, # |   0 When will editorial be available?
 » 7 years ago, # |   0 For C div2, My solution is to print all prime and perfect square numbers that are less than or equal 'n'.Why is it wrong ??
•  » » 7 years ago, # ^ |   +5 8
•  » » 7 years ago, # ^ |   +5 you must also print 3, 4,5... powers, that less or equal n
•  » » 7 years ago, # ^ |   +5 for each prime, you print prime^i if this is <=n.
•  » » 7 years ago, # ^ |   0 Do sieve and print all prime powers <=n. It is/not easy to see that we need to do this so that if we have a,b : a|b, then we will avoid printing b because there exist some c : c|b but not a.
 » 7 years ago, # |   +1 How solve problem C div1 ?
 » 7 years ago, # |   +5 Wow , do we have a new dreamoon_love_AA : .o. ?
 » 7 years ago, # |   +84 The problems are awesome. Hard to believe none of them had been used before. =)
•  » » 7 years ago, # ^ |   -18 Why do you call B and C awesome? Some arguments? B is 'write two if-s', C is 'think of the correct partition', both are boring and non-interesting for me.
•  » » » 7 years ago, # ^ |   +45 Well, B ends up somewhat involved while being really simply stated (also I tend to like problems somehow connected to graph isomorphism =)), and C has a constructive flavour which is always nice. The 'think of the correct partition' is for sure more creative than 'implement the segment tree for the bazillionth bloody time'.
•  » » » » 7 years ago, # ^ |   +16 I agree that such original problems are the best. Like misof said, "The less it resembles anything I've seen before, the better!"
•  » » » 7 years ago, # ^ |   0 It is because you are too good For beginner, like me :'( , they are too interesting
•  » » » » 7 years ago, # ^ |   +3 Lol, I'm yellow forever
•  » » 7 years ago, # ^ |   0 The idea of E is old though. For some reason it's still not very overused, I've only seen it maybe four times.
•  » » » 7 years ago, # ^ |   +8 Can you provide some links? malcolm and sankear invented this idea while solving some completely different problem (having nothing common with this kind of semi-online dynamic connectivity) in a pretty complicated but elegant manner.
•  » » » » 7 years ago, # ^ |   0 http://se.math.spbu.ru/SE/diploma/2012/s/Kopeliovich_diploma.pdf(for the dynamic connectivity; the DSU with flags is new to me and was a nice touch)
•  » » » » » 7 years ago, # ^ |   +8 Of course the dynamic-connectivity-offline itself is well-known thing, we do not pretend on inventing it. What I asked you is idea that while traversing the tree of divide-and-conquer we can still modify information in the future in a manner similar to segment tree. Did you see such approach before?BTW, DSU with flags (as I understand you mean a data structure for adding edges and checking if the graph is bipartite) is described on e-maxx.
•  » » » » » » 7 years ago, # ^ |   0 Oh, ok, I guess that's new. Sorry, haven't thought about it as a separate idea. Probably because in the implementation I'm used to it's a straightforward modification.
 » 7 years ago, # |   0 How to solve Div1-D?
 » 7 years ago, # |   0 Div 2 D anyone??
•  » » 7 years ago, # ^ |   0 Div 2.D == Div 1.B
 » 7 years ago, # | ← Rev. 2 →   +1 please make testcase so as to fail all n*m solutions mine n*m failed while this HURTS
•  » » 7 years ago, # ^ |   0 That solution is not n*m. That solution is min(n*m, m*m). (The loop will always break after at most m iterations, for reasons discussed above).In other words, that solution is correct.
 » 7 years ago, # |   0 Anybody who solved C(Div 1) as follows. Divide into 1000 blocks with 10^6x1000 rectangles. in each rectangle sort points by (x[i]+y[i]), I think it can be proven that will give 2n \sqrt(n) bound.
•  » » 7 years ago, # ^ |   0 No, you can create a test giving 3E9 if you don't alternate the sort order.
•  » » » 7 years ago, # ^ |   0 It seems that it works if each block is 1414x10^6.
 » 7 years ago, # |   +5 Why there wasn't any announcement for the extra 10 minutes!!
•  » » 7 years ago, # ^ |   +1 I tried to submit solution 2 minutes before contest end and I could not do it. 15 seconds before end I could submit, but I was not fast enough. I waited 2-3 minutes to see if contest is extended, but it was not. The only good think is that my solution would be incorrect anyway as I checked.
 » 7 years ago, # |   0 Div 2. A. What is a worst test case time complexity for this solution? 12930538.
•  » » 7 years ago, # ^ |   0 It seems to be that the worst case for that solution is a n = 10⁵ and x = Highly composite number below 10⁹. It may be something like divisors(x) * n. On a quick analysis it seems that x has more or less 10³ divisors. So, the result should be 10⁸.
 » 7 years ago, # |   0 In Poblem B module sum : in sample test 3 , why the answer is "YES" ?
•  » » 7 years ago, # ^ |   0 it's about subset, but not continuous segment. p.s. there is explanation under examples
•  » » » 7 years ago, # ^ |   0 but I think That it is about Finding a SubSequence not a subset , and SubSequences must be contiguous !
 » 7 years ago, # |   0 LoL, why this solution gives TLE:12934189? Is it because of using vectors?
•  » » 7 years ago, # ^ |   0 No, because you did O(n*m). Beign n <= 10⁶ and m <= 10³ you have a 10⁹ solution. That's slow.
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 You are dividing 1E9 times but divisions are expensive so you can't make a lot more than 1E8 of them per second.
•  » » » 7 years ago, # ^ |   0 But my solution is O(m^2)( I consider case when n>m).
•  » » » » 7 years ago, # ^ |   0 Ah sorry, I think the problem is that you are reading a million ints using cin, c++ streams are often too slow for such huge input.
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 that would be really sad as i also seem to have O(m**2) but i am reading data with cin :(.I also think this should have been covered in pretests
•  » » » » » » 7 years ago, # ^ |   +1 cin is fine; just add this magical command: ios_base::sync_with_stdio(false);See here.
•  » » » » » » » 7 years ago, # ^ |   0 Magical command helps a lot, but anyway cin is much slower then scanf, even with command.
•  » » » » » » » » 7 years ago, # ^ |   +17 Ironically, I've had my first experience with that just now.But it is fairly rare. Still, I'll use scanf from now on.
•  » » 7 years ago, # ^ |   +1 Do you ever clear xp? I think xp might be getting really big near the final iterations...
•  » » » 7 years ago, # ^ |   0 Oh, thanks. I think that was actual problem:)
 » 7 years ago, # | ← Rev. 2 →   0 Ugh, I only had a bit less than one hour for the contest. To be precise, I'm travelling and the only place where I could do the contest was one train/bus station (next to each other). But the train station's net hotspot didn't work and the bus station only has a 3rd party connection with 1 hour free, then nothing. So I hurried a lot and I think I'm going to fail both B and C.Why couldn't the round be 2 hours earlier... I could've done it at home then...UPD: yes, I failed both B and C.
•  » » 7 years ago, # ^ |   0 Why didn't you leave this one for virtual contest if you were travelling?
•  » » » 7 years ago, # ^ |   +13 Because it'd be yet another one. Most CF contests have had awful dates for me recently (which means the last few months, because there have been so few). When I'm home, there's nothing, then I leave somewhere without net for a few days and a CF contest is guaranteed.
•  » » » » 7 years ago, # ^ |   +5 So, you prefer losing ratings than not enjoying a contest. That is very inspiring Xellos :)
 » 7 years ago, # |   +6 2s * 617sols * 50tests ~ 900 min testing (task C)Where am I wrong?
•  » » 7 years ago, # ^ |   +3 Ok, I can't into parallel calculations and good solutions which work fast (or fail early), but it still slows testing, thank you for the limits
 » 7 years ago, # |   +141 Am I the only one who mistakenly read the constraint in problem C as 2.5·108 instead of 25·108? The common agreement about scientific representation of real numbers is to use normalized notation and according to it the constraint in problem C should've been 2.5·109.
•  » » 7 years ago, # ^ |   +12 You are not alone)
•  » » » 7 years ago, # ^ |   0 And our solutions is very similar. We both tryed to solve it O(n*logn), TL.
•  » » 7 years ago, # ^ | ← Rev. 2 →   +12 At first I also misread it, but the points (1000*i, 1000*j) with 1 <= i,j <= 1000 are such that the shortest Hamiltonian path has length ~10^9
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 In fact it was possible to understand that you understood something wrong by noticing that for the 1000x1000 uniform lattice (all points of form (1000a, 1000b)) the answer has order of 10^9.Nevertheless, you are right, writing 2.5 * 10^9 could've been much better.UPD: oh, Nicolas16 said the same thing before me.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +27 Well, the statement said "it's guaranteed that the answer always exists for given input" so I didn't worry too much about that :)
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   +5 Yeah but then there would have been input where the minimal length is exactly 2.5 * 10^8, which means that we would have had to find the exact minimal path in this particular case (which did not seem to be the the goal of the problem).However, I had to remark all these things during the contests and I lost some time before understanding I misread the bound, so I am not saying you are wrong :-)
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 I thought it was a trick to obscure the desired complexity. 2.5·109 looks pretty much like while 25·108 is «what the wierd constant is it?!»I really thought of it as a nice beautiful obfuscation, no irony here.
 » 7 years ago, # |   0 Too scared to look at my submissions page.
•  » » 7 years ago, # ^ |   0 congrats you passed all three you attempted:)
•  » » » 7 years ago, # ^ |   0 Honestly, I would not have opened the page at all. Thanks for telling me :)
 » 7 years ago, # |   0 Those permutation problems are cool
 » 7 years ago, # |   +22
 » 7 years ago, # |   0 What is special at test 9 from div1B? I looked at my source 10 times bbefore submitting it to be sure I don't miss anything. I've even hacked some sources=)))
•  » » 7 years ago, # ^ |   0 printf ("%d %d\n", nod1, nod2); for (int i=2; i<=N; i++) Isn't this going to miss node 1 if it is not either nod1 or nod2?
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 Yes, it does...stupidest bug ever.Thanks.I don't know why I pressed 2
 » 7 years ago, # |   0 I might be the happiest blue coder to-be ever!!!! Should be out of green right??!!!!
•  » » 7 years ago, # ^ |   0 seems likely all the best !
•  » » » 7 years ago, # ^ |   0 Thanks!! :)
 » 7 years ago, # |   +14 "and it's strongly disadvised to skip it."Nice trap
 » 7 years ago, # |   +22 Look, the green coder latisel is the winner of a Div2 contest!, oh wait look at his previous contest here.
•  » » 7 years ago, # ^ |   +8 Worse than worse . Unbelievable!
•  » » 7 years ago, # ^ |   +11 some red seems to be having FUN!
•  » » 7 years ago, # ^ |   +19 I guess he did so because he was "only" second. That's crazy how people think they will become "famous" by winning a Div 2 contest...
•  » » » 7 years ago, # ^ |   +14 Alone man who won div2 and became famous was just sorry_dreamoon.
•  » » 7 years ago, # ^ |   +14
 » 7 years ago, # |   +34 I passed D with "bad" solution :) Only optimization is order of for loop in matrix multiplication — I remember reading somewhere that you can make naive multiplication cache-friendly by switching order of for loops from i, j, k to i, k, j. And after that, all that's left is a trivial if statement that checks a[i][k] isn't 0 before multiplying it with the for loop with j.
•  » » 7 years ago, # ^ |   +8 I thought about submitting that, but I was pretty sure it wouldn't pass... Guess I shouldn't underestimate the CF servers after all :)
•  » » » 7 years ago, # ^ |   0 Looks like that is the wanted complexity... Makes me think D is a pretty bad problem now, is it just "submit the obvious solution and hope that it passes"?
•  » » » » 7 years ago, # ^ |   0 There is a typo in editorial I think. It should be "it's not enough", not "now enough". So /32 was intended.
•  » » » » » 7 years ago, # ^ |   0 Yeah, it's definitely a mistake, thank you.
•  » » 7 years ago, # ^ |   0 I think I have the same solution (12942073), but it got WA44 and I can't find the bug now...
•  » » » 7 years ago, # ^ | ← Rev. 3 →   +8 Edit: You didn't clear "nextcur".
•  » » » » 7 years ago, # ^ |   0 Oh, really, AC now. Thank you!
 » 7 years ago, # |   0 for DIV2 B: can any one find whats wrong with this submission: http://codeforces.com/contest/577/submission/12944993
•  » » 7 years ago, # ^ |   0 What is this? for(int j=1;j<= ht[i];j++) sum = (sum + i); 
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 after putting number into buckets within %m.....I am iterating over each bucket for count of #'s in it...this loop is for that....Thanks for your reply...I can understand if this goes on and gives TLE but i want to know why WA....
•  » » » 7 years ago, # ^ |   0 Hi....thanks again for looking into my code....it turns out just a shift of loops here and there and it got AC.here is the submission: http://codeforces.com/contest/577/submission/12963454
 » 7 years ago, # | ← Rev. 2 →   0 why does the use of pow function from math library give a WA while without that its AC... Ans 1 : with pow func http://codeforces.com/contest/577/submission/12941362 Ans 2 : without pow func http://codeforces.com/contest/577/submission/12947283
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 Its happening with me too!!!!!codeforces is giving me this output for test case_ 7_**** 19 32 16 8 4 27 9 24 2 3 5 7 11 13 17 19 23 29 31 37 but my system is giving this output! 19 32 16 8 4 27 9 25 2 3 5 7 11 13 17 19 23 29 31 37
•  » » » 7 years ago, # ^ |   0 for me its test case 4... cf : n=15 -> 9 2 3 4 5 7 8 9 11 12 ideone : n=15 -> 9 2 3 4 5 7 8 9 11 13
•  » » 7 years ago, # ^ |   +1 Pow uses floating point values and you round them down when you convert them to ints. It should pass if you add an epsilon.
•  » » 7 years ago, # ^ |   -8 Try using powl()
 » 7 years ago, # |   +139 al13n got 90 tests on problem E, but Endagorion got TL on 96 test, wtf?
•  » » 7 years ago, # ^ |   0 We are already investigating this.
•  » » 7 years ago, # ^ |   +8 Fixed. That was not a judgement error, but only an error of verdict page showing information not for all testcases.
 » 7 years ago, # |   -7 hi.. i think that there is something wrong with codeforces compiler this code gives wrong answer on test4 problem C http://codeforces.com/contest/577/submission/12937746 i tried the same input with the same code on my computer and on ideone (http://ideone.com/hIQ3BM) and it gave the right answer.. could any one pleas tell me what is going on?!!
•  » » 7 years ago, # ^ |   0 You can't trust the pow function since it uses floating point arithmetics.
•  » » » 7 years ago, # ^ |   -7 Thanks JohStraat..but i can't really understand ..is using pow function causes undefined behavior?? ..so what do you suggest instead using pow function in general?
•  » » » » 7 years ago, # ^ |   0 as suggested by dushyant use powl or make your own pow it will be a short function
•  » » » » » 7 years ago, # ^ |   -7 Thank you brighterstill
•  » » 7 years ago, # ^ |   -8 The same problem. Change compiler to MS C++ and it's work now((( WTF?(
 » 7 years ago, # |   -8 Sorry, but my code in test-system get one answer and in my system — another. My algomythm looking for p^k, but in test-system on test 7 I get one of the numbers = 24, instead of 25. It's imposible!! P.S. Problem was fixed by changing compiler in test-system....WTF????? In G++ it get one answer, but in MS C++ another... Seriously??
 » 7 years ago, # |   0 Div1 C checker is awesome!)
 » 7 years ago, # |   +103
•  » » 7 years ago, # ^ |   0 Deja Vu it seems ,Sir :)
•  » » 7 years ago, # ^ |   0 I was thinking about this too when I saw the final standing. LOL
 » 7 years ago, # | ← Rev. 4 →   -8 !
 » 7 years ago, # |   0 I didnt became div1, but I am too close. I hope at future to be :) Thank you for the great contest!
 » 7 years ago, # |   +5 Finally got into Div. 1 ..
 » 7 years ago, # |   +59 Thanks pretests...
 » 7 years ago, # |   +28 2496501499 in C, seems legit :D
•  » » 7 years ago, # ^ |   +10 With 999 endings instead of 500 in 44th test it would go up to ~2990*10^6, buckets should be sorted to avoid that. Solution of Marcin_smu looks hackable too.
 » 7 years ago, # |   0 This is really bad in cf. TLE with cin and AC with scanf for div2 B. These are the solution links 12935258 12951554My rating also went down. It could have gone up
•  » » 7 years ago, # ^ | ← Rev. 2 →   +37 First know how cin works vs how scanf works before blaming codeforces.its good thing your rating went down.
•  » » » 7 years ago, # ^ |   +1 Yes I know that but this almost never happens on codeforces. There are cases when 10^9 complexity solutions are also accepted
•  » » » » 7 years ago, # ^ |   +16 And part of competitive programming is knowing when it is and when it isn't.
•  » » » 7 years ago, # ^ |   +1 Never a nice thing to say :P
• »
»
»
»
7 years ago, # ^ |
0

hi, can u tell me how this works for modulo sum (Div 2 B)

# include <bits/stdc++.h>

using namespace std;

int main() { int n, m; scanf("%d%d", &n, &m); bitset<2001> f; f.set(0); for (int i = 0; i < n; ++i) { int x; scanf("%d", &x); if ((x %= m) == 0) x = m; f |= f << x; f |= f >> m; } puts(f[m] ? "YES" : "NO"); return 0; Thanks,