SPOJ.com - Problem HISIX

HISIX - Hi6

"I read somewhere that everybody on this planet is separated by only six other people. Six degrees of separation between us and everyone else on this planet. The President of the United States, a gondolier in Venice, just fill in the names. I find it A) extremely comforting that we're so close, and B) like Chinese water torture that we're so close because you have to find the right six people to make the right connection... I am bound to everyone on this planet by a trail of six people." - Ouisa Kitteridge, "Six Degrees of Separation"

Is widely know that one is separated from everyone in the world in no more than 6 degrees of separation. A degree of separation is defined by the minimum numbers of connections you need to make to contact someone else. For instance, if you know personally another person, then you are separated by one degree. If you know somebody through some friend but not directly (a friend of a friend), then you are separated by two degrees, and so on.

Nevertheless, young Kevin Smith is not convinced about this theory and wants to probe it false. To achieve this, he has hacked the Hi6! social network and requested you to help him knock down the theory of six degrees of separation.

Input

The first line contains an integer T, which specifies the number of test cases. Then, T test case descriptions will follow. Each test case will start with a line with one positive integer, N meaning the number of connections. The next N lines will contain the following pattern:

<name_1> <name_2>

meaning that person "<name_1>" is connected with the person "<name_2>" by making D connections and vice versa. Note that both persons can know each other by a lower degree of separation using other connections.

Output

For each input case you must print the string "Case #i: ", where i is the test case number, starting from 1, following by the maximum degree of separation between the specified people. If there is someone that cannot connect to another person, print "INFINITE" instead.

Constraints

All names will be non-empty strings composed only by lowercase characters.
All names will have between 1 and 10 characters, inclusive.
"<name_1>" will be different than "<name_2>" for all connections.
There will be no pair of connections between the same pair of persons.
D will be an integer between 1 and 1000, inclusive, for all connections.
T will be between 1 and 100, inclusive.
N will be between 1 and 10^5, inclusive.

Example

Input:
3
2
john judy 1
mary peter 1
3
john judy 7
john peter 2
judy peter 2
7
john judy 3
katie peter 4
john peter 2
judy mary 1
peter mary 2
john katie 1
katie mary 1

Output:
Case #1: INFINITE
Case #2: 4
Case #3: 3

Submit solution!

Added by:	Daniel Ampuero
Date:	2010-10-15
Time limit:	1.447s-2.940s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	Own Problem

hide comments

2018-05-19 05:33:02
By "correct" I mean of course the optimal (and sub-optimal) ones; I think of SPOJ as a school where we get assignments meant to lead us to optimized solutions, be it by observation, studying algos or implementation experiments. Like in school, we should be rewarded for achieving the range of desired solutions; without reward the whole thing loses its meaning. Now it's been long since I've come to terms with the fact that many psetters don't bother to or know how to design the problem such that the desired solution will get AC in various languages while not allowing unwanted one in C. Yes this is often hard to do, but graph problems are usually not the case. Here a naive solution would fall apart *regardless* of TL, even for much smaller n, and would be a monster effort to produce compared to learning and adapting a known algorithm (which is what the question demands, but fails to recognize unless you implement it in C). Do we really need fractions of a second to separate O(n^3) and O(n!)?

I'm also uncomfortable with the spam here we've produced, don't think we need to move it elsewhere though. First, I'd be barking up a wrong tree since, of all, your problems have particularily low TLE rate, second I'm merely alerting other psetters, that might pass by here, to poor problem design. Most people intend for others to have fun with their problems and only set them badly because issues like we've discussed have never been pointed out to them.

Last edit: 2018-05-19 09:48:19

2018-05-18 12:36:23
Except for problems focused directly on implementation difficulty, virtually all problems don't 'accept all correct algorithms' (e.g. the most common problems which require nlogn vs. n^2), they accept 'all correct and fast enough algorithms' - the problem is almost always not 'how do I get the right answer' but 'how do I get it fast enough'. Its too bad O(n^3) can manage to pass even here, but that just shows it's impossible to enforce correct complexity (which is what you said it should be used for) while letting slow languages pass (although that surprises me, n^3 vs n^2logn is slower by a factor of over 100). Hackerrank, for example, allows to easily set different TL for different languages - I think it's fair to request TL for slow languages that pass with the same algorithm. We can't do that here, and as a result slow languages sometimes suffer to keep fast unpotimal solutions in check (which slightly failed here) :/
P.S. I think our discussion is spamming the comments here when noone else really wants to read it :D mind taking it somewhere else?

Last edit: 2018-05-18 12:41:51

2018-05-18 03:55:33
You didn't prove anything; as opposed to psetter here, cegprakash understood there was no purpose messing around with TL in a problem like this and set it so that any correct algorithm can pass (including my PyPy solution faster than both yours and mine O(n^3) in C). Here O(n^3) in C can pass as well (see last ranked AC) so psetter clearly didn't target any specific algorithm just designed the problem poorly. The only thing TL achieves here is make Python / Java / Pascal coders waste their time wondering what they're doing wrong when in fact they might be doing everything right; this is not the kind of problem where passing a certain time limit proves anything.

2018-05-18 01:22:39
@nadstratosfer Well, to prove my point, I went ahead and coded a O(n^3) solution for GASOLINE. Accepted in 10 seconds over several test cases, so I assume I managed to fit even under 3 seconds/test case in that problem. So sadly TL doesn't enforce appropriate complexity in that problem, and possibly wouldn't even at 3 seconds. This one seems fair to me; although it might be the case that a TL could be found where the most optimized hacky C++ heuristics don't pass while optimal Python does, it's not a psetter's obligation to figure it out.

Last edit: 2018-05-18 01:23:16

2018-05-17 10:14:22
I can't see why this should be completed in 3 seconds. The purpose of TL is to enforce certain complexity or disallow brute force; the first is not the case here as you've noticed yourself, the latter would still not fly even if the limit was 1 week.

2018-05-13 23:57:56
@nadstratosfer And as a result (I haven't coded it) I believe an order worse complexity C code can pass there. Not all problems can be set for languages that are orders of magnitude slower than C/C++ which are most common in competitive. This one takes an order of 10^6 operations per test case to solve (especially if N is actually not even in the 10^3 range), if a language can't handle that in 3 seconds, not much can be expected/done from psetter's side (in my experience)

2018-05-13 19:45:53
It's hard to explain without giving off spoilers, but my point is the TL doesn't serve any purpose in figuring out the algorithm here, just enforces writing in C (compare TL in GASOLINE which uses similar concept).

2018-05-12 13:23:28
@nadstratosfer: What do you mean NP-hard? My solution is polynomial. Just not of the first degree, hence why I said N << 10^5

2018-05-11 23:48:20
Unnecessarily tight limit for what is a NP-hard problem, even if n is actually less than 700 :/

2017-03-07 00:25:38
Can confirm what Blue.Mary said - the number of distinct people in a case isn't anything close to 10^5