8VC Venture Cup 2016 — Elimination Round
By scott_wu, 9 years ago, In English

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:

  1. Petr
  2. jqdai0815
  3. ilyakor
  4. bmerry
  5. Errichto

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

The editorial can be found here.

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

Comments Comments (172)
| Write comment?
»
9 years ago, # |
← Rev. 2   Vote: I like it -64 Vote: I do not like it

I hope This contest will be very interesting and there are many hacks. Good luck every one !!!

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

    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.

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

      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.

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

        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.

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

        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.

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

The score gaps of the first three problems is close => Must solve fast.

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

tourist is joining, how high will his rating go?

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

Hope that all legendary masters will compete. Very big prizes!!!

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

Is it rated?

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

Good luck everybody.

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

    How do you know that letters will be ABCDEFG? Are you a cheater?

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

What does top 20 local finishers mean? Is there also an onsite version of this round?

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

    Local means people who can get to San-Francisco by their own (organizers do not cover transportation expenses)

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

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

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

Перевод на русский будет?

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

It feels nice, inspiring and much exciting to compete with the Div 1 participants.

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

Oh money money.

Wwonder who will be the first , and takes the money.

1st place 2500$

tourist will still rich ))

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

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 ?

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

    No, rating change only happens after you make a submission.

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

      Yayyyy :)))

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

      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.

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

        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.

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

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

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

"Without looking, they hand their balls to Harry"

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

Okay, for E, am I right that I only need 1,2,3 or 4 elements? I couldn't handle the 4-case :(

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

    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.

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

      Oh, thanks! :)

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

      Why odd number of elements is enough? The problem kind of pushes towards this conclusion but I could not see why is it true.

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

        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.

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

    NO 6 2 2 2 3 12 12

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

How to hack C? QAQ

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

    I used 9 4

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

    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.

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

      Is 14 the right answer? If it is, then greedy probably works.

      Here is the link to my greedy solution: link.

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

      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.

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

    7 6 -> ans 20

    6 4 -> ans 15

    I used these two.

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

    I used just 2 random big numbers.

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

difficulty : A<B<C<D<<<<<<<<<<<<<<<<E,F<<<<<<<<<G

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

How to solve F?

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

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

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

      Can you please define Open Intervals ?

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

        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.

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

      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.

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

        I did this and got TLE :(

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

        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.

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

          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.

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

For Problem F, can someone explain me why the answer at the second test is 13 and not 15 ? :/

EDIT : ok I got it.

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

I guess, the statement of problem C is not describe clearly.

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

C had weak pretests / made for hacks :D I wish i read "alphabetically" earlier in B :( Cost me 3 WA

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

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.

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

    All(15) — [7,10][8,9] — [7,9][8,10]

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

    You need to keep TOTAL imbalance at most k (meaning sum of imbalances of sets)

    → Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like 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.

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

    I also got confused when the problem said that the students were stacking the blocks lengthwise.

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

    There is a clear distinction between pieces and blocks in the statement. IMHO no confusion.

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

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

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

    Unluckily. But I didn't know how to solve F, even now QwQ

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

Could anyone explain test 8 for E?

I have completely no idea :(

→ Reply
»
9 years ago, # |
  Vote: I like it +26 Vote: I do not like 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...

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

    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.

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

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

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

      I see. I briefly considered ternary search as one of my guesses, but didn't try to prove con[vex/cave]ity.

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

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

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

      I got WA7 with that solution. Is there any problems with floating values?

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

      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

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

        If the mean doesn't change, it doesn't matter which one you pick :D

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

          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.

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

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

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

            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.

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

        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.

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

      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.

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

        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.

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

          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.

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

            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.

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

              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)])
              → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          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.

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

            Yeah, the first version was incorrect, but I've updated my comment as if it never happened :)

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

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

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

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.

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

207 T_T

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

Is me only one who thinks that problem C should be more elaborated :/. I read PS thrice before i figured out what it meant :(

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

    I agree. Russian statement is about impossible to understand (at last I switched the language).

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

      Even in English it took some time to understand.

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

    No. It also has the first explanation wrong. It should be written '2' instead of '4'...

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

      It isn't wrong. 2, 3, 6, 9 and 3,4,6,9 both are acceptable i think

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

      4 is also acceptable so the explanation is right.

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

        Oh, so maybe I didn't understand it even after the end of the contest :) It happens.

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

      Both 2 and 4 is correct.

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

      how 4 came?

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

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.

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

    Me too, No lag during hacks too. And its combined round

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

    System tests was extremely fast too.

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

    It was perfectly prepared round at all. And i have not any problems with translation. Thanks a lot for everyone!

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

Conclusion : US Round = Math Round

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

It's 4:23 a.m. in China, And I think I must go to bed to have a rest. So Tired QwQ

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

    So many of us are with you.XD

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

Can any one please tell me why this submission to D fails in 6th test 16007337

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

    (2000*1999)^3 > 2^64

    You have to divide by 8 somewhere in between.

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

    Overflow at B = N * N * N * (N - 1) * (N - 1) * (N - 1).
    Before division this term overflows. Your accepted code with the changes 16008548

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

Failed due to integer overflow on problem D :(. Was sitting for so long not understanding why my code was failing :(

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

Auto comment: topic has been updated by scott_wu (previous revision, new revision, compare).

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

Who thinks B was harder than C ?

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

    I didn't even understand C.

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

    B is easier as algorithm, but harder in terms of implementation accuracy (a lot of possible cases).

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

      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.

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

        So, you are saying that 10 IF statements is not a lot of cases? :)

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

          Okay... but still not 14 "if" and 6 "else" ;)

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

            Now just multiply all your IFs on recursion depth and compare :)

            "Easier" is not a synonym for "shorter code".

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

      I've found a short and easy solution: 15992405 without many ifs and elses

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

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

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

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

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

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

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.

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

Identical participant output results in different checker's comment:

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

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

    Also seems to give Denial of Judgement when I try to print some stuff to debug: [submission:http://codeforces.net/contest/626/submission/16009256]

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

      Yes, checker crashed if you output some large number first. That happens. No one was affected during the contest anyway.

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

      Checker is OK now, submission was rejudged.

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

    We noticed bug in checker's comment during the contest and fixed it. So the first submission was made before the bug was fixed.

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

How to solve D?

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

    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

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

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

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

Failed systests in 2 problems because of overflow

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

Screencast with russian rock

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

    Wait for my scrincast with russian rap

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

      Can you code and sing at the same time?

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

Are there any other contests before the final round? Or there will be 2 weeks without any contests...

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

Only one more Legendary grandmaster till all in the top rated be Legendary grandmaster. ;)

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

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.

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

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

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

    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.

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

      thanks for correcting me ,yes it is O(m^2 log m^2) .

      fixed and got AC .

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

No editorials?

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

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?

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

    It is binary search! :D

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

    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.

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

Why I've passed pretest ? The pretest just have one testcase? :))

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

    Why I get TLE ? on 2 RG ?

    for submission ? 16006497

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

    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.

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

    I think they made a clarification that test 2 is not equal to pretest 2, and gave the data for test 2.

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

      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

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

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?

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

    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.

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

I wonder how much rating gain Bus will get if he did not purposely lowered his point o.O

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

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.net/contest/626/submission/16013981

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

Anything known about top 20 local finishers?

→ Reply