Facebook Hacker Cup 2019: Round 1

5 years ago, # ^ |

Yes, they will be

→ Reply

its_aks_ulure

5 years ago, # |

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.

→ Reply

5 years ago, # ^ |

You have indeed advanced to Round 1

→ Reply

arknave

5 years ago, # |

This starts in under 1 hour! Good luck to all!

→ Reply

hdude0164

5 years ago, # |

-48

Which online compilers should I use for such large input and outputs..

Ideone doesn't seem to work for that

plz help...

→ Reply

Jakube

5 years ago, # ^ |

Use an offline compiler.

→ Reply

hdude0164

5 years ago, # ^ |

-13

which one???

→ Reply

Jakube

5 years ago, # ^ |

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

→ Reply

hdude0164

5 years ago, # |

-70

plz help plz.... fast

→ Reply

fan__of_potterr

5 years ago, # ^ |

-6

You can use Sublime + Linux Which works fine

→ Reply

starboy_jb

5 years ago, # |

LoneFox, What is the time limit of problem B.

→ Reply

5 years ago, # ^ |

+12

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.

→ Reply

starboy_jb

5 years ago, # ^ |

Ohh, I understood.

Thanks.

→ Reply

farmersrice

5 years ago, # |

+55

Great and interesting problems, thanks.

→ Reply

5 years ago, # |

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.

→ Reply

arknave

5 years ago, # ^ |

+21

Please submit a clarification request in the Hacker Cup interface for issues like this.

→ Reply

its_aks_ulure

5 years ago, # ^ |

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

→ Reply

arknave

5 years ago, # ^ |

The input file stays the same per user for the entire 6 minute window. You do not need to re-download it before resubmitting.

→ Reply

mnbvmar

5 years ago, # ^ |

+32

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.

→ Reply

5 years ago, # ^ |

+21

Thanks, I did send a clarification request and they fixed it!

→ Reply

mnbvmar

5 years ago, # ^ |

← Rev. 2 →

+39

Nice :>

→ Reply

5 years ago, # ^ |

+116

If I'm not sure about some +-1 in my code, I will just submit two versions next time and tell them later which one should be judged :D

→ Reply

5 years ago, # |

← Rev. 2 →

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

→ Reply

all_too_well

5 years ago, # ^ |

I did the same and got accepted.

→ Reply

the_art_of_war

5 years ago, # ^ |

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

→ Reply

awoo

5 years ago, # ^ |

← Rev. 2 →

+32

You shouldn't print edges with weight > $$$10^6$$$.

→ Reply

rtanmay

5 years ago, # ^ |

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.net/gym/102264/submission/56359042

→ Reply

TimonKnigge

5 years ago, # ^ |

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

→ Reply

rtanmay

5 years ago, # ^ |

← Rev. 2 →

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)

→ Reply

TimonKnigge

5 years ago, # ^ |

← Rev. 3 →

+10

You're right, my bad. The issue is in your Floyd-Warshall code. It is important that your loop structure has the following form:

for (int b = 0; b < n; ++b)
  for (int a = 0; a < n; ++a)
    for (int c = 0; c < n; ++c)
      if (d[a][b]+d[b][c] < d[a][c])
        d[a][c] = d[a][b]+d[b][c];

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 endpoints a and c with a new edge).

Conversely, your code currently has the following loop structure:

for (int a = 0; a < n; ++a)
  for (int c = 0; c < n; ++c)
    for (int b = 0; b < n; ++b)
      if (d[a][b]+d[b][c] < d[a][c])
        d[a][c] = d[a][b]+d[b][c];

Here we loop over the point to relax over (b) inside. It's not easy to find a counter example for this, e.g.:

  0 -- 2 -- 3 -- 1

.. where all edges have weight 1. This loop structure will never find the optimal path from 0 to 1, see here: https://ideone.com/rdJue1

→ Reply

rtanmay

5 years ago, # ^ |

← Rev. 2 →

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

→ Reply

finnlidbetter

5 years ago, # ^ |

+95

*Unless you run it 3 times: Incorrect implementations of the Floyd--Warshall Algorithm give correct solutions after 3 repeats (Recent paper uploaded to arxiv).

→ Reply

DEGwer

5 years ago, # ^ |

+20

Hi, I am one of the author of this paper. Where did you know it? (Just for my curiosity)

→ Reply

rng_58

5 years ago, # ^ |

+48

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.

→ Reply

5 years ago, # ^ |

+52

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.

→ Reply

TimonKnigge

5 years ago, # ^ |

+13

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

→ Reply

finnlidbetter

5 years ago, # ^ |

+10

I think I saw it on the "Theory of Computing Blog Aggregator" RSS feed as a newly posted paper on arxiv.

→ Reply

vaibhav1997

5 years ago, # ^ |

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.

→ Reply

khelbe_tiger_jitbe_tiger

5 years ago, # ^ |

Instead of doing what you did, just printing all the edges in your 'edges' vector gave AC.

Your updated code

→ Reply

5 years ago, # ^ |

+16

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.

→ Reply

5 years ago, # ^ |

I am only printing edges given in queries.

→ Reply

xuanquang1999

5 years ago, # ^ |

← Rev. 2 →

Did you consider the case where multiple distance request are on the same pair of vertices?

→ Reply

5 years ago, # ^ |

← Rev. 3 →

In question it is mentioned — "No two requirements pertain to the same unordered pairs.

→ Reply

rcpc-master

5 years ago, # ^ |

Maybe you made all the nodes 0-indexed during your input processing and printed them back out? The nodes are 1-indexed.

→ Reply

5 years ago, # ^ |

No I printed them based on 1 indexing. Here is my solution — https://ideone.com/zmzB2a

→ Reply

dush1729

5 years ago, # ^ |

← Rev. 2 →

impossible

→ Reply

5 years ago, # ^ |

What?

→ Reply

5 years ago, # ^ |

-16

Oh god! Are you saying Impossible != impossible?

→ Reply

kusumit

5 years ago, # |

+17

I came up with a max flow solution for C, but didn't have time to code it. Did anyone else take this approach?

→ Reply

the_art_of_war

5 years ago, # ^ |

+20

I think it is the only solution.

→ Reply

_LeMur_

5 years ago, # ^ |

+11

I also solved it with max flow.

→ Reply

AomeII

5 years ago, # ^ |

+21

Am I the only one who solved C with DP?. To whom it may concern, link to my code: https://pastebin.com/ziQz0hAp.

→ Reply

mango_lassi

5 years ago, # ^ |

I also used DP, but only had $$$N^2$$$ states compared to what seems like $$$N^4$$$ in your code.

code

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
const ll INF = 1e18;

const int N = 10 + 50;
ll dp[N][N];

void solve() {
	// Sort ladders by x-coordinate
	// Divide ladders into upper and lower part
	// DP. Store A and B, giving downmost ladder in upper part and upmost ladder in lower part.
	// If ladder starts at zero, it must be at lower part. If it ends at h, it must be at upper part
	// -> O(N^2) DP states, and O(N^3) algorithm.

	int n, h;
	cin >> n >> h;

	vector<pair<int, pair<int, int>>> lads(n);
	for (int i = 0; i < n; ++i) {
		cin >> lads[i].first >> lads[i].second.first >> lads[i].second.second;
	}
	lads.push_back({-1, {0, 0}});
	lads.push_back({-1, {h, h}});
	sort(lads.begin(), lads.end());
	n = lads.size();

	for (int a = 0; a < n; ++a) {
		for (int b = 0; b < n; ++b) {
			dp[a][b] = INF;
		}
	}
	dp[0][1] = 0;

	for (int i = 2; i < n; ++i) {
		int i0 = lads[i].second.first;
		int i1 = lads[i].second.second;
		for (int a = 0; a < i; ++a) {
			for (int b = 0; b < i; ++b) {
				if (dp[a][b] >= INF) continue;
				int h0, h1;
				if (a < b) {
					h1 = lads[b].second.first;
					h0 = min(lads[a].second.second, h1);
				} else {
					h0 = lads[a].second.second;
					h1 = max(h0, lads[b].second.first);
				}
				// If that condition doesn't hold, this ladder does nothing
				if (i1 >= h0 && i0 <= h1) {
					// Place to upper part
					if (i0 > 0) {
						ll cost = dp[a][b] + max(0, h0 - i0);
						dp[a][i] = min(dp[a][i], cost);
					}
					// Place to lower part
					if (i1 < h) {
						ll cost = dp[a][b] + max(0, i1 - h1);
						dp[i][b] = min(dp[i][b], cost);
					}
					// Clear old entry since this covers it
					dp[a][b] = INF;
				}
			}
		}
	}

	ll ans = INF;
	for (int a = 0; a < n; ++a) {
		for (int b = 0; b < n; ++b) {
			ans = min(ans, dp[a][b]);
		}
	}
	if (ans >= INF) cout << "-1\n";
	else cout << ans << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int q;
	cin >> q;
	for (int qi = 0; qi < q; ++qi) {
		cout << "Case #" << (qi+1) << ": ";
		solve();
	}
}

→ Reply

aditya123garg

5 years ago, # ^ |

Can you please explain your approach?

→ Reply

5 years ago, # |

← Rev. 4 →

-63

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.

→ Reply

5 years ago, # ^ |

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!

→ Reply

5 years ago, # ^ |

← Rev. 2 →

-60

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

→ Reply

atsumumiya

5 years ago, # ^ |

+51

you indeed cried a lot for a single competition.

→ Reply

5 years ago, # ^ |

← Rev. 2 →

-70

I have submitted the same exact code on Codeforces Gym and my code got accepted. Now?

→ Reply

5 years ago, # ^ |

+21

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.

→ Reply

csegura

5 years ago, # |

← Rev. 2 →

-8

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.

→ Reply

5 years ago, # |

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

→ Reply

MikeMirzayanov

5 years ago, # |

+20

The contest is in Codeforces::Gym: 2019 Facebook Hacker Cup, Round 1

→ Reply

5 years ago, # |

Why solutions are not checked even on sample test?

→ Reply

Redux

5 years ago, # ^ |

It’s a no feedback style of contest.

→ Reply

5 years ago, # |

← Rev. 6 →

-134

Gym's Testcases for Problem A are weak

→ Reply

aid

5 years ago, # ^ |

+53

Maybe you should read the proof of Floyd's algorithm and see why the order is important.

→ Reply

Deemo

5 years ago, # ^ |

+27

Pfff, no. I'd rather ask it publicly and let somebody else rewrite the proof and explain it to me in a magical way.

→ Reply

5 years ago, # ^ |

+57

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

→ Reply

5 years ago, # ^ |

-37

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

→ Reply

5 years ago, # ^ |

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

→ Reply