Hello everyone! The first round of the 8VC Venture Cup will be held on Saturday, February 13th at 12:35PM EST. ecnerwala 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.
Разбалловка объявлена за 3 часа до контеста. Остановите Землю, я сойду.
I hope This contest will be very interesting and there are many hacks. Good luck every one !!!
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.
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. :D
I 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.
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.
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.
The score gaps of the first three problems is close => Must solve fast.
tourist is joining, how high will his rating go?
Hope that all legendary masters will compete. Very big prizes!!!
I am not sure, but scott_wu would probably win ;)
I notice that codeforces authors seldom participate in their own contests, do they?
Is it rated?
YES
Most asked question of the year.
Good luck everybody.
How do you know that letters will be ABCDEFG? Are you a cheater?
What does top 20 local finishers mean? Is there also an onsite version of this round?
Local means people who can get to San-Francisco by their own (organizers do not cover transportation expenses)
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".
Перевод на русский будет?
It feels nice, inspiring and much exciting to compete with the Div 1 participants.
Oh money money.
Wwonder who will be the first , and takes the money.
1st place 2500$
tourist will still rich ))
As always, jokes about tourist :/
One of the 100 ways to raise contribution — to write about tourist.
And post a picture of him.
One of the 100 ways to lost contribution — post huge pictures.
Another is to correct someone's grammar, (lost — lose)
A way for tourist to raise contribution — to write anything)
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 ?
No, rating change only happens after you make a submission.
Yayyyy :)))
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.
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.
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).
"Without looking, they hand their balls to Harry"
Okay, for E, am I right that I only need 1,2,3 or 4 elements? I couldn't handle the 4-case :(
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 13
Optimal solution is to take all 5 elements.
Oh, thanks! :)
Why odd number of elements is enough? The problem kind of pushes towards this conclusion but I could not see why is it true.
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.
NO 6 2 2 2 3 12 12
Thank you! :)
How to hack C? QAQ
I used 9 4
6 3
I 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.
Is 14 the right answer? If it is, then greedy probably works.
Here is the link to my greedy solution: link.
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.
7 6 -> ans 20
6 4 -> ans 15
I used these two.
I used just 2 random big numbers.
difficulty : A<B<C<D<<<<<<<<<<<<<<<<E,F<<<<<<<<<G
How to solve F?
Sort by value and then
dp[open_intervals][cost_so_far]. When we move fromitoi+1thencost_so_farchanges tocost_so_far + open_intervals * (t[i+1]-t[i]).Can you please define Open Intervals ?
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.
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.
I did this and got TLE :(
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.
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.
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
For Problem F, can someone explain me why the answer at the second test is 13 and not 15 ? :/
EDIT : ok I got it.
hey how to get 13 not 15?
The total imbalance must me lower than k, and not the imbalance of each group.
I guess, the statement of problem C is not describe clearly.
Первый раз у меня вырубили свет, когда все засылали В, второй раз — когда все перешли к С. Очень обидно, а ведь я в кое-то веке стал синим — видимо, не надолго. Именно эта небольшая разница в баллах и играет роль в соревнованиях, когда очень многие решают одинаковое количество задач. К слову, что может быть не так с 4-м претестом в D? UPD: как раз-таки та задача, которую я писал с лету после того, как потерял кучу времени, не прошла из-за дурной ошибки — массив на один элемент меньше нужного.
C had weak pretests / made for hacks :D I wish i read "alphabetically" earlier in B :( Cost me 3 WA
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.
All(15) — [7,10][8,9] — [7,9][8,10]
You need to keep TOTAL imbalance at most k (meaning sum of imbalances of sets)
Ah I see. I've somehow missed it :(
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.
I also got confused when the problem said that the students were stacking the blocks lengthwise.
There is a clear distinction between pieces and blocks in the statement. IMHO no confusion.
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⊙)
Unluckily. But I didn't know how to solve F, even now QwQ
Could anyone explain test 8 for E?
I have completely no idea :(
OK, got it
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...
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.
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).
I see. I briefly considered ternary search as one of my guesses, but didn't try to prove con[vex/cave]ity.
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..
I got WA7 with that solution. Is there any problems with floating values?
No. 16008582
I got WA 7 when I used > instead of < in my ternary search.
How do you handle equal values of mean with ternary search?
e.g. 0 0 0 0 1 2 2 2 2
If you fix median = 1, then there're lots of equal value of mean for different values of k
If the mean doesn't change, it doesn't matter which one you pick :D
That's a small example. It could be something like:
0 1 1 1 1 10 99 100 100 100 100
If 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.
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 :)
My ternary search doesn't find anything because I don't have any ternary search :D
In 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.
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.
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.
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.
And it seems to me that it's not actually convex. If we have something like
aaa...aaabbb...bbbmxxx...xxxyyy...yyy
(number of bs=number of ys<<number of as=number of xs)
then we'll have two almost flat segments.
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.
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.
Yeah, the first version was incorrect, but I've updated my comment as if it never happened :)
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).
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.
My bad
207 T_T
Is me only one who thinks that problem C should be more elaborated :/. I read PS thrice before i figured out what it meant :(
I agree. Russian statement is about impossible to understand (at last I switched the language).
Even in English it took some time to understand.
No. It also has the first explanation wrong. It should be written '2' instead of '4'...
It isn't wrong. 2, 3, 6, 9 and 3,4,6,9 both are acceptable i think
4 is also acceptable so the explanation is right.
Oh, so maybe I didn't understand it even after the end of the contest :) It happens.
Both 2 and 4 is correct.
how 4 came?
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.
Me too, No lag during hacks too. And its combined round
System tests was extremely fast too.
It was perfectly prepared round at all. And i have not any problems with translation. Thanks a lot for everyone!
Conclusion : US Round = Math Round
It's 4:23 a.m. in China, And I think I must go to bed to have a rest. So Tired QwQ
So many of us are with you.XD
Can any one please tell me why this submission to D fails in 6th test 16007337
(2000*1999)^3 > 2^64
You have to divide by 8 somewhere in between.
Overflow at B = N * N * N * (N - 1) * (N - 1) * (N - 1).
Before division this term overflows. Your accepted code with the changes 16008548
Thanks!!
Failed due to integer overflow on problem D :(. Was sitting for so long not understanding why my code was failing :(
Auto comment: topic has been updated by scott_wu (previous revision, new revision, compare).
Who thinks B was harder than C ?
I didn't even understand C.
B is easier as algorithm, but harder in terms of implementation accuracy (a lot of possible cases).
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.
So, you are saying that 10 IF statements is not a lot of cases? :)
Okay... but still not 14 "if" and 6 "else" ;)
Now just multiply all your IFs on recursion depth and compare :)
"Easier" is not a synonym for "shorter code".
I've found a short and easy solution: 15992405 without many ifs and elses
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
Both will advance probably :)
I am in 203rd place. Only three places from final(((
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.
Thanks for the contest. I'm interested in editorial
Reminds 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.
Identical participant output results in different checker's comment:
http://codeforces.me/contest/626/submission/16002527
participants output: 3 0 475712 999999
checker output: wrong answer jury found better answer: expected simple skewness 262143/3, found simple skewness 48575/48575
http://codeforces.me/contest/626/submission/16008372
participants output: 3 0 475712 999999
checker output: wrong answer jury found better answer: expected simple skewness 262143/3, found simple skewness 48575/3
Also seems to give Denial of Judgement when I try to print some stuff to debug: [submission:http://codeforces.me/contest/626/submission/16009256]
Yes, checker crashed if you output some large number first. That happens. No one was affected during the contest anyway.
Checker is OK now, submission was rejudged.
We noticed bug in checker's comment during the contest and fixed it. So the first submission was made before the bug was fixed.
How to solve D?
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
And which is the proof about this solution?
Thanks :)
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
Failed systests in 2 problems because of overflow
Screencast with russian rock
Wait for my scrincast with russian rap
Can you code and sing at the same time?
Are there any other contests before the final round? Or there will be 2 weeks without any contests...
Only one more Legendary grandmaster till all in the top rated be Legendary grandmaster. ;)
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.
min(2, n) cards of each is enough to decide :)
http://codeforces.me/contest/626/submission/16008137
can someone please tell me why this solution for problem D gives TLE 16009986
let 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 :)
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.
thanks for correcting me ,yes it is O(m^2 log m^2) .
fixed and got AC .
No editorials?
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?
It is binary search! :D
We are using binary search on possible answer. We know that if
xis possible that all values greater thanxare possible. Similarly, ifxis not possible, all values less thanxare not possible. So takemin=0andmax=INFand calculatemid. Ifmidis possible then our answer will be greater than or equal tomidelse less thanmid. Iterate till only one possible answer is left which will be the answer.Why I get TLE ? on 2 RG ?
for submission ? 16006497
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.
I think they made a clarification that test 2 is not equal to pretest 2, and gave the data for test 2.
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 Input
2 RB
Иногда можно и топ 6 победителей написать... так, на всякий случай.
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?
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.
I wonder how much rating gain Bus will get if he did not purposely lowered his point o.O
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.me/contest/626/submission/16013981
Out-of-bound access.
i + j < 5200=>i + j + 1 < 5200Well, I think you are wrong — if the array dp has 5201 elements, so
i + j + 1 < 5201=>i + j < 5200There is some problem with long double on CF, yeah, I know it sucks :/
PS: http://codeforces.me/contest/626/submission/16019223 :)
deleted
Что он сказал?
Anything known about top 20 local finishers?