MemSQL is excited to announce Start[c]UP 3.0 – the third iteration of the programming competition hosted by Codeforces with an onsite at MemSQL HQ in San Francisco, California.
Start[c]UP 3.0 consists of two rounds. Round 1 is online and takes place on September 16th at 10:35 AM PST. Round 1 follows regular Codeforces rules and consists of at least 5 problems. For this round, the complexity of the problems will be comparable to a regular Codeforces round. There are no eligibility restrictions to participate in the round. The round will be 2.5 hours long, and will be rated.
Round 2 takes place on September 30th at 10:30 AM PST and uses regular Codeforces rules. The complexity of the problems is higher than a regular Codeforces round, the round will be 3 hours long, and will be rated. Only people who finished in the top 500 in Round 1 can participate. The top 100 in round 2 will receive a Start[c]UP 3.0 T-shirt.
For Silicon Valley residents, MemSQL will be hosting up to 25 people on-site during the second round. The winner of the on-site round will be awarded a special prize.
If you are interested in job opportunities/intern positions in MemSQL (San Francisco and Seattle) please fill in the form http://mirror.codeforces.com/memsql2017/apply or you can do it during the registration on the round.
Round 1 has started!
There are 7 problems scored as 500-750-1000-1500-2000-2750-3000. The problems were prepared by pieguy with help from cerealguy and nika. Big thanks to KAN for helping with the contest and cyand1317, vintage_Vlad_Makeev, Arpa for testing.
Have MemSQL already sent t-shirts for the previous Start[c]UP? I don't remember ever receiving one.
Do people with such experience as you actually care about 128th T-shirt?
One does not simply not care about t-shirts.
Of course I do! I need to maintain the supply of t-shirts to not have to wash them.
Wait ... Contests organizers ACTUALLY SEND THEIR T-SHIRTS?
I never received one even though I have won a few of them. :/
Distributing 2 × 1013 T-shirts is no cakewalk > <
Says the person who doesn't even know what "round" is
you too
Is this contest more Div 1. Level or Div. 2?
Yes.
Sorry, but what does "yes" mean exactly? Div 1 or Div 2?
The meme.
Yes
So, let me get this straight. Yes means yes.
That is also a true statement.
Ja Ja Ja
I hope this should go without saying, but recent experience shows that people still need to be reminded about this. PLEASE ADJUST THE DRAIN THANK YOU VERY MUCH YOURS SWISTAKK
Finally, we have a rated contest after a long wait of 10 days. We had 4 rated contests between 29th Aug and 6th Sep. After that the frequency dropped drastically.
wow.....cool observation
Have this contest difficult of Div2? Div1?
Yes.
Div 2?
He said "Yes" don't you understand !!
I don't understand, can you explain?
yes
lol :D
This is 2h30 long contest, so it will probably be a (Div 1 + Div 2)-like contest, with seven problems, starting with Div 2 A and ending with Div 1 E.
actually, the last memSQL round 1 is 2h30 with only 6 problems and the blog also mention at least 5, so I am not sure if there would be 7 problems.
for those who is interested in the previous contest, here's the link
Will this contest rated?
I just expect to learn more from every contest Codeforces conducts. Why do people ask everytime that whether the contest is rated or not??? Completely pointless.
ikr they are insane
Is Scala a supported language in this contest?
Announcement email says that it is, but submissions still keep failing randomly with runtime errors, which is already an old issue (here or here).
still long queue and contest will start in about 6 hours !!!
is it rated?
Yes. It is rated.
i don't understand what did you mean by "regular round". Please tell us that it will be standard for Div 1 or Div2 or both of the divison :)
Thanks.
It will be like a conventional combined round with problems for all levels.
Thank You Very Much. :)
Why so few people registered? I expected 6000+ contestants since it's Div1+Div2 and we didn't have contest for over 7 days.
I imagine the number of contestants will be closer to 5000+ by the time it starts. The round is quite late for many places, especially the time the contest is scheduled to end (2305 Moscow time).
I guess because the game time is midnight in Asia, so many Asian players will not register for the game. Another reason, even round 433, the total number of div1 and div2 players is only 4200+
Are we meant not to know the exact number of problems before the beginning?
How do you use that information? =)
so you know how many times you have to copy paste your template before contest
you seem too confident that you will solve all the problems
Of course not, but I got burned by not reading 1D last rated round, so I will look at all of the problems this time
Did you try to solve a contest, like tourist, without any templates? :)
Actually I used to paste the template after the contest started but I figure I can save about a minute if I paste beforehand.
Probably I am wrong, but I always thought that the timing is only important for the problems A and B. Starting from task C the time when you solve the problem becomes less and less important.
I would rather have the 10 point advantage than not.
Need +49 to be blue for the first time !
Eagerly waiting for the contest !!
Scoring?
I think that round will be very epic and interesting.
very few participants, only 4376, specially considering it is a Div1+Div2 combined round!
For the first time in my 6 months at codeforces, I am seeing that tourist is not on page 1 in standings. :(
Must be some problem with the judge :))
Check it again.
He is back :)
The authors sure do like PI a lot.
That's right. The problems were prepared by pieguy.
hired
Main post should have +314 score, but some people forgot to vote
What is wrong with my solution for E? I'm finding all cycles and trees. Answer is 2^(number of cycles)*product of sizes of trees. https://pastebin.com/FShyKDWw
When the cycles are loops, you shouldn't multiply by 2. That's the case of the second sample
what is pretest 7
I had WA on pretest7 7 times.
I have if(a != b) graph[a].pb(b)
and then your code will consider it as tree while it should not
take this example:
You will have to additionally mark such nodes having self loops to handle above mentioned case. Number of ways for any component having such marked node will be 1.
What does it return for
? It should return 1.
I'll guess that you are considering self-loops as potential roots for your trees when you shouldn't.
Oh yes thx.
Can you explain 2 examples in problem E for me? I had read it 15 min but coundn't understand the requirement! What is a valid arrangement?
Was just me or someone else didn't know what is 'expected score' ?
Thank you for the problems ... I actually need to work on my probability skills.
Sooo, which epsilon will work for sure on G?
2^-1900 passes all tests I could come up with.
Damn it!
My solution with epsilon 1e-9 passed... Maybe the solutions are different?
Hi how can you prove that the points will converge after only one interation over the possible polygon?
What epsilon? I used only whole numbers.
One solution is to check whether:
Where omega is the n-th root of unity. Though I think it will go down unfortunately because I have really low knowledge of how precision works and couldn't choose the right epsilon.
You could have used root of unity by modulo some number. No epsilon would be required then — just several big modules.
Yeah, but how do you find modulo for which there's an N - th root of unity?
Choose prime of the form kN+1.
Actually, no, you CAN'T use a modulus for this solution to work.
For a technically correct solution over the reals (or complex numbers), you actually need to check that the sum is 0 for the phi(N) roots of unity w^k for k coprime to n. The vector space V of unreachable vectors has dimension phi(n), so of course you can't check for containment using a single dot product.
But (I guess?) cleverly checking it only for w^1 works because the actual problem's input is so constrained. It's quite likely that [0-9]^N doesn't intersect with the thinner vector space V \ {w^1*i} at all, so there probably aren't any counterexamples or challenge cases to fail on.
This is NOT the case if you move to a nice convenient finite field... then it'd be fairly easy to search for counterexamples that still lie in the space [0-9]^N. For example, using N=30, 3 and 3^7 == 17 are both Nth roots of unity modulo 31. This case will then fail if you're using w=3: "490000000000000000000000000000". 4 + 9*3 == 0 mod 31, but 4 + 9*17 != 0 mod 31, so this is not a reachable vector.
I think if you want to avoid using epsilons to solve this problem, your only choice is to do a proper FFT over a finite field. You can't fake it with a single dot product.
EDIT: Ok, I suppose you'll almost certainly get away with it if you randomize which prime you use. But I think the simplest way to solve this in the actual contest is just to do the dot product for several different roots of unity, so you can pick a weak epsilon (1e-6) and not worry too much.
In reals if w is a root then wk are also roots because input has integer coefficients and cyclotomic polynomials are irreducible.
Ah, makes sense. Neat!
There is a potential challenge case, #66 in the system tests:
Picking a random prime is important.
Can you please explain a bit? :(
The intuition is that when you have equidistant points on a circle, you can probably use the roots of unity. Then, as it's customary for problems where you have some transformations and ask yourself if you can reach some state, you should probably search for some invariant.
It's not hard to come up with it, because each operation is basically changing the value of some points which are the n / k-th roots of unity, where k divides n. And it's very well known that:
So this is why it's natural to choose the invariant described above. This way we proved that the condition from above is necessary to reach a value of 0 for all points.
To prove that it's enough, the only way that comes up to my mind is the one from the editorial. Basically you need to check whether $n$-th cyclotomic polynomial Φn(x) divides your polynomial, but this is equivalent to checking whether the n-th primitive root of unity is a root of your polynomial, because Φn(x) is the minimal polynomial in
of the n - th primitive root of unity.
Thanks!
In C problem: Why can't Bob choose 653, so he will get 653+141?
exactly my mistake — the order of pies is given.
OMG really??? I've spent so much time thinking what's wrong!
Then Alice skips 592, because she wants to maximize her own score.
When he choses 141 the decider token goes to Alice who will pass the second value to Bob and take 653.
I am realy a dumbhead — debugging problem D for 15 minutes to find out that I forgot to specify output precision... now 523th, I must be lucky to be able to proceed to next round.
How to solve D ?? I can almost never solve expected value questions :(
first, you count probabilities of appearance of all players on all layers of the tournament, then use DFS from the winner (try to use all players for the winner) and solve undetermined subtrees. You can improve the search with remembering max. gain of once solved subtrees.
I got the same idea just before end :(
Could you please explain how to get 3.141592 as best score in 3rd sample test case ? It seems I didn't get how to calculate it. My idea is described as below :
As a result we get 0.79 + 0.91 + 0.79 * 2 * 0.97 = 3.2326 (which isn't the correct output). I don't get what's wrong with my idea.
Uhm, I will try: the last thing you wrote is incorrect — probability of player 2 in final is 0.79, but with prob. 0.91 he will find team 3, so add 0.79*2*0.91*0.97, and with prob. 0.09 he will find team 4, so add 0.79*2*0.33*0.09.
Okay, so I completely misunderstood problem D :-( ! Thanks for your help, it's clear now.
DP table. I let dp[i][j] be the expected value of the BEST sub-bracket that predicts player j to win the first i rounds of the tournament. To compute it, run through every possible opponent of j in round i, compute their best sub-bracket, and use linearity of expectation.
The answer will be the max value of dp[N-1][j].
Can someone give me a hint for solving problem C?
Dynamic programming (or recursion+memoization). Starting with i=N-1, figure out the optimal results both with Alice to move and Bob to move. To figure out Bob's best move at i, see what happens if he keeps piece i for himself (making the position i+1, with Alice to move), or if he gives the piece to Alice (making the position i+1, with Bob to move). Whichever one results in a better deal for Bob, should be his move. Analogously compute Alice's best move.
fml
it is 254992384/1024/1024 = 243,18 MB
Why :( Why so much math :(
fastest system testing ever !
System test servers on fire again!
Why 1500 for D and 2000 for E, should'n be the opposite??
E had a lot more tricky edge cases. D was much easier than E if you knew how to use BigDecimal or a similar data structure.
What was the use of this data structure? My solution used regular floating point arithmetic and worked fine.
I used it just to be safe... no need to deal with potential floating point nightmares when everything is divisible by a power of 10 and there's so much performance overhead left over after doing an O(teams^2) algorithm.
Those system tests were faster than my rating drop last round
What is the usual approximate ranking to go onsite? As in, last time, what was the ranking for the 25th person that went onsite?
have to be careful while dealing while playing with c++!!
It's just a fact of C++, accessing outside array bounds has an undefined behaviour, it's not definite. Maybe it'll cause a seg fault, maybe it won't, there's no way to determine what will happen. The more you go outside the array bounds however, the more likely a seg fault will occur.
It's undefined, it can do whatever it wants, that means it can make correct answer. It can also make wrong answer.
If you compile using -D_GLIBCXX_DEBUG it will warn you and exit on those edgy cases.
I just learnt this yesterdat.
thank you! :)
can you tell me how do you do that?
Let's say you usually compile like this
Well, you have to add that flag to the end
ah ok, thanks
system testing finished !!!!!
First contest post without thanking Mike Mirzayanov
Is problem D probability + DP? I am getting WA in pretest 7 and I cant wait to know my mistake. My approach was this. We can see that the architecture of tournament is a complete binary tree. So each game will correspond to a node in this tree. We can also see that expected score for each subtree is independent (that is if the tournament comprised of only those players belonging to the subtree). If we fix the winner of the current subtree, we can independently compute the maximum expected score in each subtree that branch from the path joining the winner node in level 0 to the node corresponding to the current game, and add them to the expected score we get for fixing the current player. Am I being too vague?
It seems correct — have you checked precission of your result? I forgot to write something like %.18f instead of %f and I got WA on test 6 as well
Yes the precision is fine ....
For each subtree, it's not enough to find the best bracket. You need to find the best bracket for each subtree COMBINED with each player that can win that subtree.
For example, say there are 16 players, and the best bracket for subtree [9,16] is player 10, and for subtree [1,8] is player 1. Then it could happen that player 1's probability of beating player 10 is close to 0.5, whereas some other pair of players, say 3 and 12, have a probability closer to 1.
Then it may be better to choose suboptimal brackets, that predict 3 and 12 winning, because then you'll expect to win more points for the winner of the entire tournament.
Yeah right ... it did occur to me during the contest. Unfortunately I forgot to incorporate it in the code while coding. Thank you!
Weird, the contest page isn't showing pending rating update. It just shows finished.
why can't i see testcases or other solutions ?
When we will have access to look others' codes?
Probably after rating updates
Usually, we can see other codes immediately after contest...
what is the logic of problem c i got WA on 12. i have partitioned the array into 2 minimal difference sum not caring about order.
It can't work — for example:
11
1000 1 1 1 1 1 1 1 1 1 1
min. difference is 10 1000, but the correct solution is 5 1005.
Could someone please take a look at my submission for E, which gets TLE on Main Test 8? I thought the runtime of my code is nlogn....
Submission
Screencast
Editorial!
If we have N=10^5 equations with at most 7 terms each (1 of which is a constant), at most 1.4 * 10^5 distinct variables, and the variables can be "colored" with 6 colors such that no equation has more than one variable of the same color, is there a way to check if there are integer solutions for this system in less than O(N^2)? Potentially in O(N * 2^6)?
Screencast
problem A has exactly 25 tests :O
I did exactly what everyone else has done in E. Consider graph as undirected and check if their is a cycle that is not a self loop. If there is, multiply by 2 and if no cycle, multiply by the size of component. I got WA on test 7, can anyone help me debug this?
You might have a component larger than one but with one self loop, in that case you do *2 but you should not.
If there is a self loop, then none of the "if" and "elseif" conditions hold true and I do not multiply anything. Right?
not sure about where is the bug in your code, but it fails on the more simple test :
2 1 2 2 2
(it answers 2 instead of 1)
Thanks a lot. I was checking for a cycle before a self loop, just needed to switch the order of if statement.
How to know if I'm eligible for the onsite contest? e.g. Would there be a form so contestants can express their willingness in competing onsite and MemSQL will pick the top 25 participants?
Also curious, is it true that finishing outside of the top 500 most certainly excludes one from the onsite? Because I think there is chance that fewer than 25 people in Bay area finished in top 500 ...
Unless you live in Bay Area or have plans to travel to Bay Area on that date, you are out of luck. Otherwise you could stop by, it should be fun!
How will we know if we will be given a spot to participate if we come to the onsite contest?
Yeah, I'm planning to come. I just don't want to run into the situation where there's already 25 people there with higher rank than me, which probably means I would have to leave.
I am in the same situation. Do we just come onsite at the competition time? When and how will we get more information about the onsite competition?
I think the problem A provides a lot of insight.
I made a video trying to explain the solution to problem c. https://www.youtube.com/watch?v=VhfYgXyC8ZY
Any idea about E's 26th case?
If anyone would see the code.
You set flag mark d[l].mark = 1; and then you swap "l" and "r". As a result you have component with d[root].mark = 0. Another thing is that if you merge two trees, one with root1, and second with root2, such that d[root1].mark = 1 and d[root2].mark = 0, you don't assure that new_root of the new tree has d[new_root].mark = 1.
Really thanks a lot <3 :D
Can any body help me to clear my doubt,yesterday while solving problem c I applied recursive dp with parameter current pos,chance and sum remaining. So, to memoize i created a 3D array of size[51][2][500000],It passed all the test cases.But one thing i didn't get how ?
After investigating i found: arr[5][1][5000000]=1,didn't give error but it's third argument is out of bound but this arr[50][1][5000000] = 1,gives seg fault. Can anyone explain why?
read this
Please publish EDITORIALS....
Edit : Sorry, it is published already. Blog is not updated with the link of editorial.
It's published a long time ago...
Has anyone received invitation for onsite?
I got one about 5 days ago. It asked me fill out a form saying yes/no with a deadline of 9/26. I'm guessing it'll be a bit slow to keep sending out more invitations since there may not be much response to this form.
Same here. Look for the invitation in your Talks tab.
Thanks for the responses. Does anyone know when location/schedule details are released?
So will there be parallel round for those that did not finish in top 500?