ahmed_aly's blog

Let's judge our solutions in Facebook Hacker Cup 2015 — round 1
By ahmed_aly, 9 years ago, In English

Edit: Looks like the following outputs are correct, you can use them to judge your solutions (or you can submit your solutions here). Also it looks like many contestants will fail in the last problem, so I guess the cutoff will be 60 points (anyone with at least 60 points will be qualified).

Until Facebook finishes the manual judging, let's compare our solutions against each other. Here are what I think should be the correct outputs for the given inputs, please run your solutions against these inputs and write a comment here and say what your solution agrees with and what it doesn't.

A. Homework

Full input link: https://drive.google.com/file/d/0ByHbOJKKpXM9dEtiSkxZdExXR00/

Full output link: https://drive.google.com/file/d/0ByHbOJKKpXM9Y1Q0dVZvUkRxanc/

B. Autocomplete

Full input link: https://drive.google.com/file/d/0ByHbOJKKpXM9eklueGpLdmh1ZEE/

Full output link: https://drive.google.com/file/d/0ByHbOJKKpXM9TWdMUVo2amJ2RUk/

C. Winning at Sports

Full input link: https://drive.google.com/file/d/0ByHbOJKKpXM9eTU0YVFRSHUyWTg/

Full output link: https://drive.google.com/file/d/0ByHbOJKKpXM9NnhpX2xfOUlJelU/

D. Corporate Gifting (this is not the output I submitted, what I submitted was wrong)

Full input link: https://drive.google.com/file/d/0ByHbOJKKpXM9elVuOVNld3pRMkE/

Full output link: https://drive.google.com/file/d/0ByHbOJKKpXM9SG43c1R3ZHlrWGc/

The above outputs are not guaranteed to be correct, I'll update the post if I found that any of them is wrong.

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

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

There is this too http://codeforces.com/blog/entry/15829#comment-207625

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

I agree on all outputs. Of course I have a history of making stupid mistakes on FBHC.

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

I have uploaded the round 1 problems to an online judge.

P1 Homework

P2 Autocomplete

P3 Winning at Sports

P4 Corporate Gifting

I used my own inputs and output as the test data. Please note that the judge is strict and requires the output to be in the exact format as the sample output (i.e. newline after every case, # signs).

Also, the hard memory limit for the problems is 1GB and time limit is 1 minute, which may differ a bit from your local resources.

On the judge, please do not read from file — all input/output is from/to stdin/stdout.

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

    I'm getting RTE on the last problem, probably due to stack size.

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

      Sorry, I will try to increase the stack size and rejudge in a few minutes. Also I will raise the memory limit to 1GB for all the problems.

      Update: The issue is resolved.

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

        If I am getting RTE because of exceeding the memory limit. Will the solution be discarded?

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

          If you mean on the real Facebook Hacker Cup, then no, because me putting the problems on the judge is totally unofficial. If you mean on the judge, the solution will not be deleted and you can view it at any time.

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

      Ok, I haven't found the problem (yet), but I ran your code on the 32-bit judge. The RTE only happens on the 64-bit (and faster) ones, so we're still looking into that.

      Update: The "few minutes" turned into "almost an hour" but I finally fixed the issue. In case you were wondering, it's because I'm bad and forgot to recompile the C++ part of the judge. Sorry to anyone who was affected by this stack size issue! I'm in the process of rejudging all the RTE/IR.

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

        I'm getting Stack Overflow with Java 8 in the problem B. Can this size be increased somehow? Thanks!

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

          It is done.

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

            Thanks! It passes the first case now but I'm still getting Stack Overflow in the second test case. Could you please increase it further? Thanks again!

            Edit: Thanks FatalEagle. I indeed confused it with the Gym contest. I'm sorry for the inconvenience!

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

              Ah, maybe you are talking about Codeforces Gym. In that case, I'm sorry but I have no clue how to change the stack size. Perhaps someone more experienced than myself could offer you a solution.

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

    Thank you very much!

    Though I realized that I got D wrong which makes me sad, because so many people submitted it and it looks that cutoff will be definitely higher than 60 pts ;___;. I got some little hope that given sufficient amount of luck I may be able to qualify to onsite and I failed on first round, so pathetic :(. I think that I just disregarded this round since it lasts 24h, 500 people qualify and so on ;/.

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

      Oh come on! I bet that 60 pts will be enough to advance — just read all the comments of people like you who submitted D but failed on it.

      I personally failed as well because I somehow came up with provement that 3 colors would be enough but I have no doubts that will advance — we don't need to underestimate weaknesses of other contestants.

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

        Hm, on the second thought it was pretty easy to came up with a wrong solution. Was bicoloring enough to pass samples? It was pretty tempting to code that :P. But there are >1300 people with submitted solutions which are worth >60 pts + don't forget about manual judgments, I guess we just need to wait.

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

          The final sample requires a 3, if I'm not mistaken.

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

          I read a comment on FB hacker cup that the cutoff point will not be affected by the manual judgement(which gave me some hope). Let's hope the cut off points will just be 60 :(

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

        Nice to hear that I wasn't the only one 100% certain of my "proof" that 3 colors are all you need. :) However, I'm not that confident that 60 points will be enough ... but there's still hope.

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

        I didn't assume anything about the number of colours and used a more programming-oriented solution — when doing the DP, you can just consider the best colours of sons and the 2 smallest ones that aren't the best of any son.

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

    Thanks for uploading the problems. Actually adding them to CF Gym might be better as users here are already registered and can submit the problems directly. I think Mike already did so.

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

for the last problem I constructed a directed graph for the given input , nodes — employee ID and edges — directed edge from A -> B if A is the manager of B . Then I ran a simple dfs hitting base cases filling from 1 as least for each nodes to provided least expenditure which is greater than the max value than its sub employees and saved it in a separate array and then accumulated the result which I tested for many cases and runs well for 2*10^5 big cases also and throws a seg fault all of a sudden for 5th case this approach correct ?

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

    Actually you need dynamic programming here..... maximum number of color we need to minimize the result will not be greater than log(n).

    dp state (i,prev) // i is the current node and prev is the color used.

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

    The RTE is most probably due to stack overflow. If the tree is something like: 1 -> 2 -> 3 -> ... -> 200000, then your dfs will go to a depth of 2*10^5.

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

      thanks a lot !! yes now I get it can you then clarify me on the maximum depth the recursion can hold ? and now while checking Sammarize_blog_entry I realized that keeping color 1 for all leaves would fail in a case where root has 2 children and one of these children has 1 child mine would throw 7 while I can get 6 .

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

checked !! all the outputs matched !! :) hope we do not have same bugs :D

it's very unfortunate for me that i could not submit my D for stupid stack overflow problem :( :(. i tried number of ways to increase stack size in 6min but failed :( :(....

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

I agree with the outputs here. My first 3 solutions are good, except the last one.

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

1st & 3rd outputs are identical with yours. 2nd output is different. 4th problem hasn't been solved.

you can check differences here... https://www.diffchecker.com/diff

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

plus this comment if u have 60 pts

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

plus this if u have more then 60 pts

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

plus this comment if u have less then 60 pts

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

all outputs match :)

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

Found silly mistake in my C. A,B,D matches.

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

All matched, except B...

FOR(tc, 1, z) {
   cin >> n;
   nodes_num = 1;
   FOR(i, 0, nodes_num) nodes[i].clear();
   //...

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

    This is why in problems with testcases you should wrap everything in struct like in following code: http://ideone.com/wenuKz . It doesn't allow you to make silly bugs in clearing data structures.

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

I've added the round to the Gym: 2015 Facebook Hacker Cup, Round 1. Used inputs/outputs from ahmed_aly. Feeling glad that my solutions passed the tests :-)

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

    I'm getting Stack Overflow with Java 8 in the problem B. Can this size be increased somehow? Thanks!

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

Thanks for posting this! My A,B,C match (and I already knew my D was wrong).

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

Darn, apparently the input wasn't given as a topological sort in D (i.e. parent[i] < i). Am I the only one who thought this?

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

Is it just me or for the D problem, i found less values than your output...

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

I literally jumped when all my submission got accepted as verdict in the codeforces gym. Then I realized I didn't manage to submit problem B.

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

Stack overflow caused me 40 points T_T

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

Yes match for A to D ;-)

I didn't notice this blog when I upload FBHC problem with my test data to SPOJ. By the way, you can compare your output with mine on SPOJ here.

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

Is it possible for only 50pts to advance? I have made stupid error on question B and C:(

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

I have submitted the solutions for all the problems, and I have received a tick on all of them on the scoreboard. According to the scoreboard, I have a score of 100. Is this the final score? Or is it possible that some of my solutions may be wrong?

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

    Your solution is only judged at the end of the round, so it is not final result,BTW you can check your solution in Codeforces/Gym.

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

Got memory limit exceeded in B. Matches to output given by Ahmed Aly. UPD: Now getting Judgement Failed.

→ Reply