Announcing MemSQL Start[c]UP 3.0
By cerealguy, 7 years ago, In English

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://codeforces.net/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.

  • Vote: I like it
  • +413
  • Vote: I do not like it

Comments Comments (172)
| Write comment?
»
7 years ago, # |
  Vote: I like it +73 Vote: I do not like it

Have MemSQL already sent t-shirts for the previous Start[c]UP? I don't remember ever receiving one.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Do people with such experience as you actually care about 128th T-shirt?

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +47 Vote: I do not like it

    Wait ... Contests organizers ACTUALLY SEND THEIR T-SHIRTS?

    I never received one even though I have won a few of them. :/

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Distributing 2 × 1013 T-shirts is no cakewalk > <

    → Reply
»
7 years ago, # |
  Vote: I like it -60 Vote: I do not like it

→ Reply
»
7 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Is this contest more Div 1. Level or Div. 2?

→ Reply
»
7 years ago, # |
  Vote: I like it +107 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it -46 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
  Vote: I like it -18 Vote: I do not like it

Have this contest difficult of Div2? Div1?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Yes.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +26 Vote: I do not like it

      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

      → Reply
»
7 years ago, # |
  Vote: I like it -50 Vote: I do not like it

Will this contest rated?

→ Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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).

→ Reply
»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

still long queue and contest will start in about 6 hours !!!

→ Reply
»
7 years ago, # |
  Vote: I like it -30 Vote: I do not like it

is it rated?

→ Reply
»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    It will be like a conventional combined round with problems for all levels.

    → Reply
»
7 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Why so few people registered? I expected 6000+ contestants since it's Div1+Div2 and we didn't have contest for over 7 days.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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).

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    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+

    → Reply
»
7 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Are we meant not to know the exact number of problems before the beginning?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How do you use that information? =)

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      so you know how many times you have to copy paste your template before contest

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        you seem too confident that you will solve all the problems

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

          → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it -14 Vote: I do not like it

        Did you try to solve a contest, like tourist, without any templates? :)

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Actually I used to paste the template after the contest started but I figure I can save about a minute if I paste beforehand.

          → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it -16 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I would rather have the 10 point advantage than not.

              → Reply
»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Need +49 to be blue for the first time !

Eagerly waiting for the contest !!

→ Reply
»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Scoring?

→ Reply
»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I think that round will be very epic and interesting.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

very few participants, only 4376, specially considering it is a Div1+Div2 combined round!

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For the first time in my 6 months at codeforces, I am seeing that tourist is not on page 1 in standings. :(

→ Reply
»
7 years ago, # |
  Vote: I like it +230 Vote: I do not like it

The authors sure do like PI a lot.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +67 Vote: I do not like it

    That's right. The problems were prepared by pieguy.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    hired

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Main post should have +314 score, but some people forgot to vote

    → Reply
»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    When the cycles are loops, you shouldn't multiply by 2. That's the case of the second sample

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      what is pretest 7

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have if(a != b) graph[a].pb(b)

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        and then your code will consider it as tree while it should not

        take this example:

        2
1 2
2 2
        → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it +5 Vote: I do not like it

        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.

        → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    What does it return for 

    2
1 2
2 2

    ? It should return 1.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    I'll guess that you are considering self-loops as potential roots for your trees when you shouldn't.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Was just me or someone else didn't know what is 'expected score' ?

→ Reply
»
7 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Thank you for the problems ... I actually need to work on my probability skills.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Sooo, which epsilon will work for sure on G?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    2^-1900 passes all tests I could come up with.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Damn it!

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      My solution with epsilon 1e-9 passed... Maybe the solutions are different?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hi how can you prove that the points will converge after only one interation over the possible polygon?

        → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    What epsilon? I used only whole numbers.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You could have used root of unity by modulo some number. No epsilon would be required then — just several big modules.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah, but how do you find modulo for which there's an N - th root of unity?

          → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it +11 Vote: I do not like it

            Choose prime of the form kN+1.

            → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          ← Rev. 4   Vote: I like it +3 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            In reals if w is a root then wk are also roots because input has integer coefficients and cyclotomic polynomials are irreducible.

            → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            There is a potential challenge case, #66 in the system tests:

            4
0500

            Picking a random prime is important.

            → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you please explain a bit? :(

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          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.

          → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In C problem: Why can't Bob choose 653, so he will get 653+141?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    exactly my mistake — the order of pies is given.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      OMG really??? I've spent so much time thinking what's wrong!

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Then Alice skips 592, because she wants to maximize her own score.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When he choses 141 the decider token goes to Alice who will pass the second value to Bob and take 653.

    → Reply
»
7 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve D ?? I can almost never solve expected value questions :(

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I got the same idea just before end :(

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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 :

      • 1 vs 2 -> winner is 2 we increment score by 0.79 * 1.
      • 3 vs 4 -> winner is 3 we increment score by 0.91 * 1.
      • 2 vs 3 -> winner is 2 we increment score by 0.79 * 2 * 0.97.

      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.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Okay, so I completely misunderstood problem D :-( ! Thanks for your help, it's clear now.

          → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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].

    → Reply
»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Can someone give me a hint for solving problem C?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
7 years ago, # |
  Vote: I like it +35 Vote: I do not like it

fml

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    it is 254992384/1024/1024 = 243,18 MB

    → Reply
»
7 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Why :( Why so much math :(

→ Reply
»
7 years ago, # |
  Vote: I like it +53 Vote: I do not like it

fastest system testing ever !

→ Reply
»
7 years ago, # |
  Vote: I like it +44 Vote: I do not like it

System test servers on fire again!

→ Reply
»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Why 1500 for D and 2000 for E, should'n be the opposite??

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      What was the use of this data structure? My solution used regular floating point arithmetic and worked fine.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
7 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Those system tests were faster than my rating drop last round

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

What is the usual approximate ranking to go onsite? As in, last time, what was the ranking for the 25th person that went onsite?

→ Reply
»
7 years ago, # |
← Rev. 6   Vote: I like it -54 Vote: I do not like it

have to be careful while dealing while playing with c++!!

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it +12 Vote: I do not like it

    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.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It's undefined, it can do whatever it wants, that means it can make correct answer. It can also make wrong answer.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    If you compile using -D_GLIBCXX_DEBUG it will warn you and exit on those edgy cases.

    I just learnt this yesterdat.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      thank you! :)

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you tell me how do you do that?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        Let's say you usually compile like this

        g++ -std=c++11 a.cpp

        Well, you have to add that flag to the end

        g++ -std=c++11 a.cpp -D_GLIBCXX_DEBUG
        → Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

system testing finished !!!!!

→ Reply
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

First contest post without thanking Mike Mirzayanov

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah right ... it did occur to me during the contest. Unfortunately I forgot to incorporate it in the code while coding. Thank you!

      → Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Weird, the contest page isn't showing pending rating update. It just shows finished.

→ Reply
»
7 years ago, # |
  Vote: I like it +18 Vote: I do not like it

why can't i see testcases or other solutions ?

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

When we will have access to look others' codes?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Screencast

→ Reply
»
7 years ago, # |
  Vote: I like it +59 Vote: I do not like it

Editorial!

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +18 Vote: I do not like it

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)?

→ Reply
»
7 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Screencast

→ Reply
»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

problem A has exactly 25 tests :O

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You might have a component larger than one but with one self loop, in that case you do *2 but you should not.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If there is a self loop, then none of the "if" and "elseif" conditions hold true and I do not multiply anything. Right?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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)

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks a lot. I was checking for a cycle before a self loop, just needed to switch the order of if statement.

          → Reply
»
7 years ago, # |
  Vote: I like it +34 Vote: I do not like it

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?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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 ...

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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!

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      How will we know if we will be given a spot to participate if we come to the onsite contest?

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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?

        → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        I think the problem A provides a lot of insight.

        → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I made a video trying to explain the solution to problem c. https://www.youtube.com/watch?v=VhfYgXyC8ZY

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any idea about E's 26th case?

If anyone would see the code.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Please publish EDITORIALS....

Edit : Sorry, it is published already. Blog is not updated with the link of editorial.

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Has anyone received invitation for onsite?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Same here. Look for the invitation in your Talks tab.

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thanks for the responses. Does anyone know when location/schedule details are released?

    → Reply
»
7 years ago, # |
  Vote: I like it +22 Vote: I do not like it

So will there be parallel round for those that did not finish in top 500?

→ Reply