By scott_wu, 5 years ago,

Hello everyone! The first round of the 8VC Venture Cup will be held on Saturday, February 13th at 12:35PM EST. ecnerwal and I are the problem setters. We want to thank GlebsHP for his help in preparing the contest, Delinur for translating the problems, and MikeMirzayanov for creating the Codeforces platform

The contest is for competitors in both divisions and contains seven problems. The scoring distribution is as follows:

500 — 750 — 1000 — 1500 — 2000 — 2500 — 3000

The contest will be slightly longer than usual — two and a half hours. The top 200 contestants will advance to the final round, and the top 20 local finishers will be invited to Woodside, CA to compete onsite. Good luck!

UPD: System testing is now over. Congratulations to the top contestants:

The top 200 contestants will advance to the final round in two weeks. Congratulations!

The editorial can be found here.

• +351

 » 5 years ago, # | ← Rev. 2 →   -64 I hope This contest will be very interesting and there are many hacks. Good luck every one !!!
•  » » 5 years ago, # ^ |   +42 How do you know? And by the way being among the top 100 while having solved only 3 problems (because of hacks) is not a good thing.
•  » » » 5 years ago, # ^ | ← Rev. 3 →   +41 being among the top 100 while having solved only 3 problems (because of hacks) is not a good thing. but being among the top 20 while having solved only 3 problems (because of hacks) is a very good thing. :DI think nothing is not good in being in the top 100, if you solve problems or make successful hacks both are allowed in CF rounds. If you did not cheat then you deserve this place.
•  » » » » 5 years ago, # ^ |   +5 I was about to say among the top 20 but then changed it to 100 when I remembered that there're gonna be Div. 1 participants :D And by the way I am proud of my rank in that contest, but I'm not proud of my performance. A participant who solved the forth problem would have deserved my rank much better.
•  » » » » 5 years ago, # ^ |   +11 Hacks are good when you open the source code of another person and try to find a bug (which is really challenging and who makes it successfully deserves a higher rank), not when you find a test case that's not included in the pretests and keep refreshing the room for new participants to hack with that same test.
 » 5 years ago, # |   +19 The score gaps of the first three problems is close => Must solve fast.
 » 5 years ago, # |   -30 tourist is joining, how high will his rating go?
 » 5 years ago, # | ← Rev. 2 →   0 Hope that all legendary masters will compete. Very big prizes!!!
•  » » 5 years ago, # ^ |   +56 I am not sure, but scott_wu would probably win ;)
•  » » » 5 years ago, # ^ |   -13 I notice that codeforces authors seldom participate in their own contests, do they?
 » 5 years ago, # |   +2 Is it rated?
•  » » 5 years ago, # ^ |   +13 YES
•  » » 5 years ago, # ^ |   +88 Most asked question of the year.
 » 5 years ago, # |   -6 Cant wait for it.
 » 5 years ago, # | ← Rev. 3 →   -54 Good luck everybody.
•  » » 5 years ago, # ^ |   +81 How do you know that letters will be ABCDEFG? Are you a cheater?
•  » » » 5 years ago, # ^ |   -51 Yes i am a cheater. First problem A.Distrubition 500.A: binary search, segment trees
 » 5 years ago, # |   +8 What does top 20 local finishers mean? Is there also an onsite version of this round?
•  » » 5 years ago, # ^ |   0 Local means people who can get to San-Francisco by their own (organizers do not cover transportation expenses)
•  » » 5 years ago, # ^ |   +12 People who marked "I would like to compete onsite in finals" during a registration. Organizers don't pay for travel so likely only people living close to Woodside want to attend onsite finals. Thus, "local finishers".
 » 5 years ago, # |   -27 Перевод на русский будет?
 » 5 years ago, # |   -6 It feels nice, inspiring and much exciting to compete with the Div 1 participants.
 » 5 years ago, # |   0 So lately!
 » 5 years ago, # |   -116 Oh money money.Wwonder who will be the first , and takes the money.1st place 2500\$tourist will still rich ))
•  » » 5 years ago, # ^ |   +21 As always, jokes about tourist :/
•  » » 5 years ago, # ^ |   +34 One of the 100 ways to raise contribution — to write about tourist.
•  » » » 5 years ago, # ^ |   +10 And post a picture of him.
•  » » » 5 years ago, # ^ |   +104 One of the 100 ways to lost contribution — post huge pictures.
•  » » » » 5 years ago, # ^ |   +136 Another is to correct someone's grammar, (lost — lose)
•  » » » 5 years ago, # ^ |   +39 A way for tourist to raise contribution — to write anything)
 » 5 years ago, # |   -6 I have a few problems solved, but I didn't succesfully register :-(
 » 5 years ago, # |   0 Sorry I'm asking this here.If someone registers for a contest and sees the problems but makes no submission will their rating be changed ?
•  » » 5 years ago, # ^ |   +1 No, rating change only happens after you make a submission.
•  » » » 5 years ago, # ^ |   0 Yayyyy :)))
•  » » » 5 years ago, # ^ |   +40 I personally think the current system should be changed — anyone who sees problems should be automatically counted. There seem to be a lot of people who register but decide not to submit anything after they find out they can't solve enough problems to boost their rating. About 5500 registered, but only about 3000 are in standings. There are probably some people who couldn't just make it to the contest, but there are also probably a lot who just look at the problems and go away after finding them too difficult.
•  » » » » 5 years ago, # ^ |   +10 Unfortunately in your case there will be a lot of twice account guy in CF, every cheater can register another account to see whether problems are difficult or not. As consequence we will have inflation of rating(all fake account will fall in rating). Anyway, cheaters gonna cheat.
•  » » » » » 5 years ago, # ^ |   +8 That is true — there is no perfect way to block cheating. However, a lot more people will hesitate when they realize they are doing something that explicitly breaks the rules (IIRC registering and not submitting due to problem difficulty is not breaking the rules).
•  » » » » 5 years ago, # ^ |   0 I've found out that even if someone who submitted their solution(s) thinks that he'll get less points than he wants to, he starts decreasing his current points by bad hacks until it turns negative, which will not effect his rating.
 » 5 years ago, # |   +75 "Without looking, they hand their balls to Harry"
 » 5 years ago, # |   +3 Okay, for E, am I right that I only need 1,2,3 or 4 elements? I couldn't handle the 4-case :(
•  » » 5 years ago, # ^ |   +10 If I'm right, you never need an even number of elements, but you might need an odd number of elements bigger than 4. Example:5 0 0 0 13 13Optimal solution is to take all 5 elements.
•  » » » 5 years ago, # ^ |   +3 Oh, thanks! :)
•  » » » 5 years ago, # ^ |   0 Why odd number of elements is enough? The problem kind of pushes towards this conclusion but I could not see why is it true.
•  » » » » 5 years ago, # ^ |   0 I'm not going to post the whole algebra here, but basically, suppose you have an optimal subset with an even number of elements, the middle ones being A1 and A2. Now consider the same subset without A2, and you'll see the simple skewedness can only increase by removing that element, which means the original subset wasn't actually optimal.
•  » » 5 years ago, # ^ |   0 NO 6 2 2 2 3 12 12
•  » » » 5 years ago, # ^ |   0 Thank you! :)
 » 5 years ago, # |   +1 How to hack C? QAQ
•  » » 5 years ago, # ^ |   0 I used 9 4
•  » » 5 years ago, # ^ | ← Rev. 2 →   +6 6 3I think I got hacked this way. I used greedy then after getting hacked I switched to binary search.P.S. I thank the guy who hacked me so that I at least have 400+ points instead of 0 by failing System Tests.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Is 14 the right answer? If it is, then greedy probably works. Here is the link to my greedy solution: link.
•  » » » 5 years ago, # ^ | ← Rev. 3 →   0 Greedy? Binary search? Take a look at my submission. It passed all hacks described here, and I hope, it will pass sys. tests: 16001257 UPD: Yes, it passed. But maybe it is greedy too.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 7 6 -> ans 206 4 -> ans 15I used these two.
•  » » 5 years ago, # ^ |   0 I used just 2 random big numbers.
 » 5 years ago, # |   +61 difficulty : A
 » 5 years ago, # |   0 How to solve F?
•  » » 5 years ago, # ^ |   +61 Sort by value and then dp[open_intervals][cost_so_far]. When we move from i to i+1 then cost_so_far changes to cost_so_far + open_intervals * (t[i+1]-t[i]).
•  » » » 5 years ago, # ^ |   +14 Can you please define Open Intervals ?
•  » » » » 5 years ago, # ^ |   +18 The number of groups (intervals) for which we have already processed at least one element but there is at least one non-processed element. In other words, the first element of a group (interval) is not greater than i, and the last element is greater than i.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +20 Another possible solution (with much worse complexity, yet fast enough to pass) :We are interested in having difference between sum of all "left endpoints" and all "right endpoints" at most k. Let's calculate dp[open_intervals][current_difference]. When considering new element, it can either start new interval (and increase current sum of "left endpoints") or join some existing interval; in both cases it can either close interval (and increase sum of "right endpoints") or keep it open.
•  » » » » 5 years ago, # ^ |   0 I did this and got TLE :(
•  » » » » 5 years ago, # ^ |   -8 It sounds like you're describing the same solution. The "current difference" can be big, but that can be solved by indexing using "current_difference-open_intervals*current_number"; if you write down how it changes the rules for opening/closing, you arrive at errichto's formula.
•  » » » » » 5 years ago, # ^ |   +33 It's easy to see that it isn't the same solution because the complexities are different. The solution which I_love_Tanya_Romanova described with your optimization (which is what I implemented) has (n * max(ai) * k) states, while errichto's doesn't depend on the actual values of the integers in the array. Of course, as max(ai) = 500 in this problem, it's clearly good enough.
•  » » » » » » 5 years ago, # ^ |   -17 From the point of view of someone who went from I_love_Tanya_Romanova's solution to errichto's, they are one solution in finished&unfinished versions :D
 » 5 years ago, # | ← Rev. 2 →   0 For Problem F, can someone explain me why the answer at the second test is 13 and not 15 ? :/ EDIT : ok I got it.
•  » » 5 years ago, # ^ |   0 hey how to get 13 not 15?
•  » » » 5 years ago, # ^ |   0 The total imbalance must me lower than k, and not the imbalance of each group.
 » 5 years ago, # |   +1 I guess, the statement of problem C is not describe clearly.
 » 5 years ago, # | ← Rev. 2 →   +4 C had weak pretests / made for hacks :D I wish i read "alphabetically" earlier in B :( Cost me 3 WA
 » 5 years ago, # |   +1 So, can anyone please explain why the result of 2nd sample case in task F is 13?I've manually calced it on paper like 10 times in different ways and keep getting 15.
•  » » 5 years ago, # ^ |   +5 All(15) — [7,10][8,9] — [7,9][8,10]
•  » » 5 years ago, # ^ |   +4 You need to keep TOTAL imbalance at most k (meaning sum of imbalances of sets)
•  » » » 5 years ago, # ^ |   0 Ah I see. I've somehow missed it :(
 » 5 years ago, # |   +8 I'm sure that there are many people confusing when they read "so no two students’ towers may contain the same number of blocks" in problem C. While it should be no two towers have the same height.
•  » » 5 years ago, # ^ |   +8 I also got confused when the problem said that the students were stacking the blocks lengthwise.
•  » » 5 years ago, # ^ |   0 There is a clear distinction between pieces and blocks in the statement. IMHO no confusion.
 » 5 years ago, # | ← Rev. 2 →   +15 I'm really upset. I can't pass the Examples while I'm working on F. Finally I found a bug but there are only 16 seconds left. I was too exciting to submit my code properly. (I had a mistake when copying my program and it got CE.)upd:Now I feel much better because I got TLE on test 11. (⊙o⊙)
•  » » 5 years ago, # ^ |   +8 Unluckily. But I didn't know how to solve F, even now QwQ
 » 5 years ago, # |   0 Could anyone explain test 8 for E?I have completely no idea :(
•  » » 5 years ago, # ^ |   0 OK, got it
 » 5 years ago, # |   +26 In E, I quickly found out that we need 2 intervals (in the array sorted left to right), where the middle element/s have to be in the first one and the second one touches the right end. I couldn't move from that point for over an hour...
•  » » 5 years ago, # ^ | ← Rev. 2 →   +5 I saw several passed solutions that looks like this: make ternary search in one part, in another, make binary search in another place, and check another 100 places. I don't think that it is solution supposed by authors.
•  » » 5 years ago, # ^ |   +10 Let's assume that the median is fixed. We need to find optimal k (that is, the length of the suffix). Key observation: if we consider "skewness" as a function of k, it's convex and ternary search is applicable to it(can be verified by writing down all sums and seeing what happens if we increase k by one).
•  » » » 5 years ago, # ^ |   0 I see. I briefly considered ternary search as one of my guesses, but didn't try to prove con[vex/cave]ity.
•  » » » 5 years ago, # ^ |   0 All I could guess from looking at examples, was that it was a monotonous function, so I coded binary search and it failed pretest 8, guess I looked at poor examples..
•  » » » 5 years ago, # ^ |   0 I got WA7 with that solution. Is there any problems with floating values?
•  » » » » 5 years ago, # ^ |   0 No. 16008582
•  » » » » 5 years ago, # ^ |   0 I got WA 7 when I used > instead of < in my ternary search.
•  » » » 5 years ago, # ^ |   +41 How do you handle equal values of mean with ternary search?e.g. 0 0 0 0 1 2 2 2 2If you fix median = 1, then there're lots of equal value of mean for different values of k
•  » » » » 5 years ago, # ^ |   0 If the mean doesn't change, it doesn't matter which one you pick :D
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   +8 That's a small example. It could be something like:0 1 1 1 1 10 99 100 100 100 100If you fix median = 10, the mean changes at some point, but your ternary search doesn't find it.Zlobober's comment answered my question though.
•  » » » » » » 5 years ago, # ^ |   0 change if (f2(mid, k) < f2(mid+1, k)) { r = mid; } else l = mid; to if (f2(mid, k) < f2(mid+1, k)) { r = mid; } else l = mid + 1; you will get ac :)
•  » » » » » » 5 years ago, # ^ |   0 My ternary search doesn't find anything because I don't have any ternary search :DIn fact, I said the same thing as Zlobober. It doesn't matter which value you pick out of an interval of identical ones. Look at ternary search as binary search for a point where the difference between consecutive values of the given function (a prerequisite of ternary search is that it's monotonous) changes sign from  > 0 to  ≤ 0; it's more obvious that way.
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   +15 Actually, as you take elements from right to left from both sides, there may be no more than one segment of equal values for the function we are willing to maximize. And this segment corresponds to the maximum value of a function as it is concave.
•  » » » 5 years ago, # ^ |   +5 Could you prove why it is convex? I spent a while trying to prove this during contest, but my thought were too messy, so I took a risk and submitted it without a proof and as it turned out, that was a good decision, however I am still not convinced why this works.
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   +36 Not sure how to prove it's convex, but it's somewhat easy to see it's bitonic, which is good enough.What happens when we increase size by two? We move from S/n to (S+a+b)/(n+2). As we know, the latter lies between S/n and (a+b)/2. (a+b)/2 continuously decreases (since we move to the left). So while (a+b)/2 is greater than the current mean, we will get an increase, and when it starts being less, we will always get a decrease.
•  » » » » » 5 years ago, # ^ |   +26 And it seems to me that it's not actually convex. If we have something likeaaa...aaabbb...bbbmxxx...xxxyyy...yyy(number of bs=number of ys<
•  » » » » » » 5 years ago, # ^ | ← Rev. 2 →   +5 Can you show an actual example? I'm quite satisfied with an explanation I provided below.UPD: got it, my explanation below is an explanation of bitonicity. Of course the slope of a line joining the origin and the point on the convex polygon doesn't have to be convex itself.
•  » » » » » » » 5 years ago, # ^ |   +39 import matplotlib.pyplot as plt %matplotlib inline n1 = 100 n2 = 10 vals = [0.0] * n1 + [1.0] * n2 + [2.0] + [3.0] * n1 + [4.0] * n2 def Mean(count): all = vals[n1 + n2 - count : n1 + n2 + 1] + vals[len(vals) - count:] return sum(all) / len(all) plt.plot(range(n1 + n2 + 1), [Mean(x) for x in range(n1 + n2 + 1)]) 
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Ahhh, right, thanks :). I had similar thoughts during contest, but couldn't join them to get that proof, however if I'm not mistaken there's still a flaw in your proof (or something that doesn't sound as you wanted to) -> "current mean always increases" (which is obviously just a silly mistake since you wanted to show it's bitonic :). That mean increases up to point where that (a+b)/2 becomes smaller than mean. After it, mean also decreases, but slower than (a+b)/2 (it will be larger than previous value of (a+b)/2), so (a+b)/2 will stay smaller than mean, so after that point mean is decreasing.
•  » » » » » » 5 years ago, # ^ |   +10 Yeah, the first version was incorrect, but I've updated my comment as if it never happened :)
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +5 It can be seen as a slope of a line joining the origin and the point whose x-coordinate is number of taken integers and y-coordinate is their sum. As you increase the number of taken integers, the differences between consecutive y's are non-increasing (since the numbers that we add are non-increasing), so it looks like a concave polygon in positive quadrant that we draw a tangent to from an origin.UPD: this is not an explanation why the function we are willing to maximize is convex, but it is a proof that it is bitonic (i. e. first increases, then decreases).
 » 5 years ago, # | ← Rev. 2 →   +24 My B passed pretests during the contest. Why did it fail test 1 during system tests?Edit: I found a typo that makes it fail pretest 1. Yet it somehow passed all pretests the first go around. It was merely a typo and I fixed it here. I would have quickly fixed it during the contests if it told me that pretest 1 failed.
 » 5 years ago, # |   +2 207 T_T
 » 5 years ago, # |   +31 Is me only one who thinks that problem C should be more elaborated :/. I read PS thrice before i figured out what it meant :(
•  » » 5 years ago, # ^ |   +43 I agree. Russian statement is about impossible to understand (at last I switched the language).
•  » » » 5 years ago, # ^ |   +4 Even in English it took some time to understand.
•  » » 5 years ago, # ^ |   0 No. It also has the first explanation wrong. It should be written '2' instead of '4'...
•  » » » 5 years ago, # ^ |   +1 It isn't wrong. 2, 3, 6, 9 and 3,4,6,9 both are acceptable i think
•  » » » 5 years ago, # ^ |   +4 4 is also acceptable so the explanation is right.
•  » » » » 5 years ago, # ^ |   +5 Oh, so maybe I didn't understand it even after the end of the contest :) It happens.
•  » » » 5 years ago, # ^ |   +4 Both 2 and 4 is correct.
•  » » » 5 years ago, # ^ |   0 how 4 came?
 » 5 years ago, # | ← Rev. 2 →   +113 Btw, it is me, or today codeforces was running like 5 times faster than usual? Literally no page load longer than 1 second, and pretests was really fast too.
•  » » 5 years ago, # ^ |   +3 Me too, No lag during hacks too. And its combined round
•  » » 5 years ago, # ^ |   +8 System tests was extremely fast too.
•  » » 5 years ago, # ^ |   +7 It was perfectly prepared round at all. And i have not any problems with translation. Thanks a lot for everyone!
 » 5 years ago, # |   -23 Conclusion : US Round = Math Round
 » 5 years ago, # |   +21 It's 4:23 a.m. in China, And I think I must go to bed to have a rest. So Tired QwQ
•  » » 5 years ago, # ^ |   0 So many of us are with you.XD
 » 5 years ago, # |   0 Can any one please tell me why this submission to D fails in 6th test 16007337
•  » » 5 years ago, # ^ |   -10 (2000*1999)^3 > 2^64You have to divide by 8 somewhere in between.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Overflow at B = N * N * N * (N - 1) * (N - 1) * (N - 1). Before division this term overflows. Your accepted code with the changes 16008548
•  » » » 5 years ago, # ^ |   0 Thanks!!
 » 5 years ago, # |   0 Failed due to integer overflow on problem D :(. Was sitting for so long not understanding why my code was failing :(
 » 5 years ago, # |   0 Auto comment: topic has been updated by scott_wu (previous revision, new revision, compare).
 » 5 years ago, # |   +9 Who thinks B was harder than C ?
•  » » 5 years ago, # ^ |   0 I didn't even understand C.
•  » » 5 years ago, # ^ |   0 B is easier as algorithm, but harder in terms of implementation accuracy (a lot of possible cases).
•  » » » 5 years ago, # ^ |   -6 No, you are wrong. You can take a look to my solution — there is not a lot of different cases. And algorithm is even easier as yours :) 16007975 The only thing because of I have not solved it is 200 instead of 201( I had lost a lot of time and was very busy, so, done really stupid mistake.
•  » » » » 5 years ago, # ^ |   0 So, you are saying that 10 IF statements is not a lot of cases? :)
•  » » » » » 5 years ago, # ^ |   0 Okay... but still not 14 "if" and 6 "else" ;)
•  » » » » » » 5 years ago, # ^ |   +1 Now just multiply all your IFs on recursion depth and compare :)"Easier" is not a synonym for "shorter code".
•  » » » 5 years ago, # ^ | ← Rev. 7 →   +5 I've found a short and easy solution: 15992405 without many ifs and elses
 » 5 years ago, # |   +18 The top 200 contestants will advance to the final round in two weeks.Currently, there are 2 people in 200th place (me and Nikitosh), so what will it be? XD
•  » » 5 years ago, # ^ |   0 Both will advance probably :)
•  » » 5 years ago, # ^ |   +12 I am in 203rd place. Only three places from final(((
 » 5 years ago, # | ← Rev. 3 →   +34 Memory limit exceeded in F, though the array is int[][][] dp = new int[n + 1][n + 2][K + 1], which is 201*202*1001*4 ~ 160Mb, while memory limit is 256Mb. 16003432Running max test (n=200, k=1000) in "Custom Invocation" shows 309828 KB of memory usage.Running test with (n=184, k=1000) shows only 128488 KB.
 » 5 years ago, # |   0 Thanks for the contest. I'm interested in editorialReminds me that I must work more on proper technical execution, I spent too much time finding "i" instead of "1" bugs. Also I knew that numbers in D must be sorted, I thought I sorted them and did not understand why pretest fail.. Only a few minutes after the end of contest I realized how close to success I was.A. Is a nice example of "read constrains" problem. Surely naive solution is not the fastest, but it is fast enough.
 » 5 years ago, # |   +39 Identical participant output results in different checker's comment:http://codeforces.com/contest/626/submission/16002527participants output: 3 0 475712 999999checker output: wrong answer jury found better answer: expected simple skewness 262143/3, found simple skewness 48575/48575http://codeforces.com/contest/626/submission/16008372participants output: 3 0 475712 999999checker output: wrong answer jury found better answer: expected simple skewness 262143/3, found simple skewness 48575/3
•  » » 5 years ago, # ^ |   +5 Also seems to give Denial of Judgement when I try to print some stuff to debug: [submission:http://codeforces.com/contest/626/submission/16009256]
•  » » » 5 years ago, # ^ |   +18 Yes, checker crashed if you output some large number first. That happens. No one was affected during the contest anyway.
•  » » » 5 years ago, # ^ |   0 Checker is OK now, submission was rejudged.
•  » » 5 years ago, # ^ |   0 We noticed bug in checker's comment during the contest and fixed it. So the first submission was made before the bug was fixed.
 » 5 years ago, # |   +4 How to solve D?
•  » » 5 years ago, # ^ |   0 Store all the possible differences in a frequency array . such that freq[i]= number of pairs such that their difference =i . eg if array is 1 2 10 freq[1]=1(2-1) freq[8]=1(10-2) freq[9]=1(10-1). Now make a cumulative array such that A[i]= number of pairs such that their difference is greater than or equal to i. Now for value for every pair of difference value find the number of pairs which have value greater than this pair . i.e if Winning points were a in first round and b in second round you need number of pairs such that winning round is greater than a+b(which is A[a+b+1]. multiply all the case and divide by (nc2)^3 Code
•  » » » 5 years ago, # ^ |   0 And which is the proof about this solution?
•  » » » 5 years ago, # ^ |   0 Thanks :)
 » 5 years ago, # |   0 Worst contest for me ! I submitted the same code which got WA (first submission) second time thinking i got WA on my corrected code :'( and submitting the corrected code got AC . trying not to cry
 » 5 years ago, # |   +112 Failed systests in 2 problems because of overflow
•  » » 5 years ago, # ^ |   +25
 » 5 years ago, # |   +26
•  » » 5 years ago, # ^ |   +80 Wait for my scrincast with russian rap
•  » » » 5 years ago, # ^ |   +59 Can you code and sing at the same time?
 » 5 years ago, # |   +11 Are there any other contests before the final round? Or there will be 2 weeks without any contests...
 » 5 years ago, # |   +5 Only one more Legendary grandmaster till all in the top rated be Legendary grandmaster. ;)
 » 5 years ago, # |   0 B: once you have many cards of the same color, it doesn't matter if you have 4 or 100000. You get the same result. This means you could implement the most naive bruteforce you can think of — and it will be fast enough — after you truncate the input to max 4 cards of each color.
•  » » 5 years ago, # ^ |   +6 min(2, n) cards of each is enough to decide :)http://codeforces.com/contest/626/submission/16008137
 » 5 years ago, # |   0 can someone please tell me why this solution for problem D gives TLE 16009986let m be max element , so my solution runs in O(m^2) and m < 5000 I think 25m operation with 2 seconds isn't too much thanx :)
•  » » 5 years ago, # ^ |   +6 Your solution complexity is O(m^2 log m^2) as you insert elements in a map; which should run in logarithmic time with a large constant factor — as you're inserting ~25M elements there. Try reducing this by removing the map and using arrays directly for storage and indexing.
•  » » » 5 years ago, # ^ |   0 thanks for correcting me ,yes it is O(m^2 log m^2) . fixed and got AC .
 » 5 years ago, # |   +5 No editorials?
 » 5 years ago, # |   0 Can somebody tell me what principle/algorithm is used in this solution for 626C - Block Towers 15992435, when taking a large segment from 0 to INF and then narrowing down to the correct answer? Looks like a binary search, but why does this work here?
•  » » 5 years ago, # ^ |   0 It is binary search! :D
•  » » 5 years ago, # ^ |   0 We are using binary search on possible answer. We know that if x is possible that all values greater than x are possible. Similarly, if x is not possible, all values less than x are not possible. So take min=0 and max=INF and calculate mid. If mid is possible then our answer will be greater than or equal to mid else less than mid. Iterate till only one possible answer is left which will be the answer.
 » 5 years ago, # |   +3 Why I've passed pretest ? The pretest just have one testcase? :))
•  » » 5 years ago, # ^ |   0 Why I get TLE ? on 2 RG ? for submission ? 16006497
•  » » 5 years ago, # ^ |   0 Same thing happened to me. Except for test case 1. So I passed pretests but managed to fail test 1, which was just the sample test case. I'm pretty salty that the first sample case wasn't in the pretests.
•  » » 5 years ago, # ^ |   0 I think they made a clarification that test 2 is not equal to pretest 2, and gave the data for test 2.
•  » » » 5 years ago, # ^ |   0 I will clarify my question: Why my solution gets TLE on codeforces while working fine on my machine.E.g.: Time: 2000 ms, memory: 7920 KB Verdict: TIME_LIMIT_EXCEEDED Input2 RB
 » 5 years ago, # |   +8 I really need some advice about programming. Yesterday I did problem C, and I was quite sure about the solution, only to find the failed system test. When I checked, what I did wrong was missing a small, simple but crucial character "=". How do good coders avoid such silly mistake?
•  » » 5 years ago, # ^ |   0 Practice, practice, practice,test your code before you submit (try and make up some test cases so you make sure all of your code in all cases have been run, except if you're very confident),double check your code before you submit.Those 3 things I guess. I also still struggle with quite a few things like that as I'm new as well. I failed D because I hadn't used long long but the rest was just fine :(. It's sad, I know, I think we all know that feeling being programmers haha.
 » 5 years ago, # |   +21 I wonder how much rating gain Bus will get if he did not purposely lowered his point o.O
 » 5 years ago, # | ← Rev. 2 →   0 Could somebody tell me why my solution to D fails on test 2? On my machine it works perfectly, but on custom invocation it fails, even if I manually set br = 2, total = 27? My solution: http://codeforces.com/contest/626/submission/16013981
•  » » 5 years ago, # ^ | ← Rev. 2 →   +10 if(b[i] && b[j] && i + j < 5200){ br += dp[i + j + 1] * b[i] * b[j]; } Out-of-bound access.i + j < 5200 => i + j + 1 < 5200
•  » » » 5 years ago, # ^ |   0 Too late
•  » » » 5 years ago, # ^ |   -10 Well, I think you are wrong — if the array dp has 5201 elements, so i + j + 1 < 5201 => i + j < 5200
•  » » » » 5 years ago, # ^ |   0 There is some problem with long double on CF, yeah, I know it sucks :/
 » 5 years ago, # |   +43 Anything known about top 20 local finishers?