eduardische's blog

Facebook Hacker Cup 2015 Round 2
By eduardische, 10 years ago, translation, In English

A reminder that today at 21:00 GMT the second round of Facebook Hacker Cup 2015 is taking place. After first round last weekend 732 contestants are continuing the battle. Top 100 from the second round advance to the third, while top 550 receive T-shirts. The round will be 3 hours in length. For contestants the tasks will be available here, while the standings — here.

UPD: Round is over, provisional results have been published. Cutoffs:

  • Advancement to Round 3: 55 points (A+B+C) with time ≤ 2:21:53
  • Facebook Hacker Cup 2015 T-Shirt: 10 points (А) with time ≤ 30:23
  • Vote: I like it
  • +67
  • Vote: I do not like it

Comments Comments (113)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Did they send notification by email this time? I didn't receive it...

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

    I got one.

    Also, 50 more shirts! Yay!

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

Hmm contest starts 5am here.. Not sure if I should go to sleep or stay awake (・_・ヾ

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

Good luck, everybody! May we have a smoother round than last time :)

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

    Is ranking going to be online during the contest? Is it going to be frozen before end of the round? When will we know the official results?

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

      The live (pre-judgment) scoreboard is available to everyone during the contest. It never gets "frozen" (in the ICPC sense) because you don't actually see the judgments until the end of the round. The scoreboard should be revealed shortly after the end of the round.

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

        Why can't people not competing see the problems? Can't think of any cheating argument or anything else. Would make it more exciting as a spectator to be able to see what problems people are solving.

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

          Agreed. We're going to make sure this is available for next year. We unfortunately don't really have any time to do development on the system during the contest season because we're busy with the administration of the contest. But I intend to make a bunch of improvements for next year.

          I just made a post with the problem statements: https://www.facebook.com/hackercup/posts/904095026289353

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

            One thing I would like to add if possible divide a problem into two set, like gcj one having small test and another large. Otherwise it is painful to do small mistake which you can not correct after 6 min.

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

            Could you reupload the image for the last problem (Fox Socks) in bigger resolution, please? It is possible to read it, but it is quite problematic.

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

              There's an image?

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

              You can click "Options" and then "Download" (if you're on a desktop).

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

                I am, and I don't see "Options"; neither does Ctrl+F.

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

        Could you share an estimate on when the results will be available? Does it make sense to wait or should we go to sleep?

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

          On an fb post, they said about 30 minutes

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

          Announced estimate from home page was 30 minutes ;-)

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

    Last problem: does the queries mean:

    From bin Ai to Bi or from bin Ai to bin (Ai + Bi-1) ?

    Edit: nevermind, I got response from organizers. It was Ai to (Ai + Bi — 1)

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

I want to express my gratitude towards the authors of the last task. I believed I love segment trees so much that I can code them really quick. You showed me how wrong I was.

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

How to solve the 25 points problem?

I've tried a greedy approach by picking up the string that will decrease the cost and in case of equal the one that has less similar suffix strings. But unfortunately I got a bug that I couldn't discover before the 6 minutes passed :(

Is my approach correct?

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

    I used dynamic programming (for trie nodes in DFS order), but I don't know if a greedy solution is possible.

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

    I did a dynamic programming, after you sort the strings: best[i][j][l], the minimum cost if you put the i-th string, you already have j other strings, and the cost of adding it is l. When you add another string, you look at the last one added and it's cost l, and see if by adding the new string you'll change the cost, so you can take this into account (since the cost of a string i is determined by the previous and the next in the sorted array)

    It ran in in about 3 minutes.

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

    Greedy approach:

    1. start with all possible one character prefixes as S

    2. until you have K prefixes do steps 3-4:

    3. remove shortest prefix X with most direct childs from S

    4. add all prefixes starting with X and one character longer then X into S

    5. print sum of prefixes lengths in S (K oldest if you have too many)

    Special cases:

    • if prefix has only one indirect child there is no reason to remove it

    • if prefix is only direct child of its parent use its parent length for step 5

    • use word+'#' so every word ends in leaf. just make sure 'abc#' prefix length is 3.

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

Seems like last problem needs only accuracy, accuracy and accuracy :(

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

    It also requires some interesting insights (imo). When I first saw it I thought it was a segment tree problem with a bunch of complexity thrown in for the sake of making it take longer.

    It took me quite a while to realize that you need to have two trees (or a tree with two sets of values) for the odd- and even-numbered bins to handle the fourth operation. Figuring out what to store in the tree to handle the first two operations was interesting too.

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

Why not N ≤ 100000 and M ≤ 100000 on Fox Socks? My computer couldn't run 1000000 in time...

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

    Maybe to avoid bruteforces ran on supercomputers...

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

    My laptop is more than 5 years old, and it processed the input in time in 1 thread. Either you need to write faster code, or your computer is too old. Still I didn't expect the input to consist almost entirely of max tests.

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

I won't say, how I am impressed by the innovative and interesting task D, but am I the only one, who wrote log N solution per query, and I was able to get answers only to 11 of 20 tests due to big constant of segment tree and slow notebook?..

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

    :) I ran my solution using 3 parallel threads, and got all cases solved in ~5 minutes. I guess you could also use parallelization to squeeze through.

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

How to come up with last problem?

  • Hmm, lazy propagation can handle this one

  • This one too

  • We can use it for this problem either

...

Lets merge all of them to make single problem and see who codes faster?

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

    Oh it could be worse...

    Why not use a tree (in preorder numbering) instead of a line?

    Why not make the tree dynamic?

    Just 4 queries? Pfft, add several more — with min/max conditions, some bitwise operations for good measure, both updating and counting ones

    and increase the limits on N, M.

    'tis a dangerous path no problemsetter should ever tread!

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

      You forgot about creating cactus out of tree by adding one more edge. :)

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

      You forgot about dynamic cactus graphs.

      // Whoops, it means I'm not the only one who thought about this :D

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

    I think the interplay between the 1st and 4th operations is a really interesting part of this problem. I agree that when I first saw this I thought it was a chimera, but there are subtleties at work that make it much more than the sum of its parts.

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

      If that is the only interesting part of this problem, why not get rid of queries 2 and 3? There are already dozens of problems on queries 1, 2 and 3.

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

        I think 1 and 2 together force a bit more consideration as to what gets stored at each node in your segment tree.

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

          If this is the first time such problem appear, you are correct. But unforetunately, FBHC is not the first one, nor the second one to come up with such problem (・_・;). Given that this problem is painful to code + already appeared on the Internet, I think many competitors felt like (╯°□°）╯︵ ┻━┻ (at least 36 people downvoted your 1st comment).

          Also, about the 3rd problem, isn't it too old too? DP on tree, at each vertex you need Knapsack DP to select K vertices from subtree. I solved it many times already. And it was quite straight-forward to reduce to that problem. (˘_˘٥)

          Overall, so far I haven't seen any interesting problems (all are old, only more complexity is added). Since next round is to select top 25, I hope the quality of problems will significantly improve.. ヽ(•‿•)ノ

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

            I understand where you're coming from. If you have some particular favourite problems from any contest in the last few years, I'd love to see them, and this goes for everybody else too. I've always been a huge Derek Kisman (SnapDragon) fan.

            I'm probably a little out of touch because I haven't been a regular competitor at all for the last few years. But yeah, any problems you or anyone else has been really fond of recently I'm quite interested in seeing. This is the kind of feedback that really helps improve future years.

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

          How about the fact that the array was circular? Doesn't add much to the problem.. just the need to split the query in 2.

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

      If we omit the last operation (which is really just a few more lines of code), it becomes one of the first hard problems I ever encountered in a competition. Around 4 years ago. No, it's not very original. Not to mention it's practically impossible to code it in time if you don't know all the catches already.

      If it's really necessary to give a DS problem in a contest like this, then you should've omitted one type of updates and significantly decreased the point value.

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

Last problem, I finished implementing my code when there were 10 minutes left. My code passed first 4 pretests and failed the last one :(

What a great feeling.

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

    I found like 10 different bugs that didn't change answer on first 4 pretests, so if it makes you happy you can't really know how close you are to answer based on that :P

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

Furthermore, problem C has a tricky case from using DP approach if K = 1. If not considered separately, the code might output 0 instead of 1. However, no case with K = 1 was present in at least two people's inputs.

No comment on whether this is good or bad, but I hope K = 1 case wasn't present in only some people's inputs.

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

    Yeah I also noticed the same. My input also didn't have the case.

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

    You're right that there was no K = 1 case. That was an oversight on my part. If we had it, it definitely would have been included in everybody's files.

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

Can someone share tests/answers? I'm adding a training to the Gym. I have my answers for A-C, but not sure about them.

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

I want to say that quality of tests is... well, I don't want to use the word awful.

In my input for task C there wasn't any test with K = 1. Are you serious? At least there should be following test:


1
2 1
a
b

I'm sure that 10% of AC solutions for this task will handle this test incorrectly. Techincally, the answer 0 here works (since we choose some word and empty prefix is enough to pick it), but there was a remark in the statement regarding non-empty prefixes.

It is such simple idea that there should always be testcases attaining maximum/minimum possible values of constraints...

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

    Well, yes, on the other hand one might argue that it's good to not penalize contestants who solved the task correctly and forgot to add one if statement.

    The only absolutely necessary requirement is to either give this case to everybody or give it to no one. Out of four people who shared this information, no one has it, so hopefully no disaster here.

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

      In case you don't want to penalize contestants for that, why not set the constraint as K>=2?

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

    Yes, I was astonished to discover that test case is missing...

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

    Most of the participants who didn't consider this special case in their solution would just manually fix it once they see "0" in the output. So IMO missing this case is not a big deal.

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

      10% in my comment is my estimation for the number of contestant that do not pay attention for zeroes in their output. Actually I think this number may be even bigger... That really affects the final scoreboard.

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

    I've added the test to the Gym's version. After rejudge the number of solvers reduced from 52 to 33.

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

Looks like YuukaKazami (Tom Chen) have submitted his solutions for R1 instead of R2 and thus got zero points instead of first place. What a pity.

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

    I thought there could be some victims when I saw all T=20...

    I have some suggestion to FHC:

    1) That kind of errors could be prevented if FHC does more sanity check on the output file. The output of Round 1 A is positive integers, but Round 2 A is yes/no.

    2) Change the number of test cases between the problems: Why T=20 for all problems?

    3) Even if sanity check found output file is wrong, the font for notifying this is not bolded or underlined, so there is some possibility to neglect the message. Some red-background box, like notifying problem statement changes, will work.

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

      1) Yup. For next year I plan to always include the sample cases as the first K cases in everybody's input. Then we can confirm that you at least match the sample output. That'll catch this along with a slew of other problems, like:

      • Not formatting "Case #X:" properly. We get a lot of "Case #X" and "Case X:".
      • Outputting the wrong number of decimal places
      • Strange whitespace. A bunch of people were tab-separating things in the output rather than space-separating.
      • Uploading your source as your output and vice versa (in the amusing case where your source has the same number of lines as the output should have).

      2) Yeah, I intend to change this too.

      3) Agreed. I'd like a more eye-catching UI for things like this, and for clarification announcements. The current UI is at least 4 years old.

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

        Any progress on "For next year I plan to always include the sample cases as the first K cases in everybody's input."?

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

          As far as I noticed, they are always included but somewhere in the middle because tests are shuffled.

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

            I came here to ask the exact same question! I think the sample cases were also included in a random order last year, so it seems they didn't implement this, which would be a really good change. I guess I should have bugged wjomlex personally when I got to see him :p

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

              Yeah, currently the samples are always included, but mixed in. We took a different approach of catching more PEs before they happen. If you have the wrong number of cases in your output, or the wrong number of tokens (contiguous non-whitespace characters) in a case, or your first tokens aren't "Case" and "#xx:", you'll get a formatting error right away and you'll be asked to resubmit.

              The idea of matching on the samples up front was largely to prevent PEs, not WAs, so if you have the right format, but don't match the samples, we won't say anything.

              We finally changed our legacy "every problem has 20 cases" thing this year (that was very silly), and we stopped requiring a specific number of decimal places for real values.

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

You increased number of T-shirts by 10%.

I suggest you to increase the number of the advancers by 10% too.

Just an idea from the guy on the 110-th place.

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

    There are 550 Tshirts :)

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

      Yep, I know. But there were only 500 of them before round 1.

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

        Oh, sorry, misunderstood the comment :(

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

    Good idea, johnasselta took 111th place :]].

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

    +105 :)

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

    BTW, there are people in top 100 with wrong answers for this test case. Of course, I won't mention their names, because this is both unethical and unfair, but increasing the number of spots in Round 3 may actually be a good idea.

    In case you think, that I am complaining just because I didn't made it to the Round 3 — I'm truly not. I support fairness, that's all.

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

      Would it be fair for those who legitimately got to top 100?

      They want to compete among 100 participants as rules say, not among crowd.

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

      Before my submission, I had thought of this case.

      Then, I checked if there were "0" in my output, and opened the input file, searching for " 1".

      There were no such cases.

      Therefore, I ignore this situation, and submit the "wrong" code.

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

Can you give an estimate regarding the T-shirt shipment timing? It's not really a crucial thing right now, but I'm kinda worried about them getting stuck somewhere in the process. Smooth round by the way, I'm glad there were no technical issues this time.

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

    I'm going to change address in 5 months. I don't know if I should enter my current address, since if T-shirts does not come in 5 months, I'll lose it..

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

      I had the same issue a few times and the easiest solution for me was to send the T-shirts at my parents address (which changes an order of magnitude less often than mine).

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

    I'm not sure we have an estimate at the moment. I would say message me in a month and we should have a better idea then. The T-shirt logistics are one thing that I'm not really a part of.

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

      Hi, I recently figured out that my address was incorrect and I fixed it like 10 minutes ago.
      Wasn't it too late?

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

        No problem. We don't have the shirts printed yet :)

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

Did you notice to ZhengJie rank 101 ? his total time is 2:21:54!! Just 1 second more than rank 100. Is it unfair or we should call him so unlucky person ?

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

    And what is unfair exactly?

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

      I remember that in ICPC World Final 2013, they gave a bronze medal to rank 13th just because of tiny difference in total time with the rank 12th.

      There was a debate on this here

      Anyway, I think it's not unfair if they accept all participants with total time less than 1 minute with rank 100.

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

        ICPC and FBHC are too different contests, why do FBHC organizers need to care about the decisions of ICPC organizers at all? This is not a common practice, I never seen this kind of "additional prizes" anywhere except ICPC, where all rules are weird (e.g. in Asia regionals, last year & the year before that, there was rule that in each of Singapore & Hong Kong, only 1 team can advance to WF).

        There are lots of reasons why we should not accept participants with 1 minute more:

        • Just because they are a bit unlucky, now top 100 have to fight more people in order to advance to top 25.
        • It's not fair to the guys with 61 seconds slower. Why did you choose the 60 seconds cutoff, why not 10 secs, 30 secs, 45 secs, 90 secs, 120secs...
        • Normal actions that organizers should take is to follow their rules. If they break the rules once just to let some guys with few seconds slower (note that in this case, there're no technical issues like last round), how do we know if they will follow their own rules in future?
        → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Bad luck "only"...

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

For Fox Socks, the gap between the 4th and the 5th sample testcases are quite huge. I failed all the sample testcases on my first run. Luckily, the first four sample testcases are small (N=5) and I can debug them. I fixed several mistakes and managed to get the first four sample testcases correct, but the last sample case is too big to debug with. Can't get the last sample correct until the end of the round :'(

Anyway, I'm still qualify to Round 3. Yeay!

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

    Nevertheless, correct output on last sample wasn't a proof the program correctness. At some moment (with some combination of bugs) I had all samples passing, but program was still giving wrong answer on some obvious cases with n = 2.

    The best idea for this task was to start with writing naive solution (implementing what is described in statement), checking that you understand complicated input format correctly, and only then writing the full solution and stressing it with a naive.

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

I was very lucky for the T-Shirt rank 550.

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

can anybody tell me how to reduce time complexity of my code for the problem Autocomplete Strikes Back

(http://codeforces.me/gym/100587/submission/9562793)

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

    recur() doesn't modify "vector<int> y", so it should be "const vector<int> &y" to avoid copies. Furthermore, recur() is called repeatedly with same parameters, so you can use memoization.

    Also, for your own sake, use an editor with proper automatic indentation, makes the code much easier to read.

    diff: http://pastebin.com/6shUwb1f

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

Can someone enlighten me please; I see the following pattern common amongst many AC solutions submitted for problem #2: all_critical, eg. @ http://attachment.fbsbx.com/hackercup_source.php?sid=369011793270735

  • why is it necessary to +1 here: sum = 1;
  • why must the sum be divided here (and why is the term to be divided 1 - notsele[i] ?: dp[i] = sum / (1 - notsele[i]);

Is this popular approach different from what the editorial note explains @ https://www.facebook.com/notes/facebook-hacker-cup/hacker-cup-2015-round-2-solutions/1051224511560116 ?

Thanks

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    1. You have equation like dn = c0·d0 + c1·d1 + c2... d2 + ... + cn·dn, you can't calc d_n using it itself, but you now know that dn(1 - cn) = c0·d0 + c1·d1 + c2... d2 + ... + cn - 1·dn - 1
    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 6   Vote: I like it 0 Vote: I do not like it

      Explanation posted as top FB comment to official editorial:

      We can reduce the time complexity for "All Critical" to O(20^2) by computing the infinite sum in a different way, without worrying about precision and L.
Let E[n] be the expected number of playthroughs to get n critical bars.
E[0] = 0
E[n] = Σ[0 ≤ k ≤ n] C(n,k) * p^k * (1-p)^(n-k) * (1+E[n-k])
We select k critical bars which we get (we got them in 1 playthrough), the remaining (n-k) we don't get (we will get them eventually in E[n-k] playthroughs).
This formula is recursive since there is E[n] on both sides of the equation, but this can be easily solved resulting in:
E[n] = ((1-p)^n + Σ[1 ≤ k ≤ n] C(n,k) * p^k * (1-p)^(n-k) * (1+E[n-k])) / (1-(1-p)^n)
E[20] is the answer

      My question:

      In your equation, why is it C(n,k), and not C(20-(n-k), k), since you will achieve (n-k) critical bars in E[n-k] playthroughs, but in your 1 playthrough, you can select k out of the remaining 20 (ie. total) &mdash; (n-k) sections of that song?
      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Forget about 20 for a moment. You have n bars and make 1 step.

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

Yay! Received my T-Shirt today. =D

(Classy of Facebook to use FedEx delivery by the door. ^^)

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

    Eagerly waiting ! :D Haven't received mine yet. Haven't got any response lately from them either. :/

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

Just a small clarification in 20 pt problem . In the editorial , we need to calculate upto 20 powers of p and 1-p but these may become so small that P(s,i) may become zero which infact is not exactly zero. This leads to all P(s,i) values to become zero. How to overcome this?

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

    You scared me dude. Because of your post this blog appeared in the recent actions. After reading "Round is over" I thought I've missed it.

    → Reply