Facebook Hacker Cup 2019: Round 1

5 лет назад, # ^ |

Yes, they will be

→ Ответить

its_aks_ulure

5 лет назад, # |

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.

→ Ответить

5 лет назад, # ^ |

You have indeed advanced to Round 1

→ Ответить

arknave

5 лет назад, # |

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

→ Ответить

hdude0164

5 лет назад, # |

-48

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

Ideone doesn't seem to work for that

plz help...

→ Ответить

Jakube

5 лет назад, # ^ |

Use an offline compiler.

→ Ответить

hdude0164

5 лет назад, # ^ |

-13

which one???

→ Ответить

Jakube

5 лет назад, # ^ |

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

→ Ответить

hdude0164

5 лет назад, # |

-70

plz help plz.... fast

→ Ответить

fan__of_potterr

5 лет назад, # ^ |

-6

You can use Sublime + Linux Which works fine

→ Ответить

starboy_jb

5 лет назад, # |

LoneFox, What is the time limit of problem B.

→ Ответить

5 лет назад, # ^ |

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

→ Ответить

starboy_jb

5 лет назад, # ^ |

Ohh, I understood.

Thanks.

→ Ответить

farmersrice

5 лет назад, # |

+55

Great and interesting problems, thanks.

→ Ответить

5 лет назад, # |

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.

→ Ответить

arknave

5 лет назад, # ^ |

+21

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

→ Ответить

its_aks_ulure

5 лет назад, # ^ |

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

→ Ответить

arknave

5 лет назад, # ^ |

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

→ Ответить

mnbvmar

5 лет назад, # ^ |

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

→ Ответить

5 лет назад, # ^ |

+21

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

→ Ответить

mnbvmar

5 лет назад, # ^ |

← Rev. 2 →

+39

Nice :>

→ Ответить

5 лет назад, # ^ |

+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

→ Ответить

5 лет назад, # |

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

→ Ответить

all_too_well

5 лет назад, # ^ |

I did the same and got accepted.

→ Ответить

the_art_of_war

5 лет назад, # ^ |

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

→ Ответить

awoo

5 лет назад, # ^ |

← Rev. 2 →

+32

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

→ Ответить

rtanmay

5 лет назад, # ^ |

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

→ Ответить

TimonKnigge

5 лет назад, # ^ |

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

→ Ответить

rtanmay

5 лет назад, # ^ |

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

→ Ответить

TimonKnigge

5 лет назад, # ^ |

← 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

→ Ответить

rtanmay

5 лет назад, # ^ |

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

→ Ответить

finnlidbetter

5 лет назад, # ^ |

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

→ Ответить

DEGwer

5 лет назад, # ^ |

+20

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

→ Ответить

rng_58

5 лет назад, # ^ |

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

→ Ответить

5 лет назад, # ^ |

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

→ Ответить

TimonKnigge

5 лет назад, # ^ |

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

→ Ответить

finnlidbetter

5 лет назад, # ^ |

+10

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

→ Ответить

vaibhav1997

5 лет назад, # ^ |

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.

→ Ответить

khelbe_tiger_jitbe_tiger

5 лет назад, # ^ |

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

Your updated code

→ Ответить

5 лет назад, # ^ |

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

→ Ответить

5 лет назад, # ^ |

I am only printing edges given in queries.

→ Ответить

xuanquang1999

5 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

5 лет назад, # ^ |

← Rev. 3 →

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

→ Ответить

rcpc-master

5 лет назад, # ^ |

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

→ Ответить

5 лет назад, # ^ |

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

→ Ответить

dush1729

5 лет назад, # ^ |

← Rev. 2 →

impossible

→ Ответить

5 лет назад, # ^ |

What?

→ Ответить

5 лет назад, # ^ |

-16

Oh god! Are you saying Impossible != impossible?

→ Ответить

kusumit

5 лет назад, # |

+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?

→ Ответить

the_art_of_war

5 лет назад, # ^ |

+20

I think it is the only solution.

→ Ответить

_LeMur_

5 лет назад, # ^ |

+11

I also solved it with max flow.

→ Ответить

AomeII

5 лет назад, # ^ |

+21

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

→ Ответить

mango_lassi

5 лет назад, # ^ |

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();
	}
}

→ Ответить

aditya123garg

5 лет назад, # ^ |

Can you please explain your approach?

→ Ответить

5 лет назад, # |

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

→ Ответить

5 лет назад, # ^ |

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!

→ Ответить

5 лет назад, # ^ |

← 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

→ Ответить

atsumumiya

5 лет назад, # ^ |

+51

you indeed cried a lot for a single competition.

→ Ответить

5 лет назад, # ^ |

← Rev. 2 →

-70

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

→ Ответить

5 лет назад, # ^ |

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

→ Ответить

csegura

5 лет назад, # |

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

→ Ответить

5 лет назад, # |

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

→ Ответить

MikeMirzayanov

5 лет назад, # |

+20

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

→ Ответить

5 лет назад, # |

Why solutions are not checked even on sample test?

→ Ответить

Redux

5 лет назад, # ^ |

It’s a no feedback style of contest.

→ Ответить

5 лет назад, # |

← Rev. 6 →

-134

Gym's Testcases for Problem A are weak

→ Ответить

aid

5 лет назад, # ^ |

+53

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

→ Ответить

Deemo

5 лет назад, # ^ |

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

→ Ответить

5 лет назад, # ^ |

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

→ Ответить

5 лет назад, # ^ |

-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

→ Ответить

5 лет назад, # ^ |

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.

→ Ответить