SPOJ.com - Problem TWINSNOW

TWINSNOW - Snowflakes

You may have heard that no two snowflakes are alike. Your task is to write a program to determine whether this is really true. Your program will read information about a collection of snowflakes, and search for a pair that may be identical. Each snowflake has six arms. For each snowflake, your program will be provided with a measurement of the length of each of the six arms. Any pair of snowflakes which have the same lengths of corresponding arms should be agged by your program as possibly identical.

Input

- The first line of input will contain a single integer n; the number of snowflakes to follow.
- This will be followed by n lines, each describing a snowflake. Each snowflake will be described by a line containing six integers (each integer is at least 0 and less than 10000000), the lengths of the arms of the snowflake. The lengths of the arms will be given in order around the snowflake (either clockwise or counterclockwise), but they may begin with any of the six arms. For example, the same snowflake could be described as 1 2 3 4 5 6 or 4 3 2 1 6 5.

Output

If all of the snowflakes are distinct, your program should print the message:

No two snowflakes are alike.

If there is a pair of possibly identical snowflakes, your program should print the message:

Twin snowflakes found.

Sample

Input:
2
1 2 3 4 5 6
3 4 5 6 1 2

Output:
Twin snowflakes found.

Limitations

- 0 < n ≤ 10⁵.

Submit solution!

Added by:	AnhDQ
Date:	2009-05-11
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:	CCC07

hide comments

2020-12-14 21:10:30
Why is having a vector in which there is 12 different snowflakes for 1 given, and then sorting them using custom sort incorrect? It is giving me ac

2020-08-10 18:22:43
Well in my guess the correct logic is whatever u do u cannot change the neighbours of a particular arm.. so think like undirected graph and make nodes and save in vector(size will be 12) and use it as reference to find the duplicate.. in my guess this is the right approach.. neighbouring here is invariant.. eg.. for the above eg for 1 2 3 4 5 6 we have the vector as {{1,6},{6,1},{1,2},{2,1},{2,3},{3,2}....} and so on.. note: make sure to insert sorted vector in map. else it may not match..

Last edit: 2020-08-10 18:23:35

2014-05-24 00:34:05 Mitch Schwartz
"...but the incorrect logic... got AC on both the places which is definitely not right."

Your writing does not demonstrate a firm grasp of the difference between weak test data and wrong test data.

The issue merits further investigation, and I hope my previous comment was clear enough regarding action to be taken on the problem. We can email the problem setter about the issue, but he wasn't responsive in the past, so it may be a lost cause. We probably will not contact admins about this, as they tend to be busy and not interested in getting between the problem setter and his responsibility (or maybe they would phrase it a little differently, but with the same effect).

Thanks for commenting about it, and for clarifying that you took reversals into account.

Last edit: 2014-05-24 00:53:26

2014-05-23 19:46:36 The_ROCK
I'm sorry but in my correct logic code(as to me it seems) I have considered both rotation and reversal which got me WA on a single testcase 2-b on the official site and thus here too but the incorrect logic(which sorts the six lengths) got AC on both the places which is definitely not right.
I think a single test case is wrong as inferenced from the official site but still I don't know.

Last edit: 2014-05-23 19:49:07

2014-05-23 18:52:05 Mitch Schwartz
@Saurabh Prakash: You should have acknowledged the fact that your claim directly contradicts previous comments stating that the test data is merely weak (as opposed to wrong). You should also have mentioned that you are taking into account both rotation and reversal of the list of lengths, since that's not clear in (this version of) the problem statement. These things would give you more credibility. I'm not motivated to verify your claim at the moment, but maybe someone else will be.

On the basis of weak test data and the fact that there are already 423 solvers anyway, I think moving to tutorial is fine (if other EB members agree), and if the test data is found to be wrong then it can be hidden.

2014-05-23 18:21:16 The_ROCK
link to original problem statement of the contest.
http://wcipeg.com/problem/ccc07s2p2
I ran my correct logic code and it gave a WA on Test Case 2-b; but wrong logic code got AC on all test cases.

2014-05-22 22:48:28 Rishav Goyal
@Francky : Could u pls make the problem statement clear in comment. It seems something conflicting in the statements.
thankss.
--ans(Francky)--> We can see in comment that it was used like that for CCC07 (same description, same files). I'm waiting for reply for other EB advice ; there's no urge to act. Please be patient. We'll perhaps modify something.

reply(Rishav) : @Francky could u please give a link to originol problem , i tried search CCC07 but found nothing just.
--ans(Francky)--> My search engine gave me that.

Finally : Order does not matter.

Last edit: 2014-05-23 07:32:10

2014-05-22 22:17:40 Rishav Goyal
(edit Francky)***********.that's all.
it's too much.
--(Francky)--> Please be respectful even if the task is very weak. The problem could be too old to be moved...

reply (rishav) : Sorry, man.! Actually it sucks if we still have wrong statement. even after so many comments. !!

Last edit: 2014-05-22 22:35:47

2014-05-17 09:30:36 The_ROCK
This is very wrong. The correct logic i.e considering the lengths of arms of snowflakes in order (consecutive) is getting WA whereas the wrong logic i.e just sorting the six lengths is getting AC.
Pls correct the test data.