Round 1 of the 2019 Facebook Hacker Cup is less than 48 hours away!
The round will begin on June 29th, 2019 at 10am PDT and will last for 24 hours. You can check the start time in your local timezone here.
The contest will be available here shortly before the round begins.
You're eligible to compete in Round 1 if you solved at least one problem correctly in the Qualification Round.
Everyone who scores at least 30 points (regardless of time penalty) will advance to Round 2, which will take place on July 13th. Please note that all submission judgments will only be revealed after the round ends. More details about rules and other information can be found here.
Good luck!
The corresponding Facebook post can be found here.
Update: The round has ended, and solutions have been posted here. Thanks for participating!
Does the problems visible to the members who haven't attempted the qualification round??
Yes, they will be
Hi, I had commented on the FB post but no reply. I did not received the confirmation mail for the advancement to Round-1 though I had scored 30 pts. Please check that out.
You have indeed advanced to Round 1
This starts in under 1 hour! Good luck to all!
Which online compilers should I use for such large input and outputs..
Ideone doesn't seem to work for that
plz help...
Use an offline compiler.
which one???
Doesn't matter. You can installl g++ or clang. Also most IDEs come with an in-build compiler: e.g. Visual Studio, Visual Studio Code, CLion, Eclipse, Codeblocks, ...
plz help plz.... fast
You can use Sublime + Linux Which works fine
LoneFox, What is the time limit of problem B.
The only time limit for each problem is that you must be able to generate and upload your output file within 6 minutes of downloading the input file.
Ohh, I understood.
Thanks.
Great and interesting problems, thanks.
I first submitted the correct code and the correct output for the 2nd problem, but then I bymistakenly resubmitted the code and the output, but for the output I submitted the wrong file. What do I do? The code I submitted is correct. 6 min timer has expired.
Please submit a clarification request in the Hacker Cup interface for issues like this.
I too have a query, that whether the input file changes on each new submission or it remains the same because I just forgot to download the new input file and made submission on the old input file. Can someone confirm this, I am really worried about it :(
The input file stays the same per user for the entire 6 minute window. You do not need to re-download it before resubmitting.
I guess your solution will be judged as invalid. :< You can try submitting a clarification request and describing your situation, but I wouldn't hope for much. (As a good thing, you still have time to work on other problems.)
A small lifehack for the future: you can look at the details of your submission (a link just above the submission form), where you can find the MD5 hash of your output file. You can then compare this hash to your local file (e.g. on Linux,
md5sum my-output-file) to make sure you submitted the correct output.Thanks, I did send a clarification request and they fixed it!
Nice :>
If I'm not sure about some
+-1in my code, I will just submit two versions next time and tell them later which one should be judged :DWhat's wrong with this solution for 1'st problem- Add edges as given. Calculate all pair shortest distance using floyd-warshall and then check if it matches with the given information.
I did the same and got accepted.
I have similar idea and also got wrong, run floyd-warshall on gived edges. Check if distance is correct.
Then, just printed edges for each pair of vertices in graph where there is a path with weight equal to the distance between them.
Link to code
You shouldn't print edges with weight > $$$10^6$$$.
I am printing edges with weight=1 (for the nodes which are not mentioned in the input edge list. I am just joining all of them with a single node with weight=1)
Still got WA.
Here is the code: https://codeforces.me/gym/102264/submission/56359042
But then you are introducing new edges and therefore possibly newer shorter paths. The statement says your output graph needn't be connected, so you can just print the input without adding extra edges (provided the input satisfies the triangle inequality).
But I am adding the remaining nodes(which are not connected with any other node) with only one node(let's call it node A). How will this result in newer shorter paths because the remaining nodes do not have any constraints on them (i.e. Not mentioned in the input edge list)
You're right, my bad. The issue is in your Floyd-Warshall code. It is important that your loop structure has the following form:
That is, your outer loop runs over all possible 'midpoints' to relax. To see why this works, imagine the optimal path. Every time the outer loop (over
b) runs over a vertex in the optimal path, this vertex gets 'cut out' by the relaxation step (imagine removing it and connecting its endpointsaandcwith a new edge).Conversely, your code currently has the following loop structure:
Here we loop over the point to relax over (
b) inside. It's not easy to find a counter example for this, e.g.:.. where all edges have weight 1. This loop structure will never find the optimal path from
0to1, see here: https://ideone.com/rdJue1Ah, yes you are right. I thought the loops are independent because that's how they look, i.e. the initial and final values are 0 and n-1 in all of them, so I thought the order doesn't matter.
Thank you so much for the clear explanation.
Update: I submitted again after making changes and got AC now.
*Unless you run it 3 times: Incorrect implementations of the Floyd--Warshall Algorithm give correct solutions after 3 repeats (Recent paper uploaded to arxiv).
Hi, I am one of the author of this paper. Where did you know it? (Just for my curiosity)
There's a funny story behind this paper. They prepared a problem that requires Floyd Warshall on AtCoder. Then, they wrote incorrect solutions to make sure that they fail — but magically, with three repetitions, they passed.
Nice. What's next? Maybe it's enough to run greedy approach three times to solve knapsack? That would mean that P = NP. Even more, that would mean that 3*P = NP and you can compute N from that.
Actually no, the opposite is then true, if P = NP and 3*P = NP then 3*P = P so P = 0 and N is indeterminate :)))
I think I saw it on the "Theory of Computing Blog Aggregator" RSS feed as a newly posted paper on arxiv.
What I did was first checked the given data with floyd warshall and if passed then printed the same data in the output. I got AC.
Instead of doing what you did, just printing all the edges in your 'edges' vector gave AC.
Your updated code
Bear in mind that edge weights in your graph must be between 1 and 1,000,000, inclusive. Some pairwise node distances in the graph (aside from the ones in the restrictions) may exceed that value.
I am only printing edges given in queries.
Did you consider the case where multiple distance request are on the same pair of vertices?
In question it is mentioned — "No two requirements pertain to the same unordered pairs.
Maybe you made all the nodes 0-indexed during your input processing and printed them back out? The nodes are 1-indexed.
No I printed them based on 1 indexing. Here is my solution — https://ideone.com/zmzB2a
impossible
What?
Oh god! Are you saying Impossible != impossible?
I came up with a max flow solution for C, but didn't have time to code it. Did anyone else take this approach?
I think it is the only solution.
I also solved it with max flow.
Am I the only one who solved C with DP?. To whom it may concern, link to my code: https://pastebin.com/ziQz0hAp.
I also used DP, but only had $$$N^2$$$ states compared to what seems like $$$N^4$$$ in your code.
Can you please explain your approach?
I think I have been judged incorrectly for problem A, I have checked my output by running someone else's code whose code got accepted. Both the outputs match.
LoneFox
I'm afraid your submission is indeed incorrect, there's at least one case for which it outputs a graph when the answer should be "Impossible". Please see this post for the official solutions and full input/output which you can download!
I have matched my outputs by running two person's codes on the input I got and our outputs match exactly. diffchecker says the two files are identical
If my solution got rejected, they how did their's solution get accepted, even when the order of the printing of edges exactly matches with theirs
LoneFox
you indeed cried a lot for a single competition.
I have submitted the same exact code on Codeforces Gym and my code got accepted. Now?
LoneFox
I've responded to your in-contest clarification with your submitted output file as well as the correct one, so you can see for yourself where exactly you went wrong. I can't comment on the CodeForces gym and how its own custom judger was set up.
A solution for problem D.
First, if V = number of points, then every line might be a vertical line, so consider this as an alternative.
Otherwise, at least one line must be horizontal. Sort the points by X and then by Y. Now for each point we think about the solution if this point is the last one with an horizontal line. If it has an horizontal line, all the points that are upper and to the left must have horizontal lines. The points that appear later have vertical lines. Finally, the points that are at the left and lower, might be vertical or horizontal. If some of them can have horizontal lines (based on the value of H), it is good for us (because the additional cost is 0), so we put horizontal lines in those that have a larger Y. This can be implemented efficiently with binary search trees (for instance using the ones in the STL). Of course, if the number of horizontal lines or vertical lines results in a too large value, this option is discarded.
Auto comment: topic has been updated by LoneFox (previous revision, new revision, compare).
The contest is in Codeforces::Gym: 2019 Facebook Hacker Cup, Round 1
Why solutions are not checked even on sample test?
It’s a no feedback style of contest.
Gym's Testcases for Problem A are weak
Maybe you should read the proof of Floyd's algorithm and see why the order is important.
Pfff, no. I'd rather ask it publicly and let somebody else rewrite the proof and explain it to me in a magical way.
xd
"I'm getting WA" changed to "testcases are weak".
Also, if you get WA on some big test, you can still test it yourself on small random tests. Read more here.
I got my mistake but still my wrong solution got accepted on Codeforces Gym. There was no option to delete the comment so I edited it so that people dont make the same mistake I did and run to Facebook telling that their solution got accepted on Gym but it gave WA on Facebook
Then next time write a new comment for that. You modified your comment and now all replies don't make sense unless somebody clicks a small
<- revbutton.Sure, will remember in the future. Thanks!